Hello, I’m Vinch

And this is my website.

La distance de Levenshtein

10/03/06

This post is more than 11 years old. It might not reflect my current skills and convictions.

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.

6 comments

Leave a comment