Distance de Levenshtein

Carte Peu commune · n° 76620

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. 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. 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. 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.

Lire sur Wikipédia