1A.algo - La distance d’édition

Links: notebook, html, PDF, python, slides, GitHub

La distance d’édition ou de Levenshtein calcule une distance entre deux séquences. L’algorithme utilise la programmation dynamique.

from jyquickhelper import add_notebook_menu
add_notebook_menu()

Introduction

On veut mesurer la proximité entre deux mots et un moyen simple est de construire une distance : d(m_1,m_2) = d(m_2, m_1) = ?.

Premier essai de distance : Hamming

La distance de Hamming consiste à comparer les caractères les unes à la suite des autres.

\begin{array}{c|ccccc} A & c & l & o & s & e \\ \hline B & c & l & o & u & e \\ \hline d(A,B) & 0 & 0 & 0 & 1 & 0 \end{array}

La distance est alors la somme des petites distances :

def dist_hamming(m1,m2):
    d = 0
    for a,b in zip(m1,m2):
        if a != b :
            d += 1
    return d

dist_hamming("close", "cloue")
1

Les petits défauts de Hamming

Que pensez-vous de ces deux distances (on suppose que la fonction dist_hamming est celle provenant de l’exercice 1).

dist_hamming("longmot", "liongmot")
6
dist_hamming("longmot", "longmoit")
1

La lettre i a été ajoutée à deux endroits différents : vers le début dans le premier cas et vers la fin dans le second. La distance est très différente dans les deux cas.

Une propriété souhaitable de la distance

La distance de Hamming n’est sans doute pas une distance idéale, elle n’est pas très robuste pour prendre en compte les décalages. Que pourrait-on faire pour l’améliorer ?

  • On pourrait essayer de faire une sorte de mélange Jaccard-Hamming et dire que si la distance de Hamming est trop grande, on bascule sur la distance de Jaccard. On prendrait le minimum des deux distances.

  • On pourrait essayer de différencier les mots longs et les mots courts mais comment distinguer les deux ?

  • On pourrait essayer de traiter spécifiquement les cas d’insertion de lettres. Que faire alors si on en insère deux ?

Toutes ces idées proposent des améliorations mais il est difficile de prédire si elles n’auront pas un drôle de comportement dans certains cas précis.

Plutôt que de chercher des idées d’améliorations, pourquoi ne pas se demander plutôt quelles propriétés cette distance devrait vérifier. On peut découper un mot en deux mots plus petits et écrire :

d(longmot,longmoit) = d(long,long) + d(mot, moit)

Est-ce une propriété souhaitable pour notre distance ? Cela paraît raisonnable et on voit tout de suite que la distance de Hamming ne vérifie pas cette propriété.

Si on poursuit le raisonnement, on devrait pouvoir aussi avoir :

d(longmot,longmoit) = d(longmo,longmo) + d(t, it)

Et si on écrivait plutôt :

d(longmot,longmoit) = \min \left\{ d(longmo,longmo) + d(t, it), d(long,long) + d(mot, moit) \right\}

Mais peut-être que ce qui suit paraît un peu plus juste :

d(longmot,longmoit) \leqslant \min \left\{ d(longmo,longmo) + d(t, it), d(long,long) + d(mot, moit) \right\}

Cette inégalité implique deux découpages d’un mot. Mais il existe plein de façons de découper un mot en deux. Plus exactement, si le mot a n lettres, il existe n-1 façon de le couper en deux. On note m[[1..n]] un mot n caractères :

d( m_1[[1..n_1]], m_2[[1..n_2]] ) \leqslant \min_{ 1 \leqslant i \leqslant n_1-1, 1 \leqslant j \leqslant n_2-1 } \left\{ d( m_1[[1..i]], m_2[[1..j]] ) + d( m_1[[i+1..n_1]], m_2[[j+1..n_2]] ) \right\}

Mais au fait, n’aurait-on pas envisager toutes les façons de découper un mot en deux. Donc le minimum se trouve parmi l’un de ses découpages :

d( m_1[[1..n_1]], m_2[[1..n_2]] ) = \min_{ 1 \leqslant i \leqslant n_1-1, 1 \leqslant j \leqslant n_2-1 } \left\{ d( m_1[[1..i]], m_2[[1..j]] ) + d( m_1[[i+1..n_1]], m_2[[j+1..n_2]] ) \right\}

On simplifie l’écriture en écrivant m[[i..j]] = m[i:j]. Cela donne :

d( m_1[1:n_1], m_2[1:n_2] ) = \min_{ 1 \leqslant i \leqslant n_1-1, 1 \leqslant j \leqslant n_2-1 } \left\{ d( m_1[1:i], m_2[1:j] ) + d( m_1[i+1:n_1], m_2[j+1:n_2] ) \right\}

On sait maintenant exprimer la distance entre deux mots longs à partir de mots plus courts qui les composent. Comme toute définition récurrente, il faut définir la distance pour les mots les plus courts : 1 à 2 lettres. Dans ce cas, on prendra distance de Hamming.

Distance d’édition

D’après l’égalité, il existe un découage optimal (i^*, j^*) tel que $d( m_1[1:n_1], m_2[1:n_2] ) = d( m_1[1:i^*], m_2[1:j^*] ) + d( m_1[i^*:n_1], m_2[j^*:n_2] ) $. Mais on peut recommencer à découper de f-açon optimale : d( m_1[i^*:n_1], m_2[j^*:n_2] ) = d( m_1[i^*:k^*], m_2[j^*:l^*] ) + d( m_1[k^*:n_1], m_2[l^*:n_2] ). On peut découper comme cela jusqu’à obtenir un découpage optimal où on n’a plus que des mots courts de 1 ou 2 caractères. Mais alors… pourquoi ne pas utiliser ces petits mots insécables lors de l’expression de la distance.

d( m_1[1:n_1], m_2[1:n_2] ) = \min \left\{ \begin{array}{l} d( m_1[1:n_1-2], m_2[1:n_2-1] ) + hamming(m_1[n_1-1:n_1], m_2[n_2:n_2]) ) \\ d( m_1[1:n_1-1], m_2[1:n_1-2] ) + hamming(m_1[n_1:n_1], m_2[n_2-1:n_2]) ) \\ d( m_1[1:n_1-1], m_2[1:n_1-1] ) + hamming(m_1[n_1:n_1], m_2[n_2:n_2]) ) \end{array} \right.

Ces trois options sont les seules possibles en partant de la fin du mot.