Distance de Levenshtein

La 'distance de Levenshtein' est une distance, au sens mathématique du terme, donnant une mesure de la différence entre deux chaînes de caractères. Elle est égale au nombre minimal de caractères qu'il faut supprimer, insérer ou remplacer pour passer d’une chaîne à l’autre. Elle a été proposée par Vladimir Levenshtein en 1965. Elle est également connue sous les noms de distance d'édition ou de déformation dynamique temporelle, notamment en reconnaissance de formes et particulièrement en reconnaissance vocale. Cette distance est d'autant plus grande que le nombre de différences entre les deux chaînes est grand. La distance de Levenshtein peut être considérée comme une généralisation de la distance de Hamming. On peut montrer en particulier que la distance de Hamming est un majorant de la distance de Levenshtein. On appelle distance de Levenshtein entre deux chaînes M et P le coût minimal pour transformer M en P en effectuant les seules opérations élémentaires (au niveau d'un caractère) suivantes (on agit exclusivement sur M et successivement sur ses transformés) : substitution ; insertion (ou ajout) ; suppression (ou effacement). Formellement, on définit cette distance, avec deux chaînes et , le cardinal de (ou son nombre de lettres), et la chaîne tronquée de sa lettre : On associe à chacune de ces opérations un coût. Généralement, le coût est égal à 1 pour les trois opérations. La distance est la somme des coûts des opérations effectuées. On peut montrer que définir une distance au sens mathématique du terme entre les caractères d'un alphabet, entraine que la distance de Levenshtein soit aussi une distance au sens mathématique du terme, sur l'ensemble des chaines construites sur l'alphabet. Si M = « examen » et P = « examen », alors , parce qu'aucune opération n'a été réalisée. Si M = « examen » et P = « examan », alors , parce qu’il y a eu une substitution (changement du e en a), et que l'on ne peut pas en faire moins. L’algorithme ci-dessous, dû à Wagner et Fischer (1974), permet de calculer la distance de Levenshtein entre deux chaînes de caractères courtes.