Distance de Damerau-Levenshtein

En informatique théorique et sciences informatiques, 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.

Frederick J. Damerau a non seulement distingué ces quatre opérations d'édition, mais a aussi déclaré qu'elles correspondent à plus de 80 % des fautes d'orthographe humaines. 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.

L'algorithme

Ci-dessous, le pseudocode pour la fonction DamerauLevenshteinDistance qui prend deux chaînes de caractères, str1 de longueur lenStr1, et str2 de longueur lenStr2, et on calcule la distance Damerau-Levenshtein entre les deux :

int DamerauLevenshteinDistance(char str1[1..lenStr1], char str2[1..lenStr2])
   // d is a table with lenStr1+1 rows and lenStr2+1 columns
   declare int d[0..lenStr1, 0..lenStr2]
   // i and j are used to iterate over str1 and str2
   declare int i, j, cost
 
   for i from 0 to lenStr1
       d[i, 0] := i
   for j from 0 to lenStr2
       d[0, j] := j
 
   for i from 1 to lenStr1
       for j from 1 to lenStr2
           if str1[i] = str2[j] then cost := 0
                                else cost := 1
           d[i, j] := minimum(
                                d[i-1, j  ] + 1,     // deletion
                                d[i  , j-1] + 1,     // insertion
                                d[i-1, j-1] + cost   // substitution
                            )
           if(i > 1 and j > 1 and str1[i] = str2[j-1] and str1[i-1] = str2[j]) then
               d[i, j] := minimum(
                                d[i, j],
                                d[i-2, j-2] + cost   // transposition
                             )
                                
 
   return d[lenStr1, lenStr2]

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

           if(i > 1 and j > 1 and str1[i] = str2[j-1] and str1[i-1] = str2[j]) then
               d[i, j] := minimum(
                                d[i, j],
                                d[i-2, j-2] + cost   // transposition
                             )

Voir aussi

• Distance de Levenshtein

• Portail de l’informatique