À retenir
- Plus le score est bas, plus les mots se ressemblent.
- Un score de 0 indique que les chaînes de caractères sont identiques.
- Elle repose sur trois actions : insertion, suppression et substitution.
La distance de Levenshtein est un outil de mesure qui permet de chiffrer la différence entre deux textes. Elle calcule le nombre minimal de petits changements (ajouter, enlever ou remplacer une lettre) qu'il faut effectuer pour transformer un mot en un autre. C'est un peu comme mesurer l'effort nécessaire pour corriger une faute de frappe.
Étymologie
Le concept tire son nom du mathématicien russe Vladimir Levenshtein, qui l'a présenté en 1965. En informatique, on utilise aussi le terme plus générique de distance d'édition.
Exemples d'usage
- De
chatàchats: la distance est de 1 (on ajoute un 's'). - De
pommeàpomre: la distance est de 1 (on remplace le 'm' par un 'r'). - De
chienàniche: la distance est de 4 (plusieurs remplacements et déplacements sont nécessaires).
Cas d'usage
On retrouve ce concept partout où l'ordinateur doit interpréter l'imprécision humaine : les correcteurs orthographiques, les suggestions de recherche ("Vouliez-vous dire..."), la comparaison de fichiers de code, ou même en biologie pour comparer des brins d'ADN.
Bonnes pratiques
Attention à la performance : calculer cette distance sur des milliers de textes longs peut être gourmand en ressources. Pour des besoins spécifiques comme la phonétique (noms de famille), d'autres algorithmes complètent souvent Levenshtein pour mieux gérer les sons similaires.
Synonymes
Conseil
Si vous débutez en programmation, essayez d'implémenter cet algorithme manuellement (via la programmation dynamique) : c'est un excellent exercice pour comprendre comment optimiser des calculs complexes.
Questions fréquentes
Quelle est la différence avec la distance de Hamming ?
La distance de Hamming ne permet que de comparer des mots de même longueur en comptant les lettres différentes, alors que Levenshtein accepte des mots de tailles différentes en gérant les ajouts et retraits.
Est-ce que l'inversion de deux lettres compte pour 1 ?
Non, dans l'algorithme de base, inverser 'ab' en 'ba' compte pour 2 (un remplacement pour chaque lettre). Une variante nommée Damerau-Levenshtein permet de compter l'inversion comme une seule opération.