Distance d'édition (distance de Levenshtein)
Tapez recieve et votre téléphone propose receive. Il sait que vous étiez tout près, car les deux mots ne sont qu'à quelques modifications l'un de l'autre. Mesurer cette proximité, la distance d'édition, est un problème classique de programmation dynamique.
Le problème
Une modification change un mot d'une lettre : insérer une lettre, supprimer une lettre ou remplacer une lettre par une autre. La distance d'édition entre deux mots est le plus petit nombre de modifications qui transforment l'un en l'autre. Entre cat et cut, la distance est de 1, entre cat et cast aussi de 1, et entre cat et act de 2. On l'appelle aussi distance de Levenshtein, du nom du mathématicien soviétique Vladimir Levenshtein, qui l'a étudiée en 1965.
Le tableau
Soit d[i][j] la distance d'édition entre les i premières lettres d'un mot et les j premières lettres de l'autre. Transformer un mot en rien demande une suppression par lettre, donc d[i][0] = i, et construire un mot à partir de rien demande une insertion par lettre, donc d[0][j] = j. Si la lettre i est égale à la lettre j, d[i][j] = d[i − 1][j − 1]. Sinon, d[i][j] = 1 + le plus petit de d[i − 1][j − 1] (remplacement), d[i − 1][j] (suppression) et d[i][j − 1] (insertion).
Un exemple
Pour kitten et sitting, le tableau a 7 lignes et 8 colonnes. La case en bas à droite vaut 3, et la relecture à partir d'elle donne : remplacer k par s, garder i, t et t, remplacer e par i, garder n, et insérer g. De kitten à sitten, puis sittin, puis sitting : trois modifications, et le tableau prouve qu'il n'existe aucune liste plus courte.
Relire les modifications
Partez de la case en bas à droite et demandez-vous de quel voisin vient sa valeur. Si les lettres sont égales et que la case vaut autant que sa voisine en haut à gauche, la lettre a été conservée : avancez en diagonale. Si elle vaut un de plus que la voisine en haut à gauche, c'était un remplacement ; un de plus que la case au-dessus, une suppression ; un de plus que la case à gauche, une insertion. Plusieurs chemins peuvent être à égalité, et chacun donne une liste de modifications la plus courte possible.
Histoire et usages
Levenshtein a introduit cette distance en 1965 alors qu'il travaillait sur les codes correcteurs d'erreurs. La méthode du tableau a été publiée par plusieurs chercheurs, notamment par Robert Wagner et Michael Fischer en 1974, d'où son nom courant d'algorithme de Wagner–Fischer. Aujourd'hui, les distances d'édition classent les suggestions d'orthographe, retrouvent des noms mal orthographiés dans des bases de données, comparent des séquences d'ADN et de protéines, et servent à évaluer la reconnaissance vocale.
À vous de jouer
Ouvrez l'application et appuyez sur Étape. Les deux lettres comparées s'allument dans les en-têtes ; des lettres égales recopient la case bleue en haut à gauche, et des lettres différentes lisent les trois voisins bleus et ajoutent un au plus petit. À la fin, le chemin orange repart du coin, et les modifications s'affichent sous le tableau.
Questions fréquemment posées
La distance d'édition est-elle une métrique ?
Oui. Elle n'est jamais négative, elle vaut 0 seulement pour des mots égaux, elle est la même dans les deux sens, et passer par un troisième mot ne peut jamais la raccourcir : d(a, c) ≤ d(a, b) + d(b, c). Elle est donc utile pour rechercher des correspondances proches.
Qu'est-ce que la distance de Damerau–Levenshtein ?
La distance d'édition avec une modification de plus : l'échange de deux lettres voisines. Frederick Damerau a constaté en 1964 que l'insertion, la suppression, le remplacement et l'échange couvrent ensemble plus de 80 % des fautes d'orthographe. Avec les échanges, recieve et receive sont à distance 1 au lieu de 2.
Peut-on calculer la distance d'édition plus vite qu'en O(m·n) ?
Pas beaucoup. En 2015, Arturs Backurs et Piotr Indyk ont montré qu'une méthode en temps O(n^(2 − ε)) pour un certain ε > 0 contredirait l'hypothèse du temps exponentiel fort, que la plupart des chercheurs tiennent pour vraie. Pour des mots proches, en revanche, seule une bande étroite autour de la diagonale du tableau est nécessaire.
Comment la distance d'édition sert-elle à comparer l'ADN ?
Les biologistes utilisent le même tableau avec des scores au lieu de comptes : les correspondances rapportent des points, et les remplacements et les trous coûtent des points qui dépendent des lettres. C'est l'algorithme de Needleman–Wunsch de 1970 pour des séquences entières, et l'algorithme de Smith–Waterman de 1981 pour les fragments qui se correspondent le mieux.
Prêt à l'essayer ?
Ouvrez PictorX dans votre navigateur – aucune installation, aucune carte de crédit requise pour démarrer.
Essayer la distance d'édition