La distance de Levenshtein (LD) mesure la similarité entre deux chaînes de caractères. Elle est égale au nombre minimal de caractères qu’il faut supprimer, insérer, ou remplacer pour passer d’une chaîne à l’autre. Son nom provient de Vladimir Levenshtein qui l’a définie en 1965. (définition sur Wikipédia)
Par exemple, prenons les deux chaînes de caractères “couler” et “poulies” :
Pour passer de “couler” à “poulies”, il faut remplacer le “c” par un “p”, insérer un “i” avant le “e” et remplacer le “r” par un “s”.
Nous avons réalisé trois opérations, la distance de Levenshtein entre “couler” et “poulies” est donc de 3.
Pourquoi je vous parle de ça ? Parce que cet algorithme est très utilisé sur la plupart des sites que vous visitez chaque jour :
- Sur Mappy, lorsque vous orthographiez mal le nom d’une ville ou d’une rue, le site vous propose directement une liste de chaînes de caractères proches de celle que vous avez tapée. Cette liste est constituée d’un certain nombre de chaînes de caractères ayant une distance assez proche (inférieure à un seuil arbitraire) de la chaîne insérée.
- Sur le site allmusic, lorsque vous orthographiez mal le nom d’un artiste/groupe, le site propose une liste de noms proches ordonnés par relevance. Il s’agit typiquement d’une application de la distance de Levenshtein.
- Sur Google, lorsque vous orthographiez mal un terme de recherche (décidemment), on vous propose directement la correction. Il s’agit là d’une application légèrement différente de la distance de Levenshtein. Je suppose que Google regarde le terme le plus proche de celui qui a été inséré et, dans le cas où ce dernier possède beaucoup moins de résultats que son terme le plus proche, Google propose le fameux “Essayez avec cette orthographe : “
- etc.
Dans le monde actuel où une importante masse de la population ignore l’orthographe, la distance de Levenshtein sera votre amie dans le développement de votre application. Pensez-y !
Il en existe plusieurs implémentations (liste non exhaustive) :
Si votre langage de programmation préféré n’est pas représenté ci-dessus, vous pouvez toujours l’implémenter vous même à partir de l’algorithme.
Le blog de Vincent Battaglia 
Super ce billet… Très technique… Sur quel site en développement comptes-tu utiliser ce système afin que tes clients bénéficient de cette superbe opportunité ?
LikeLike
A vrai dire, je n’y avais pas encore vraiment pensé…
LikeLike
Hello Vinch
Pour Java, il y a l’implémentation de Jakarta dans les commons lang (jakarta.apache.org/common…)
Je l’ai utilisé pour faire la correspondance entre des adresse (de sociétés) entrées à la main et des adresses provenant d’un référentiel.
Dans le même genre, il y a l’algo des soundex qui se base sur la prononciation de deux mots pour déterminer leur distance (fr.wikipedia.org/wiki/Sou…). Utile pour corriger les fautes d’orthographe..
LikeLike
Hello Vinch !
Très intéressant ce billet !
Au sujet de ton exemple, je pense que la distance est de 3 entre "couler" et "poulies".
Tu transformes le ‘c’ en ‘p’, tu insères un ‘i’ avant le ‘e’ et tu remplaces le ‘r’ en ‘s’. Ce qui nous fait 3 opérations.
A bientôt,
Sélim
LikeLike
est si ces caractère soit des paires, comment on doit faire
LikeLike
Tu considères chaque caractère comme un caractère individuel. Même si ton mot comporte plusieurs “e”, chaque “e” est considéré comme un caractère à part entière. Tu ne peux donc pas dire : je remplace les deux “e” par deux “a” ce qui fait une opération. Tu dois remplacer le premier “e” par un “a” et le deuxième “e” par un “a” ce qui fait deux opérations.
LikeLike