Distance de Damerau-Levenshtein

En informatique théorique, la distance de Damerau–Levenshtein est une distance entre deux chaînes de caractères. On calcule le nombre minimum d'opérations nécessaires pour transformer une chaîne de caractères en une autre, où une opération est définie comme l'insertion, la suppression ou la substitution d'un simple caractère, ou comme une transposition de deux caractères adjacents.

Frederick J. Damerau (en) a non seulement distingué ces quatre opérations d'édition, mais a aussi écrit qu'elles correspondent à plus de 80 % des fautes d'orthographe humaines[1]. La distance d'édition a été introduite par Vladimir Levenshtein, qui a ensuite généralisé ce concept avec des opérations multiples d'édition, mais sans y inclure les transpositions.

La motivation originale était de mesurer la distance entre un mot correct et un mot comportant une faute d'orthographe humaine afin d'améliorer des applications telles que les vérificateurs d'orthographe. Mais la distance Damerau-Levenshtein peut aussi être utilisée en biologie pour mesurer les variations entre des séquences d'ADN.

Algorithme

Ci-dessous, le pseudo-code pour la fonction DistanceDeDamerauLevenshtein qui prend deux chaînes de caractères, chaine1 de longueur longueurChaine1, et chaine2 de longueur longueurChaine2, et on calcule la distance Damerau-Levenshtein entre les deux :


entier DistanceDeDamerauLevenshtein(caractere chaine1[1..longueurChaine1],
                                    caractere chaine2[1..longueurChaine2])
   // d est un tableau de longueurChaine1+1 rangées et longueurChaine2+1 colonnes
   // d est indexé à partir de 0, les chaînes à partir de 1
   déclarer entier d[0..longueurChaine1, 0..longueurChaine2]
   // i et j itèrent sur chaine1 et chaine2
   déclarer entier i, j, coûtSubstitution
   
   pour i de 0 à longueurChaine1
       d[i, 0] := i
   pour j de 0 à longueurChaine2
       d[0, j] := j
   
   pour i de 1 à longueurChaine1
      pour j de 1 à longueurChaine2
          si chaine1[i] = chaine2[j] alors coûtSubstitution := 0
                                     sinon coûtSubstitution := 1
           d[i, j] := minimum(
                                d[i-1, j  ] + 1,                 // effacement du nouveau caractère de chaine1
                                d[i,   j-1] + 1,                 // insertion dans chaine1 du nouveau caractère de chaine2
                                d[i-1, j-1] + coûtSubstitution   // substitution
                             )
           si(i > 1 et j > 1 et chaine1[i] = chaine2[j-1] et chaine1[i-1] = chaine2[j]) alors
               d[i, j] := minimum(
                                d[i, j],
                                d[i-2, j-2] + coûtSubstitution   // transposition
                             )
 
   renvoyer d[longueurChaine1, longueurChaine2]

On ajoute simplement cette partie au code de la distance de Levenshtein :

           si(i > 1 et j > 1 et chaine1[i] = chaine2[j-1] et chaine1[i-1] = chaine2[j]) alors
               d[i, j] := minimum(
                                d[i, j],
                                d[i-2, j-2] + coûtSubstitution   // transposition
                             )

Le coût de la transposition est de 0 si le coût de substitution est de 0 (chaine1[i] = chaine2[j] = chaine1[i-1] = chaine2[j-1] ⇒ permutation de deux caractères identiques).

Notes et références
  1. Fred J. Damerau, « A technique for computer detection and correction of spelling errors », Communications of the ACM, vol. 7, no 3,‎ , p. 171–176 (DOI 10.1145/363958.363994, lire en ligne, consulté le )

Voir aussi
  • Portail de l'informatique théorique
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.