Distance de Levenshtein

La distance de Levenshtein entre mots ou chaînes de caractères (distance d'édition, de similarité) donne par un calcul assez simple des indications sur le degré de ressemblance de ces chaînes. Sa définition est la suivante.

Si A, B sont deux mots, la distance de Levenshtein d est le nombre minimal de remplacements, ajouts et suppressions de lettres pour passer du mot A au mot B.
d satisfait bien à la définition des distances :
A, B et C étant trois mots quelconques (éventuellement vides),

1. d(A, B) est un réel positif ou nul
2. d(A, B) = 0 si et seulement si A = B
3. d(A, B) = d(B, A) (symétrie)
4. d(A, C) est inférieur ou égal à d(A, B) + d(B, C) (inégalité triangulaire)

On peut remarquer en outre que d(A, B) est un entier.

Exemple d'utilisation possible :
Lorsque vous recherchez le mot A dans un lexique L,
- soit A se trouve dans L : d(A, A) = 0
- soit A n'est pas dans L et vous suspectez une erreur d'écriture, en utilisant la distance de Levenshtein, vous pouvez rechercher les mots B de L les plus proches de A, tels que par exemple d(A, B) < k (k petit). L'un de ces mots sera peut-être la bonne orthographe de A.

Sur chaque ligne, inscrivez au choix

• deux mots séparés par un ou plusieurs espaces, une virgule ou un point virgule
• deux expressions ou deux parties de phrases séparées par une virgule ou par un point virgule.

(Les espaces qui se trouvent au début ou à la fin des phrases seront ignorés, les espaces multiples seront réduits).

  

mots mois janvier février textes textos machins machine méchant machine distance instance adroit gauche tiède chaud liens links un peu, beaucoup deux fois, trois fois le lapin, la lapine les malins, la maligne un, deux, trois ; deux, trois, quatre

Le code javascript de l'algorithme utilisé est indiqué ci-dessous,

function distance(a, b) {
        var n = a.length, m = b.length, matrice = [];
        for(var i=-1; i < n; i++) {
                matrice[i]=[];
                matrice[i][-1]=i+1;
        }
        for(var j=-1; j < m; j++) {
                matrice[-1][j]=j+1;
        }
        for(var i=0; i < n; i++) {
                for(var j=0; j < m; j++) {
                        var cout = (a.charAt(i) == b.charAt(j))? 0 : 1;
                        matrice[i][j] = minimum(1+matrice[i][j-1], 1+matrice[i-1][j], cout+matrice[i-1][j-1]);
                }
        }
        return matrice[n-1][m-1];
}
// la fonction minimum() est à définir !

L'application ci-dessous vous donne le détail de la matrice n×m calculée avant de déterminer la distance entre les deux mots.
Les deux mots étudiés sont écrits (en rouge) dans la colonne de gauche et sur la première ligne du tableau.
Ensuite les entiers 0, 1, 2 ... sont écrits (en vert) dans la seconde colonne et sur la seconde ligne.
Tous les nombres restants sont ceux de la matrice n×m (écrits en noir ou en bleu plour le résultat).

Appuyez sur la touche [au hasard] ou écrivez deux mots de votre choix, séparés par des espaces puis [faites afficher la matrice] calculée par l'algorithme.
La distance entre les deux mots et calculée par l'algorithme, se trouvera dans la case en bas, à droite.
Chaque élément (écrit en noir ou en bleu) de la matrice est le plus petit des trois nombres suivants :

• 1 + le nombre à sa gauche
• 1 + le nombre au-dessus de lui
• le nombre en haut à gauche (en diagonale) +
  • 0 si les lettres à gauche et en haut sont identiques
  • 1 si ces lettres sont différentes

1. Lorsque l'algorithme le permet, les transitions sont choisies aléatoirement.
   (Recalculer la matrice permet parfois d'obtenir une autre solution).
2. Promenez la souris sur les cases du tableau pour connaître le détail des calculs effectués.
3. Retrouvez comment le chemin colorié en vert dans le tableau nous apprend qu'il faut ajouter ou supprimer, modifier une lettre ou la laisser inchangée.

Écrivez un mot de votre choix et l'application le recherchera dans "Le discours de la méthode" de Descartes.
Discours de la méthode pour bien conduire sa raison et chercher, de René Descartes (1596-1650) est publié en français le 8 juin 1637 à La Haye.

Si votre mot n'est pas trouvé, les mots les plus proches seront affichés.
(Seuls sont recherchés les mots de trois lettres ou plus du texte).