Voir la source de Distance de Damerau-Levenshtein

En [[informatique théorique]], la '''distance de Damerau–Levenshtein''' est une distance entre deux [[Chaîne de caractères|chaînes de caractères]]. Elle porte les noms des chercheurs {{Lien|langue=en|trad=Frederick J. Damerau|fr=Frederick J. Damerau}} et [[Vladimir Levenshtein]], étant issue de leurs travaux sur les fautes d'orthographe courantes<ref name="bard">{{article |langue=en |titre=Spelling-Error Tolerant, Order-Independent Pass-Phrases via the Damerau-Levenshtein String-Edit Distance Metric |auteur=Gregory V. Bard |présentation en ligne=https://eprint.iacr.org/2006/364 |périodique=Proceedings of the fifth Australasian symposium on ACSW frontiers |date=janvier 2007 |passage=117-124}}.</ref>.

De manière informelle, l'évaluation de cette distance consiste à calculer 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, ou permutation, de deux caractères adjacents.

Frederick J. Damerau 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<ref>{{Article |langue=en |prénom1=Fred J. |nom1=Damerau |titre=A technique for computer detection and correction of spelling errors |périodique=Communications of the ACM |volume=7 |numéro=3 |date=1964-03-01 |doi=10.1145/363958.363994 |lire en ligne=http://portal.acm.org/citation.cfm?doid=363958.363994 |consulté le=2019-11-20 |pages=171–176 }}</ref>. 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. C'est donc la possibilité de transposition qui distingue la distance de Damerau–Levenshtein de la [[distance de Levenshtein]] classique<ref name="bard" />.

== Applications ==

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. Elle a également été utilisée pour effectuer de l'[[exploration de données]]/[[partitionnement de données]], comparer des [[paquet (réseau)|paquets de réseaux informatiques]], quantifier la similarité entre des [[Séquence (acide nucléique)|séquences d'ADN]], l'identification de gènes<ref>{{Article |langue=en |prénom1=Chunchun |nom1=Zhao |prénom2=Sartaj |nom2=Sahni |titre=String correction using the Damerau-Levenshtein distance |périodique=BMC Bioinformatics |volume=20 |numéro=11 |date=2019-06-06 |issn=1471-2105 |pmid=31167641 |pmcid=PMC6551241 |doi=10.1186/s12859-019-2819-0 |lire en ligne=https://doi.org/10.1186/s12859-019-2819-0 |consulté le=2023-01-18 |pages=277}}.</ref>.

== 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 ==
{{Références}}

== Voir aussi ==
* [[Distance de Levenshtein]]

{{Portail|Informatique théorique}}

[[Catégorie:Algorithme sur les chaînes de caractères]]