Distance de Levenshtein

La distance de Levenshtein est une distance entre deux chaînes de caractères. Elle est définie comme le nombre minimal d'opérations élémentaires nécessaires pour transformer une chaîne en une autre lorsque les opérations autorisées sont l'insertion, la suppression et la substitution d'un symbole^[1].

Elle porte le nom du mathématicien soviétique Vladimir Levenshtein, qui l'a introduite dans ses travaux de 1965 sur les codes correcteurs d'insertions et de suppressions^[1]. La distance de Levenshtein est un cas classique de distance d'édition (edit distance). Le terme « distance d'édition » peut toutefois désigner une famille plus large de mesures dans lesquelles l'ensemble des opérations autorisées ou leurs coûts diffèrent^[2].

Pour deux chaînes de même longueur, la distance de Hamming est un majorant de la distance de Levenshtein, puisqu'une transformation peut toujours être réalisée en substituant chaque symbole différent^[2].

Définition

Soient deux chaînes $a=a_{1}a_{2}\dots a_{m}$ et $b=b_{1}b_{2}\dots b_{n}$ . On note $D(i,j)$ la distance de Levenshtein entre le préfixe $a_{1}\dots a_{i}$ et le préfixe $b_{1}\dots b_{j}$ .

Les conditions initiales sont

D(i,0)=i,\qquad D(0,j)=j.

Pour $i>0$ et $j>0$ ,

D(i,j)=\min {\begin{cases}D(i-1,j)+1,\\D(i,j-1)+1,\\D(i-1,j-1)+\delta (a_{i},b_{j}),\end{cases}}

où

\delta (a_{i},b_{j})={\begin{cases}0,&{\text{si }}a_{i}=b_{j},\\1,&{\text{sinon.}}\end{cases}}

Les trois termes correspondent respectivement à une suppression dans la chaîne source, une insertion du symbole cible et une substitution — ou à l'absence de modification lorsque les deux symboles sont égaux^[3].

Dans la définition classique, chacune des trois opérations a un coût égal à 1. Lorsque les coûts dépendent de l'opération ou des symboles concernés, on obtient une distance d'édition pondérée ; selon la fonction de coût choisie, les propriétés d'une distance au sens mathématique ne sont pas nécessairement toutes conservées^[2].

Propriétés

Avec des coûts unitaires, la distance de Levenshtein est une distance au sens mathématique sur l'ensemble des chaînes : elle est positive ou nulle, symétrique, nulle si et seulement si les deux chaînes sont égales et satisfait l'inégalité triangulaire^[2].

Pour deux chaînes $a$ et $b$ de longueurs respectives $m$ et $n$ ,

|m-n|\leq \operatorname {lev} (a,b)\leq \max(m,n).

La borne inférieure vient du fait qu'une insertion ou une suppression ne modifie la longueur que d'une unité. La borne supérieure peut être atteinte en substituant les symboles de la partie commune puis en insérant ou supprimant les symboles restants.

Si les deux chaînes ont la même longueur, alors

\operatorname {lev} (a,b)\leq d_{H}(a,b),

où $d_{H}$ désigne la distance de Hamming.

Lorsque seules les insertions et les suppressions sont autorisées, le coût minimal entre deux chaînes de longueurs $m$ et $n$ s'écrit

m+n-2L,

où $L$ est la longueur d'une plus longue sous-séquence commune. Cette égalité ne s'applique pas telle quelle à la distance de Levenshtein classique, car une substitution y coûte 1 au lieu d'une suppression suivie d'une insertion^[3].

Exemples

Si ${\displaystyle M={\text{«$ et ${\displaystyle P={\text{«$ , alors $\operatorname {lev} (M,P)=0$ .

Si ${\displaystyle M={\text{«$ et ${\displaystyle P={\text{«$ , alors $\operatorname {lev} (M,P)=1$ , car une seule substitution suffit.

Un exemple classique est la transformation de kitten en sitting, dont la distance vaut 3 :

kitten → sitten : substitution de k par s ;
sitten → sittin : substitution de e par i ;
sittin → sitting : insertion de g.

Calcul

Algorithme de Wagner-Fischer

L'algorithme de Wagner-Fischer calcule la distance de Levenshtein par programmation dynamique. Il remplit une matrice de taille $(m+1)\times (n+1)$ dont chaque case contient la distance entre deux préfixes^[3].

fonction DistanceDeLevenshtein(chaine1[1..m], chaine2[1..n]):
    déclarer D[0..m, 0..n]

    pour i de 0 à m:
        D[i, 0] = i

    pour j de 0 à n:
        D[0, j] = j

    pour i de 1 à m:
        pour j de 1 à n:
            si chaine1[i] = chaine2[j]:
                coûtSubstitution = 0
            sinon:
                coûtSubstitution = 1

            D[i, j] = minimum(
                D[i-1, j]   + 1,                 // suppression de chaine1[i]
                D[i, j-1]   + 1,                 // insertion de chaine2[j]
                D[i-1, j-1] + coûtSubstitution   // conservation ou substitution
            )

    renvoyer D[m, n]

L'invariant est que D[i,j] contient le coût minimal pour transformer chaine1[1..i] en chaine2[1..j]. La réponse est donc la valeur D[m,n].

Complexité et mémoire

Le calcul direct de la matrice demande un temps $\Theta (mn)$ et, si la matrice entière est conservée, un espace $\Theta (mn)$ ^[3].

Si seule la valeur de la distance est nécessaire, chaque nouvelle ligne ne dépend que de la ligne précédente et de la ligne en cours. L'espace peut alors être réduit à $O(\min(m,n))$ en choisissant la chaîne la plus courte comme dimension stockée^[4].

Si l'on veut reconstruire une suite optimale d'opérations, on peut remonter dans la matrice depuis D[m,n]. Plusieurs chemins optimaux peuvent exister : la valeur de la distance peut donc être unique alors que la suite minimale d'opérations ne l'est pas.

Algorithmes sensibles à la distance et parallélisme de bits

Lorsque la distance réelle $s$ est petite par rapport à la longueur des chaînes, il n'est pas toujours nécessaire de remplir la matrice entière. Ukkonen a donné des algorithmes exacts dont le temps dépend de $s$ ; l'un de ses résultats atteint $O(s\min(m,n))$ en temps et en espace^[4].

Pour la recherche approximative d'un motif dans un texte, Gene Myers a proposé en 1999 un algorithme bit-vector qui représente plusieurs états de programmation dynamique dans les bits d'un mot machine et accélère ainsi de nombreux calculs de distance d'édition^[5].

Les algorithmes O(ND) de Myers (1986) et O(NP) de Wu, Manber, Myers et Miller (1990), parfois rapprochés de la distance de Levenshtein, traitent quant à eux le problème du plus court script d'édition composé d'insertions et de suppressions. Dans ce modèle, une substitution équivaut à une suppression suivie d'une insertion et coûte donc 2 ; ces résultats ne doivent pas être confondus avec la distance de Levenshtein classique à substitution de coût 1^[6].

Bornes de complexité et approximation

Pour deux chaînes de longueur $n$ , l'algorithme classique est quadratique. Backurs et Indyk ont montré qu'un algorithme exact en temps $O(n^{2-\delta })$ , pour une constante $\delta >0$ , contredirait l'hypothèse forte du temps exponentiel (SETH). Ce résultat constitue une borne inférieure conditionnelle importante pour le problème général^[7].

Des algorithmes plus rapides sont possibles lorsque l'on accepte une approximation. Andoni, Krauthgamer et Onak ont donné en 2010 une approximation polylogarithmique en temps $n^{1+\varepsilon }$ pour tout $\varepsilon >0$ fixé^[8]. En 2020, Andoni et Nosatzki ont obtenu, dans le même régime de temps $n^{1+\varepsilon }$ , une approximation à facteur constant^[9].

Applications

Recherche approximative et correction orthographique

La distance de Levenshtein est l'une des mesures fondamentales de la recherche approximative de chaînes. Elle intervient notamment dans la correction orthographique, la recherche tolérant les fautes de frappe, l'appariement de noms et le rapprochement de données textuelles^[2].

Dans les grandes collections, la distance n'est généralement pas calculée entre la requête et toutes les chaînes du corpus. Des techniques de filtrage, d'indexation, de q-grammes ou d'automates réduisent d'abord le nombre de candidats à comparer^[2].

Reconnaissance de texte et de la parole

Dans l'évaluation de la reconnaissance de texte, une distance d'édition calculée au niveau des caractères peut être normalisée pour obtenir un taux d'erreur caractère. Le NIST utilise également des mesures fondées sur les insertions, suppressions et substitutions pour l'évaluation de la reconnaissance automatique de la parole ; le taux d'erreur de mots (word error rate, WER) s'écrit

\mathrm {WER} ={\frac {S+D+I}{N}},

où $S$ , $D$ et $I$ désignent respectivement les substitutions, suppressions et insertions, et $N$ le nombre de mots de la transcription de référence^[10].

Linguistique et dialectologie

En dialectologie quantitative, la distance de Levenshtein peut être appliquée à des transcriptions phonétiques pour mesurer les différences de prononciation entre variétés linguistiques. Wilbert Heeringa en a étudié systématiquement l'emploi dans sa thèse consacrée aux différences de prononciation dialectale^[11].

Bio-informatique

La distance d'édition et l'alignement de séquences sont étroitement liés en bio-informatique. Les insertions, suppressions et substitutions fournissent un modèle simple des différences entre séquences biologiques, même si les méthodes d'alignement utilisées en pratique emploient souvent des fonctions de score et des pénalités de gap plus riches que la distance de Levenshtein unitaire^[12].

Unicode et unité de comparaison

La définition mathématique s'applique à une suite de symboles, mais une implémentation informatique doit préciser ce qu'elle considère comme un symbole. Dans un texte Unicode, le calcul peut être effectué sur des octets, des unités de code, des points de code ou des groupes de graphèmes ; ces choix peuvent conduire à des distances différentes.

L'annexe Unicode Standard Annex #29 définit les extended grapheme clusters, conçus comme une approximation algorithmique des caractères perçus par l'utilisateur^[13].

En outre, deux textes équivalents peuvent être représentés par des suites de points de code différentes. Unicode Standard Annex #15 définit les formes de normalisation NFC, NFD, NFKC et NFKD^[14]. Le choix de la segmentation et de la normalisation fait donc partie de la définition pratique de l'entrée lorsque la distance est calculée sur du texte Unicode.

Généralisation et autres distances

En remplaçant les chaînes de caractères par des séquences de symboles munies d'un opérateur d'égalité, la même construction s'applique à d'autres types de séquences.

Parmi les distances d'édition apparentées figurent :

la distance de Damerau-Levenshtein, qui ajoute la transposition de deux symboles adjacents ;
la distance de Hamming, limitée aux substitutions et aux chaînes de même longueur ;
la distance d'édition sur les arbres, qui généralise l'idée d'opérations d'édition aux structures arborescentes.

D'autres mesures de similarité entre chaînes, comme la distance de Jaro-Winkler ou la distance de Jaccard, ne sont pas des généralisations directes de la distance de Levenshtein : elles reposent sur d'autres modèles de comparaison.

Historique

Levenshtein a publié en 1965 son article sur les codes binaires capables de corriger des suppressions, insertions et changements de symboles^[1]. Les travaux sur la comparaison de chaînes par programmation dynamique ont ensuite été développés indépendamment dans plusieurs branches de l'informatique. L'article de Wagner et Fischer de 1974 a fourni une formulation générale du problème de correction d'une chaîne en une autre et constitue une présentation classique de l'algorithme quadratique^[3]^,^[12].

Des travaux ultérieurs ont développé des algorithmes sensibles à la distance, des méthodes bit-parallel, des automates de Levenshtein, des approximations et des résultats de complexité conditionnelle^[4]^,^[5]^,^[7].

Notes et références

1 2 3 V. I. Levenshtein, « Binary codes capable of correcting deletions, insertions, and reversals », Doklady Akademii Nauk SSSR, vol. 163, no 4, 1965, p. 845–848. Notice Math-Net. Une traduction anglaise est parue dans Soviet Physics Doklady, vol. 10, no 8, 1966, p. 707–710.
1 2 3 4 5 6 Gonzalo Navarro, « A guided tour to approximate string matching », ACM Computing Surveys, vol. 33, no 1, 2001, p. 31–88, doi:10.1145/375360.375365.
1 2 3 4 5 Robert A. Wagner et Michael J. Fischer, « The String-to-String Correction Problem », Journal of the ACM, vol. 21, no 1, 1974, p. 168–173, doi:10.1145/321796.321811.
1 2 3 Esko Ukkonen, « Algorithms for approximate string matching », Information and Control, vol. 64, nos 1–3, 1985, p. 100–118, doi:10.1016/S0019-9958(85)80046-2.
1 2 Gene Myers, « A fast bit-vector algorithm for approximate string matching based on dynamic programming », Journal of the ACM, vol. 46, no 3, 1999, p. 395–415, doi:10.1145/316542.316550.
↑ Sun Wu, Udi Manber, Gene Myers et Webb Miller, « An O(NP) sequence comparison algorithm », Information Processing Letters, vol. 35, no 6, 1990, p. 317–323, doi:10.1016/0020-0190(90)90035-V.
1 2 Arturs Backurs et Piotr Indyk, « Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false) », Proceedings of the 47th Annual ACM Symposium on Theory of Computing, 2015, p. 51–58, doi:10.1145/2746539.2746612.
↑ Alexandr Andoni, Robert Krauthgamer et Krzysztof Onak, « Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity », 51st IEEE Symposium on Foundations of Computer Science, 2010, p. 377–386, doi:10.1109/FOCS.2010.43.
↑ Alexandr Andoni et Negev Shekel Nosatzki, « Edit Distance in Near-Linear Time: it's a Constant Factor », IEEE Symposium on Foundations of Computer Science, 2020, p. 990–1001, doi:10.1109/FOCS46700.2020.00096.
↑ National Institute of Standards and Technology, NIST Special Publication 1112, description de la métrique WER fondée sur l'edit distance. Document NIST.
↑ Wilbert J. Heeringa, Measuring Dialect Pronunciation Differences using Levenshtein Distance, thèse de doctorat, University of Groningen, 2004. Notice de l'University of Groningen.
1 2 Bonnie Berger, Michael S. Waterman et Yun William Yu, « Levenshtein Distance, Sequence Comparison and Biological Database Search », IEEE Transactions on Information Theory, vol. 67, no 6, 2021, p. 3287–3294, doi:10.1109/TIT.2020.2996543.
↑ Unicode Consortium, « Unicode Standard Annex #29: Unicode Text Segmentation ». unicode.org.
↑ Unicode Consortium, « Unicode Standard Annex #15: Unicode Normalization Forms ». unicode.org.

Voir aussi

Articles connexes

Liens externes

Levenshtein distance — Dictionary of Algorithms and Data Structures, National Institute of Standards and Technology (NIST).
(en) Algorithm Implementation/Strings/Levenshtein distance, sur Wikibooks en anglais — implémentations en plusieurs langages de programmation.
Levenshtein.net — ressource consacrée à la distance de Levenshtein, à ses algorithmes, à son histoire et à ses applications.

Portail de l'informatique théorique

Portail des mathématiques

[lev1965-1] 1 2 3 V. I. Levenshtein, « Binary codes capable of correcting deletions, insertions, and reversals », Doklady Akademii Nauk SSSR, vol. 163, no 4, 1965, p. 845–848. Notice Math-Net. Une traduction anglaise est parue dans Soviet Physics Doklady, vol. 10, no 8, 1966, p. 707–710.

[navarro-2] 1 2 3 4 5 6 Gonzalo Navarro, « A guided tour to approximate string matching », ACM Computing Surveys, vol. 33, no 1, 2001, p. 31–88, doi:10.1145/375360.375365.

[wagner-3] 1 2 3 4 5 Robert A. Wagner et Michael J. Fischer, « The String-to-String Correction Problem », Journal of the ACM, vol. 21, no 1, 1974, p. 168–173, doi:10.1145/321796.321811.

[ukkonen-4] 1 2 3 Esko Ukkonen, « Algorithms for approximate string matching », Information and Control, vol. 64, nos 1–3, 1985, p. 100–118, doi:10.1016/S0019-9958(85)80046-2.

[myers1999-5] 1 2 Gene Myers, « A fast bit-vector algorithm for approximate string matching based on dynamic programming », Journal of the ACM, vol. 46, no 3, 1999, p. 395–415, doi:10.1145/316542.316550.

[6] Sun Wu, Udi Manber, Gene Myers et Webb Miller, « An O(NP) sequence comparison algorithm », Information Processing Letters, vol. 35, no 6, 1990, p. 317–323, doi:10.1016/0020-0190(90)90035-V.

[backurs-7] 1 2 Arturs Backurs et Piotr Indyk, « Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false) », Proceedings of the 47th Annual ACM Symposium on Theory of Computing, 2015, p. 51–58, doi:10.1145/2746539.2746612.

[8] Alexandr Andoni, Robert Krauthgamer et Krzysztof Onak, « Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity », 51st IEEE Symposium on Foundations of Computer Science, 2010, p. 377–386, doi:10.1109/FOCS.2010.43.

[9] Alexandr Andoni et Negev Shekel Nosatzki, « Edit Distance in Near-Linear Time: it's a Constant Factor », IEEE Symposium on Foundations of Computer Science, 2020, p. 990–1001, doi:10.1109/FOCS46700.2020.00096.

[10] National Institute of Standards and Technology, NIST Special Publication 1112, description de la métrique WER fondée sur l'edit distance. Document NIST.

[11] Wilbert J. Heeringa, Measuring Dialect Pronunciation Differences using Levenshtein Distance, thèse de doctorat, University of Groningen, 2004. Notice de l'University of Groningen.

[berger-12] 1 2 Bonnie Berger, Michael S. Waterman et Yun William Yu, « Levenshtein Distance, Sequence Comparison and Biological Database Search », IEEE Transactions on Information Theory, vol. 67, no 6, 2021, p. 3287–3294, doi:10.1109/TIT.2020.2996543.

[uax29-13] Unicode Consortium, « Unicode Standard Annex #29: Unicode Text Segmentation ». unicode.org.

[uax15-14] Unicode Consortium, « Unicode Standard Annex #15: Unicode Normalization Forms ». unicode.org.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]