Levenshtein Distance
La distance de Levenshtein est le nombre minimal d'insertions, de suppressions et de substitutions d'un seul caractère nécessaires pour rendre deux chaînes identiques.
Objectif
Mesure la différence d'édition entre chaînes ; utilisée pour l'appariement approximatif et la correction orthographique.
Mécanisme
Programmation dynamique : d[i][j] = min(d[i-1][j]+1, d[i][j-1]+1, d[i-1][j-1]+coût), où le coût vaut 0 si les caractères concordent et 1 sinon. Temps et espace en O(m×n) ; l'espace peut être optimisé à O(min(m,n)).
Cas d’usage
- Correction orthographique
- Alignement de séquences d'ADN
- Recherche floue et déduplication
- Traitement automatique du langage
Exemples
- entrée
kitten → sittingOutput3Substitute k→s, e→i, and insert g
Erreurs courantes
- Full O(mn) computation is too slow for long strings
- Use a BK-tree or early termination by threshold
Termes associés
Hamming Distance
La distance de Hamming est le nombre de positions où diffèrent les caractères correspondants entre deux chaînes de même longueur ; elle ne s'applique qu'aux comparaisons de même longueur. GLOSSAIRE
Jaro-Winkler Distance
La distance de Jaro-Winkler est un raffinement de la distance de Jaro qui pondère les préfixes communs, la rendant plus adaptée à l'appariement de chaînes courtes comme les noms de personne où le préfixe compte. GLOSSAIRE
Edit Distance
La distance d'édition est le nombre minimal d'opérations d'édition d'un seul caractère (insertion, suppression, substitution) nécessaires pour transformer une chaîne en une autre ; la distance de Levenshtein en est la forme la plus courante. GLOSSAIRE
Fuzzy Search
La recherche approximative (fuzzy search) est une technique de recherche tolérante aux variantes orthographiques, qui fait correspondre des résultats approchés sur la base de la distance d'édition, des n-grammes ou d'algorithmes phonétiques. GLOSSAIRE