Accueil / Langages informatiques / Algorithmes / Distance de Levenshtein

Distance de Levenshtein

Description

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.

Exemples

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).

  

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 !

Détail des calculs sur des exemples

Travail préparatoire avant les calculs

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).

Vérifiez les calculs

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

Le tableau des calculs

  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.


Recherches dans un texte

Le discours de la méthode

É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).


Autres textes

Si vous préférez effectuer les recherches dans un autre texte, copiez votre propre document ci-dessous et enregistrez-le (il prendra alors la place du "discours de la méthode"). Vous trouverez sur le site de l'ABU des textes complets d'ouvrages littéraires. Choisissez le texte complet (non formaté). Dans votre navigateur sélectionnez tout le texte, collez-le ensuite ci-dessous (faites un simple copier-coller de tout un bouquin) ! N'oubliez pas de l'enregistrer ensuite.




Documents, références, liens

Levenshtein Distance, in Three Flavors   by Michael Gilleland, Merriam Park Software
The purpose of this short essay is to describe the Levenshtein distance algorithm and show how it can be implemented in three different programming languages. (Java, C++, Visual Basic).
Wikipédia Distance de Levenshtein et Algorithm implementation en anglais  
Levenshtein   This demo by Peter Kleiweg.
Dictionary of Algorithms and Data Structures   NIST This is a dictionary of algorithms, algorithmic techniques, data structures, archetypal problems, and related definitions. Levenshtein distance (definition).
Pictures from the Director's Reception at the ZiF on March 4, 2003   (with Vladimir Levenshtein)
Catalogue des Textes   ABU : la Bibliothèque Universelle
descartes.free.fr   Jean Strajnic
Wikipédia Discours de la méthode   
Discours de la Méthode   Académie de Nice Philosophie
SecondString Project Page   
Edit distance algorithm visualization   Hannes Planatscher
















Pour un premier contact, [utilisez ce formulaire] ou utilisez l'adresse de messagerie qui y figure. Merci d'indiquer la page précise du site "http//jm.davalan.org/...", cela m'aidera beaucoup. Ne joignez aucun document à votre message.
Jeux-et-Mathématiques n'est pas un site commercial. Aucun des liens placés sur ce site n'est rémunéré, ni non plus aucune des informations données.
Important : Si votre question a un quelconque rapport avec un travail personnel (Devoir TIPE Master...) , vous devez absolument me le préciser dès votre premier message et m'indiquer très précisément les limites des informations demandées. Vous devez aussi avertir la personne qui dirige éventuellement votre travail ou le corrige de cette communication et lui montrer les documents fournis.

J'essaie de répondre aux questions posées, mais ne lis pas les documents mathématiques amateurs, pas plus que je ne donne mon avis sur les démonstrations des conjectures de Collatz ou autres. Je ne lis pas les documents word, je ne corrige pas les programmes informatiques et depuis des années je n'utilise plus de tableur.

© (Copyright) Jean-Paul Davalan 2002-2014