<page> <title>Distance de Levenshtein</title> <id>156572</id> <revision> <id>31796468</id> <timestamp>2008-07-22T17:22:38Z</timestamp> <contributor> <username>Zorrobot</username> <id>179160</id> </contributor> <minor /> <comment>robot Ajoute: [[vi:Khoảng cách Levenshtein]]</comment> <text xml:space="preserve">{{ébauche|informatique}} La '''distance de Levenshtein''' [[Mesure (mathématiques)|mesure]] la similarité entre deux [[chaîne de caractères|chaînes de caractères]].<br /> 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]].<br /> Elle est aussi connue sous le nom de '''distance d'édition''' ou encore de '''déformation dynamique temporelle''', notamment en [[Reconnaissance vocale|reconnaissance de la parole]]. Cette distance est d'autant plus grande que le nombre de différences entre les deux chaînes est grand. La distance de Levenshtein peut être considérée comme une généralisation de la [[distance de Hamming]]. On peut montrer en particulier que la distance de Hamming est un [[majorant]] de la distance de Levenshtein. == Définition == On appelle distance de Levenshtein entre deux mots M et P le coût minimal pour aller de M à P en effectuant les opérations élémentaires suivantes: * substitution d'un caractère de M en un caractère de P. * ajout dans M d'un caractère de P. * suppression d'un caractère de M. On associe ainsi à chacune de ces opérations un coût. Par exemple, dans les exemples suivants, le coût est toujours égal à 1, sauf dans le cas d'une substitution de caractères identiques. == Exemples == Si M = « examen » et P = « examen », alors LD (M, P) = 0, parce qu'aucune opération n'a été réalisée. Si M = « exam'''e'''n » et P = « exam'''a'''n », alors LD (M, P) = 1, parce qu’il y a eu un remplacement (changement du ''e'' en ''a''). == Algorithme de Levenshtein == L'algorithme ci-dessous permet de calculer la distance de Levenshtein entre deux chaines de caractères courtes. Pour des chaînes de caractères plus longues (plusieurs mots) il faut utiliser les algorithmes de Jaccard ou TF/IDF par exemple. L'algorithme de Levenshtein est un algorithme de [[programmation dynamique]] (solution de type du bas en haut), qui utilise une matrice de dimension (<var>n</var> + 1) × (<var>m</var> + 1) où <var>n</var> et <var>m</var> sont les dimensions des deux chaînes de caractères. Dans le [[pseudo-code]] suivant, la chaîne ''chaine1'' est de longueur ''longueurChaine1'' et ''chaine2'', de longueur ''longueurChaine2''. Cet algorithme renvoie un entier positif ou nul. Il renvoie 0 si les chaînes 1 et 2 sont égales. Si les chaînes 1 et 2 sont très différentes, la fonction renverra au maximum la plus grande longueur des deux chaînes. '''entier''' DistanceDeLevenshtein('''caractere''' chaine1[1..longueurChaine1], '''caractere''' chaine2[1..longueurChaine2]) ''// d est un tableau de longueurChaine1+1 rangées et longueurChaine2+1 colonnes'' '''declarer''' '''entier''' d[0..longueurChaine1, 0..longueurChaine2] ''// i et j itèrent sur chaine1 et chaine2'' '''declarer''' '''entier''' i, j, coût '''pour''' i '''de''' 0 '''à ''' longueurChaine1 d[i, 0] := i '''pour''' j '''de''' 0 '''à ''' longueurChaine2 d[0, j] := j '''pour''' i '''de''' 1 '''à ''' longueurChaine1 '''pour''' j '''de''' 1 '''à ''' longueurChaine2 '''si''' chaine1[i] = chaine2[j] '''alors''' coût := 0 '''sinon''' coût := 1 d[i, j] := minimum( d[i-1, j ] + 1, ''// effacement'' d[i , j-1] + 1, ''// insertion'' d[i-1, j-1] + coût ''// substitution'' ) '''retourner''' d[longueurChaine1, longueurChaine2] L'[[invariant]] est qu'on peut transformer le segment initial <code>chaine1[1..i]</code> en <code>chaine2[1..j]</code> en utilisant un nombre minimal de <code>d[i, j]</code> opérations. L'algorithme achevé, la solution est contenue dans la dernière position à droite de la rangée du bas de la matrice. ===Améliorations possibles=== L'algorithme présenté a une complexité temporelle et spatiale de <math>(m+1)\times(n+1)</math>. En effet, il faut stocker et remplir la matrice en mémoire. Cependant, il est possible d'effectuer le calcul en ne gardant qu'une ligne et qu'une colonne en mémoire, ce qui réduit grandement la quantité de mémoire utilisée à <math>O(m)</math>. D'autre part, il est aussi possible d'expliciter la suite d'opérations réellement effectuée par l'algorithme en utilisant une deuxième matrice où l'on stocke pour chaque opération, l'opération parente. Une fois le calcul effectué, on peut reconstruire la chaîne en suivant cette matrice depuis sa fin. Ce processus permet par exemple d'apparier les caractères de a avec ceux de b. ===Implémentations=== Plusieurs implémentations sont disponibles : [[:b:en:Algorithm implementation/Strings/Levenshtein distance|Levenshtein distance]]. == Exemple de déroulement de l'algorithme == Pour comprendre le fonctionnement de cet [[Algorithmique|algorithme]], prenons un exemple: Soit s= « NICHE » Soit t= « CHIENS » === Intuitivement === Intuitivement, on voit bien que l'on peut transformer la chaîne s en t en 5 étapes: * Suppression de N et I * Ajout de I, N et S -> CHIENS La distance de Levenshtein d entre "NICHE" et "CHIENS" est donc de 5 (l'algorithme de la distance de Levenshtein ne s'occupe pas de déplacement, il ne sait détecter que la suppression ou l'insertion d'une lettre, ainsi que le remplacement d'une lettre par une autre). === Fonctionnement === Soit n la longueur de la chaîne s (ici n=5)<br /> Soit m la longueur de la chaîne t (ici m=6) Si n=0 alors retourner d=m et quitter<br /> Si m=0 alors retourner d=n et quitter Construire une matrice M de n+1 lignes et m+1 colonnes.<br /> Initialiser de la première ligne par la matrice ligne [ 0,1,….., m-1, m] et la première colonne par la matrice colonne [ 0,1,….., n-1, n] {|class="wikitable" ! !! !! C !! H !! I !! E !! N !! S |- | || 0 || 1 || 2 || 3 || 4 || 5 || 6 |- ! N | 1 || 0 || 0 || 0 || 0 || 0 || 0 |- ! I | 2 || 0 || 0 || 0 || 0 || 0 || 0 |- ! C | 3 || 0 || 0 || 0 || 0 || 0 || 0 |- ! H | 4 || 0 || 0 || 0 || 0 || 0 || 0 |- ! E | 5 || 0 || 0 || 0 || 0 || 0 || 0 |} Soit Cout(i, j)=0 si A(i)=B(j) et Cout(i, j)=1 si A(i)!=B(j)<br /> On a donc ici la matrice Cout: {|class="wikitable" ! !! C !! H !! I !! E !! N !! S |- ! N | 1 || 1 || 1 || 1 || 0 || 1 |- ! I | 1 || 1 || 0 || 1 || 1 || 1 |- ! C | 0 || 1 || 1 || 1 || 1 || 1 |- ! H | 1 || 0 || 1 || 1 || 1 || 1 |- ! E | 1 || 1 || 1 || 0 || 1 || 1 |} On remplit ensuite la matrice M en utilisant la règle suivante&nbsp; M[i, j] est égale au minimum de: * L’élément directement avant plus 1: M[i-1, j] + 1. * L’élément directement au dessus plus 1: M[i, j-1] + 1. * Le diagonal précédent plus le coût: M[i-1, j-1] + Cout(i, j). Dans notre cas, le remplissage de la première ligne donne alors: {|class="wikitable" ! !! !! C !! H !! I !! E !! N !! S |- | || 0 || 1 || 2 || 3 || 4 || 5 || 6 |- ! N | 1 || 1 || 2 || 3 || 4 || 4 || 5 |- ! I | 2 || 0 || 0 || 0 || 0 || 0 || 0 |- ! C | 3 || 0 || 0 || 0 || 0 || 0 || 0 |- ! H | 4 || 0 || 0 || 0 || 0 || 0 || 0 |- ! E | 5 || 0 || 0 || 0 || 0 || 0 || 0 |} Nous réitérons cette opération jusqu'à remplir la matrice : {|class="wikitable" ! !! !! C !! H !! I !! E !! N !! S |- | || 0 || 1 || 2 || 3 || 4 || 5 || 6 |- ! N | 1 ||''' {{info|1|supprimer 'N'}}''' || 2 || 3 || 4 || 4 || 5 |- ! I | 2 ||''' {{info|2|supprimer 'I'}}''' || 2 || 2 || 3 || 4 || 5 |- ! C | 3 ||''' {{info|2|'C' égal 'C'}}''' || 3 || 3 || 3 || 4 || 5 |- ! H | 4 || 3 || '''{{info|2|'H' égal 'H'}}''' || '''{{info|3|ajouter 'I'}}''' || 4 || 4 || 5 |- ! E | 5 || 4 || 3 || 3 || '''{{info|3|'E' égal 'E'}}''' || '''{{info|4|ajouter 'N'}}''' || '''{{info|5|ajouter 'S'}}''' |} La distance de Levenshtein entre les mots s et t se retrouve en M[n, m]. Ici, on retrouve bien les 5 opérations trouvées de manière intuitive, la dernière matrice fournit aussi explicitement les opérations nécessaires pour passer d'une chaîne de caractères à l'autre. == Généralisation == En remplaçant chaîne de caractères par séquence de symboles, les symboles étant comparables par un opérateur d'égalité, on peut définir une distance d'édition fonctionnant sur d'autres types que des chaînes de caractères. ==Voir aussi== * [[Distance de Hamming]] * [[Distance d'édition sur les arbres]] * [[diff]] * [[:b:en:Algorithm implementation/Strings/Levenshtein distance|Implémentation en plusieurs langages de programmation]] * [[Jaro]] * [[Distance de Jaro-Winkler]] * [[Indice et distance de Jaccard]] * [[TF-IDF]] * [[Sam Chapman]] * [[William W. Cohen]] {{Navigation algorithmes textes}} {{Portail informatique}} [[Catégorie:Algorithme sur les chaînes de caractères]] [[Catégorie:Théorie des codes]] [[af:Levenshteinafstand]] [[de:Levenshtein-Distanz]] [[en:Levenshtein distance]] [[es:Distancia de Levenshtein]] [[fi:LevenÅ¡teinin etäisyys]] [[it:Distanza di Levenshtein]] [[ja:レーベンシュタインè·é›¢]] [[lv:LevenÅ¡teina attÄlums]] [[nl:Levenshteinafstand]] [[nn:Levenshtein-distanse]] [[pl:OdlegÅ‚ość Levenshteina]] [[pt:Distância Levenshtein]] [[ru:РаÑÑтоÑние Левенштейна]] [[sr:Левенштајново раÑтојање]] [[tg:МаÑофаи Левенштейн]] [[uk:ВідÑтань Левенштейна]] [[vi:Khoảng cách Levenshtein]] [[zh:編輯è·é›¢]]</text> </revision> </page>