Distance de Damerau-Levenshtein
From Wikipedia, the free encyclopedia
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[1].
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[2]. 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[1].
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 paquets de réseaux informatiques, quantifier la similarité entre des séquences d'ADN, l'identification de gènes[3].
