Distance de Levenshtein

(on dit aussi distance d'édition) Nombre positif mesurant la similarité entre deux chaines de caractères. Le distance de Levenshtein est égale au plus petit nombre de caractères qu'il faut supprimer, insérer ou remplacer pour passer d'une chaine à l'autre.

Cette distance est nulle si les chaînes sont identiques et c'est une distance au sens mathématique du terme..

Définie en 1965 par Vladimir Levenshtein, la distance de Levenshtein peut être considérée comme une généralisation de la distance de Hamming. La distance de Hamming est un majorant de la distance de Levenshtein.