Distance de Levenshtein - Définition
La liste des auteurs de cet article est disponible ici.
Exemples
Si M = « examen » et P = « examen », alors LD (M, P) = 0, parce qu'aucune opération n'a été réalisée.
Si M = « examen » et P = « examan », alors LD (M, P) = 1, parce qu’il y a eu un remplacement (changement du e en a).
Généralisation
En remplaçant chaîne de caractères par séquence de symboles, les symboles étant comparables par un opérateur d'égalité, on peut définir une distance d'édition fonctionnant sur d'autres types que des chaînes de caractères.
Exemple de déroulement de l'algorithme
Pour comprendre le fonctionnement de cet algorithme, prenons un exemple :
Soit s = « NICHE » Soit t = « CHIENS »
Intuition
Intuitivement, on voit bien que l'on peut transformer la chaîne s en t en 5 étapes :
- Suppression de N et I → CHE
- Ajout de I, N et S → CHIENS
La distance de Levenshtein d entre "NICHE" et "CHIENS" est donc d'au plus 5. On peut se convaincre par l'expérience que 5 est effectivement la distance entre les deux chaînes (l'algorithme de la distance de Levenshtein ne s'occupe pas de déplacement, il ne sait détecter que la suppression ou l'insertion d'une lettre, ainsi que le remplacement d'une lettre par une autre). Pour le vérifier formellement, on peut appliquer l'algorithme (ou tout essayer manuellement).
Fonctionnement
Soit n la longueur de la chaîne s (ici n=5)
Soit m la longueur de la chaîne t (ici m=6)
Si n=0 alors retourner d=m et quitter
Si m=0 alors retourner d=n et quitter
Construire une matrice M de n+1 lignes et m+1 colonnes.
Initialiser la première ligne par la matrice ligne [ 0,1,….., m-1, m] et la première colonne par la matrice colonne [ 0,1,….., n-1, n]
| C | H | I | E | N | S | ||
|---|---|---|---|---|---|---|---|
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | |
| N | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
| I | 2 | 0 | 0 | 0 | 0 | 0 | 0 |
| C | 3 | 0 | 0 | 0 | 0 | 0 | 0 |
| H | 4 | 0 | 0 | 0 | 0 | 0 | 0 |
| E | 5 | 0 | 0 | 0 | 0 | 0 | 0 |
Soit Cout(i, j)=0 si A(i)=B(j) et Cout(i, j)=1 si A(i)!=B(j)
On a donc ici la matrice Cout:
| C | H | I | E | N | S | |
|---|---|---|---|---|---|---|
| N | 1 | 1 | 1 | 1 | 0 | 1 |
| I | 1 | 1 | 0 | 1 | 1 | 1 |
| C | 0 | 1 | 1 | 1 | 1 | 1 |
| H | 1 | 0 | 1 | 1 | 1 | 1 |
| E | 1 | 1 | 1 | 0 | 1 | 1 |
On remplit ensuite la matrice M en utilisant la règle suivante M[i, j] est égale au minimum de:
- L’élément directement avant plus 1: M[i-1, j] + 1. (insertion)
- L’élément directement au-dessus plus 1: M[i, j-1] + 1. (effacement)
- Le diagonal précédent plus le coût: M[i-1, j-1] + Cout(i-1, j-1). (substitution)
Attention ! Il s'agit de Cout(i-1, j-1) et non de Cout(i, j) car la matrice Cout est moins grande que la matrice M, ce qui entraîne un décalage.
Dans notre cas, le remplissage de la première ligne donne alors:
| C | H | I | E | N | S | ||
|---|---|---|---|---|---|---|---|
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | |
| N | 1 | 1 | 2 | 3 | 4 | 4 | 5 |
| I | 2 | 0 | 0 | 0 | 0 | 0 | 0 |
| C | 3 | 0 | 0 | 0 | 0 | 0 | 0 |
| H | 4 | 0 | 0 | 0 | 0 | 0 | 0 |
| E | 5 | 0 | 0 | 0 | 0 | 0 | 0 |
Nous réitérons cette opération jusqu'à remplir la matrice :
| C | H | I | E | N | S | ||
|---|---|---|---|---|---|---|---|
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | |
| N | 1 | 1 | 2 | 3 | 4 | 4 | 5 |
| I | 2 | 2 | 2 | 2 | 3 | 4 | 5 |
| C | 3 | 2 | 3 | 3 | 3 | 4 | 5 |
| H | 4 | 3 | 2 | 3 | 4 | 4 | 5 |
| E | 5 | 4 | 3 | 3 | 3 | 4 | 5 |
La distance de Levenshtein entre les mots s et t se retrouve en M[n, m].
Ici, on retrouve bien les 5 opérations trouvées de manière intuitive, la dernière matrice fournit aussi explicitement une des suites d'opérations permettant de passer d'une chaîne de caractères à l'autre (Il existe 3 suites possibles).
