Distance de Damerau-Levenshtein

Carte Commune · n° 364725

En informatique théorique, la distance de Damerau–Levenshtein est une distance entre deux chaînes de caractères. Elle porte les noms des chercheurs Frederick J. Damerau (en) et Vladimir Levenshtein, étant issue de leurs travaux sur les fautes d'orthographe courantes. 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. 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...

Lire sur Wikipédia