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.
Objectif
Quantifier le degré de différence entre chaînes, utilisé pour l'appariement flou et la correction d'erreurs.
Mécanisme
Cadre général : définir l'ensemble d'opérations permises et leurs coûts, puis trouver le coût total minimal par programmation dynamique. Levenshtein permet insertion/suppression/substitution (coût 1 chacune) ; Damerau-Levenshtein ajoute la transposition de caractères adjacents ; Hamming ne permet que la substitution.
Cas d’usage
- Correction orthographique
- Alignement de séquences ADN
- Correction d'erreurs OCR
- Déduplication floue
Exemples
- entrée
cat → cutOutput1 (substituting a→u)Levenshtein
Erreurs courantes
- Confusing different edit-distance variants
- Make the operation set and costs explicit
Termes associés
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. GLOSSAIRE
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
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