distance de Levenshtein

Comparez les mots « chat » et « chars ». Pour passer du premier au second, on peut remplacer le t par un r, puis ajouter un s. Deux gestes suffisent, et un seul ne peut pas suffire : les longueurs diffèrent et une lettre commune aux quatre premières positions doit aussi changer.

La distance de Levenshtein vaut donc 2. Elle compte le plus petit nombre de modifications autorisées, et non le nombre de différences relevées au premier regard.

La distance de Levenshtein entre deux chaînes est le nombre minimal d'opérations nécessaires pour transformer la première en la seconde. Chaque opération porte sur un caractère : en insérer un, en supprimer un ou en remplacer un par un autre. Dans la version usuelle, chacune coûte une unité. Une distance nulle signifie que les deux chaînes sont identiques ; une petite valeur indique qu'elles sont proches au regard de ces trois opérations.

Le calcul compare progressivement les préfixes des deux chaînes. Le nombre d_i,j désigne la distance entre les i premiers caractères de la première chaîne et les j premiers caractères de la seconde. Les bords valent d_i,0 = i et d_0,j = j. Pour une case intérieure, on retient le minimum entre une suppression, une insertion et une conservation ou substitution : Le coût c_i,j vaut 0 si les deux caractères comparés sont identiques, et 1 sinon.

Cette programmation dynamique remplit une grille de proche en proche et conserve, pour chaque paire de préfixes, le meilleur coût déjà obtenu. La dernière case donne la distance cherchée. Pour « chat » et « chars », elle vaut 2 ; la grille permet aussi de retrouver une suite optimale, par exemple remplacer t par r puis insérer s.

Calculons la distance entre « chat » et « chars ». Les données sont les chaînes de longueurs 4 et 5, ainsi que trois opérations de coût 1 : insertion, suppression et substitution.

1. Initialisons la première colonne avec 0, 1, 2, 3, 4 et la première ligne avec 0, 1, 2, 3, 4, 5. Ces valeurs comptent les suppressions ou insertions nécessaires face à une chaîne vide.

2. Remplissons chaque case avec le plus petit des trois coûts possibles. Les lettres c, h et a coïncident successivement : le chemin optimal reste à 0 jusqu'à la case qui compare « cha » à « cha ».

3. Pour passer de « chat » à « char », la dernière lettre diffère. La diagonale ajoute une substitution : la case correspondante vaut 1. La matrice rend ce chemin minimal visible.

4. Le s final de « chars » exige ensuite une insertion. La dernière case vaut 2, donc la distance de Levenshtein entre « chat » et « chars » est 2.

5. Contrôlons la minimalité. Une seule opération ne peut pas à la fois augmenter la longueur de 4 à 5 et changer t en r. La suite « chat » → « char » → « chars » atteint bien la borne de deux opérations.

En correction orthographique, on compare un mot saisi à des mots candidats et l'on privilégie une faible distance. Si l'ordre ou le contexte des mots importe davantage que les caractères isolés, cette seule mesure ne suffit pas et un traitement du langage plus riche est préférable.

Dans une base textuelle, la distance sert à retrouver une chaîne malgré une faute, un caractère manquant ou un caractère ajouté. Une recherche exacte reste préférable lorsque toute différence doit exclure le résultat ; la recherche approximative convient quand de petits écarts sont acceptables.

Pour comparer des séquences en bioinformatique, les mêmes trois gestes offrent un premier modèle d'écart. Le choix dépend toutefois de ce que l'on veut compter : la distance de Levenshtein usuelle donne le même coût à toute insertion, suppression ou substitution.

Distance de Levenshtein et nombre de positions différentes. Compter seulement les caractères différents à la même position suppose deux chaînes de même longueur. La distance de Levenshtein autorise aussi insertions et suppressions : « chat » et « chats » sont à distance 1, malgré leurs longueurs différentes.

Distance et suite d'opérations choisie. Une transformation possible n'est pas nécessairement minimale. Pour « chat » et « chars », on pourrait multiplier les modifications, mais la distance reste 2 parce qu'une substitution suivie d'une insertion suffit et qu'une seule opération est impossible.

Chaîne vide. La distance entre une chaîne vide et une chaîne de n caractères vaut exactement n : il faut insérer les n caractères. Si le bord de la matrice ne porte pas 0, 1, …, n, il faut reprendre l'initialisation.

Transposition. Échanger deux caractères voisins n'appartient pas aux trois opérations de la définition. Ainsi, passer de « ab » à « ba » coûte 2 avec des coûts unitaires : deux substitutions atteignent ce total. Il ne faut pas compter l'échange comme une opération sans changer de modèle.

Proximité sans contexte. Une faible distance indique peu de modifications de caractères, pas une proximité de sens. Le symptôme est un résultat lexicalement proche mais inadapté au contexte ; il faut alors compléter la distance par des informations linguistiques ou propres au domaine.

Coûts modifiés. Si certaines opérations reçoivent des coûts différents, la grille calcule une distance d'édition pondérée, et le résultat peut changer. Il faut annoncer les coûts avant le calcul au lieu de réutiliser sans contrôle la récurrence à coûts unitaires.

programmation dynamique — Voir pourquoi la grille réutilise les meilleurs résultats des préfixes déjà comparés.

algorithme — Replacer le calcul de la distance dans une suite finie d'instructions et de contrôles.