Discuter:Distance de Levenshtein

Un article de Wikipédia, l'encyclopédie libre.

	Distance de Levenshtein fait partie du projet Informatique, qui a pour but d'enrichir le contenu de Wikipédia sur les sujets liés à l'informatique. Si vous voulez participer, vous pouvez modifier cet article ou visiter la page du projet où vous pourrez vous joindre au projet et consulter la liste des tâches et des objectifs. Le portail informatique pourrait aussi vous intéresser.
Ébauche	Cet article a été classé comme d'Avancement ébauche selon le Tableau d'évaluation du projet. (Voir les statistiques)
À évaluer	Cet article a été classé comme d'Importance ? selon le Tableau d'évaluation du projet. (Contester?)

Sommaire 1 Distance utilisé dans cet article 2 Explication du calcul théorique 3 Complément 4 status ébauche

[modifier] Distance utilisé dans cet article

Cet article parle bien de la distance de Levenshtein et non de la distance de Damerau-Levenshtein, l'échange de deux caractères n'est pas permis. - phe 31 mai 2006 à 18:45 (CEST)

¿ L'échange de caractères n'est pas permi ? J'aurais dit que oui. ---moyogo ☻☺ 31 mai 2006 à 19:36 (CEST)

Par échange de deux caractères je veux dire ae --> ea (transposition serait meilleur comme terme ?) comme opération de base, avec cette opération ce n'est plus une distance de Levenshtein mais une distance de Damerau-Levenshtein. - phe 30 juin 2006 à 16:34 (CEST)

[modifier] Explication du calcul théorique

Soit Cout(i,j)=0 si A(i)=B(j) et Cout(i,j)=1 si A(i)!=B(i) On a donc ici la matrice Cout:

	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

Bon, je ne suis pas un expert en ce qui concerne les matrices (du moins pas pour l'instant en tout cas), mais je ne comprend pas a quoi correspond A() et B() . Surement des conventions utilisées pour désigner un mot et l'autre, mais je ne vois pas la logique. il est écrit aussi par l'auteur: Cout(i,j)=0 si A(i)=B(j) et Cout(i,j)=1 si A(i)!=B(i) Je pense que c'est une erreur et que c'set A(i)!=B(j), mais je me trompe peut etre la aussi... Nimportnawak 24 décembre 2005 à 13:51 (CET)

Oui A et B sont les mots en entrées et il y avait bien une erreur pour le remplissage de la matrice des couts. - phe 30 juin 2006 à 16:39 (CEST)

L'explication exposée ici est fausse : il faut faire un tableau de (m+1)x(n+1), allez voir l'article anglais qui donne la bonne méthode. Si parfois la méthode exposée ici donne un résultat juste, c'est du pur coup de bol...

n'importe quoi, ça marche aussi très bien comme ça. C'est juste que cette version ne permet de suppression du premier caractère. Si tu regardes comment ils font sur [1] c'est bien avec un tbleau mxn Sylenius 17 novembre 2006 à 16:52 (CET)

Avant de d'affirmer que ce que je dis c'est "n'importe quoi" et raconter donc des conneries (là je suis faché), tu aurais du prendre le temps de vérifier ! La distance d'édition et le dynamic Time Warping, si ils se ressemblent, ne se calculent pas avec les mêmes valeurs initiales. Testes ça : Mot1=COUCHE et mot2=MOUCHE, normalement la distance devrait être de 1 et pas de 0. Pareil : Mot1=RUCHE et Mot2=COCHE , normalement le résultat devrait être 2 et non 1 (comme pour RUCHE et MOCHE) Explication : la première lettre des deux ne sert ici à rien et n'est jamais prise en considération. Le lien anglophone est ici : http://en.wikipedia.org/wiki/Levenshtein_distance. Je trouve ça SUPER SYMPA de prendre à la légère ceux qui veulent aider un tant soit peu. Ce n'est pas parce qu'une information à des source, qu'elle est fiable, surtout si la source ne l'est pas !

Bonsoir !

pas la peine de s'énerver. Toi aussi tu aurais pu lire mon message plus précisément, parce nous sommes en fait d'accord: j'ai dit que cette version ne permet pas de prendre en compte le premier caractère, c'est exactement ce que tu détailles. Désolé pour le "n'importe quoi", mais il se référait à ta remarque "Si parfois la méthode exposée ici donne un résultat juste, c'est du pur coup de bol". Ca c'est pas vrai, ça dépend juste du premier caractère, et ça dépend aussi comment on souhaite calculer son truc, ça peut être valable, ça ne donne pas n'importe quoi... Sylenius 17 novembre 2006 à 17:23 (CET)

Excuse moi de m'être emporté, mais c'est vrai que je n'ai pas trouvé l'accueil particulièrement chaleureux. Celà dit, il n'y a pas à tortiller, si la première lettre des mots compte pour des prunes, je ne vois absolument pas l'intérêt de la méthode exposée ici. Un correcteur orthographique utilisant cet algorithme pour chercher des mots approchant dans un dictionnaire donnera un résultat idiot à chaque fois que dans son dictionnaire existe deux mots avec une première lettre différentes. Et en plus, non seulement cette version ne permet pas la suppression du premier caractère, mais ni même l'insertion ni même la substitution. Ca ne devrait tout de même pas être la mer à boire d'accepter de dire qu'en l'état, ce n'est pas bon, et de rectifier le tir, non ? Ce qui est fou, c'est que ce n'est pas le premier article que je lis et ou je vois les gens se faire remballer. Wilfrid AVRILLON

C'est vrai que j'ai été brutal. Pardon. Tu as raison, et je suis d'accord pour dire qu'il faut mofifier la version présentée ici et prendre le modèle anglais par exemple. Toutefois la distance de levenshtein ne s'utilise pas forcément sur des caractères, et il y a des domaines où la version présentée ici est correcte. C'était le sens de ma (très mal exprimée) remarque, mais bon on ets vendredi soir et je dois être fatigué.... encore pardon. Sylenius 17 novembre 2006 à 17:57 (CET)

Haaaa, on avance ;) Celà prouve qu'il y a des gens intelligents sur Wikipedia (parce que dans la partie cosmologie, big bang et tout le toutim, c'est pas gagné vu les jolies fleurs à épines qu'ils se balancent nos scientifiques d'opérettes : quand ils font des erreurs, eux ne savent pas l'admettre). Je te remercie donc pour cette ouverture d'esprit. Bon revenons à nos moutons : Jusqu'à preuve du contraire, la distance de Levenshtein ne s'utilise QUE sur des chaines de caractères (ou associé, tel les séquences de nucléotides pour l'ADN, d'ailleurs on va y revenir). Par contre, la méthode de calcul à ouvert le champ, à des algorithmes dérivés, notemment celui de la distance dynamique temporelle (ou Dynamic Time Warping), qui sert à mesurer une distance entre deux échantillons de points (deux courbes échantillonnées donc), et permet de là la reconnaissance gestuelle, la reconnaissance vocale, la reconnaissance de formes, la reconnaissance faciale, d'empreintes, etc... En l'état, je ne critique pas l'algorithme informatique exposé ici, qui lui est bon, mais le chapitre Théorie qui ne tient pas debout (mais alors pas du tout !), et qui est en complet déphasage avec l'algorithme informatique qui est exposé. Avoue que ça la fiche mal, pour une encyclopédie d'exposer quelque chose qui ne fonctionne pas. Et sinon, à ma connaissance, et j'insiste : il n'y a aucun domaines où la version présentée ici soit correcte. Tu imagines la recherche sur le génome, si elle cherche une séquence d'ADN sur laquelle on oublie de comparer un nucléotide ? Ils vont être heureux de leur traitements les enfants bulles, les myopathes, etc... Et puis déjà les OGM, ça craint, mais si on a mal identifié un gène pour cloner l'épis de mais, on risque de se retrouver avec une plante carnivore.... LOL

Oui. C'est vrai que la partie théorie n'est pas très bien rédigée, ce serait à revoir. Un truc me gène dans ce que tu dis (et en général) c'est que la distance de Levenshtein a été développée à l'origine en tant que code correcteur d'erreur, et les symboles sur laquelle elle s'applique peuvent donc être autre chose que des caractères, il suffit d'avoir une notion de distance entre les symboles. La version sur les chaines de caractères, moi j'ai plutôt tendance à appeler ça distance d'édition. Cela m'amène aux multiples facettes de cet algo, en fonction des définitions des couts, des distances entre symboles, et autres, toutes appelées un peu au hasard distance de Levenshtein, distance d'édition ou DTW... alors que c'est fondamentalement le même algo et que les différences sont quand même minimes. Le papier original de Levenshtein est écrit en russe... donc je ne sais pas comment était l'algo initial ;-) Il faudrait peut être présenter l'algo de manière plus générale, et donner ses divers simplifications ensuite ? Sylenius 17 novembre 2006 à 19:41 (CET)

Hé bien écoutes, je ne sais pas si tu connais www.developpez.com. J'y suis modérateur Delphi (mon surnom est "Waskol" et je suis justement en train d'écrire un article pour le site ou j'expose le fonctionnement complet de l'algorithme de Levenshtein et de ses petits (suite à un défi de programmation que jai lancé et qui consistait en de la reconnaissance gestuelle). En fait, dans tout ce que j'ai lu, j'ai remarqué que tout le monde confond, la "distance entre deux lettre", qui correspond à un état, une sorte de lien, entre deux éléments, qui représente bien une distance bien réelle entre deux éléments des deux "Mots" à comparer (utilisé pour calculer le coût de substitution), et les coûts de transition qui servent à quantifier le coût de passage d'une case à une autre (ce qui bien à ce que sont l'insertion et à la substitution). Et en comprenant le fait que cet état qui relie deux lettre,et que l'on quantifie par la substitution, en l'éxaminant plutot comme étant "les deux lettres qui viennent d'être traitée par la transformation", je t'assures que le passage de l'énoncé "minimiser le nombre d'opérations de suppression, insertion, et substitution" à algorithme de Levenshtein devient limpide et naturel. Et je n'ai trouvé aucune explication comme celle-ci sur le web.

Ce qui serait bien, ce que tu puisses transférer l'article que tu es en train d'écrire, ou une partie, sur wikipédia, si la politique du site www.developpez.com t'y autorise. Il faut aussi que tu sois d'accord pour le texte que tu proposeras soit en licence GFDL. Tu peux l'insérer tel quel, moi, ou d'autres, se chargeront de le wikifier, c'est à dire le mettre en forme. Cordialement, Sylenius 18 novembre 2006 à 16:15 (CET)

A priori ça ne pose pas de problêmes pour DVP étant donné que je suis le seul auteur. Je me laisse le temps d'y réfléchir, de finir mon article, etc... à plus. ;)

message du 4/1/2007 : mon article pour DVP est en relecture, après corrections je lui ajouterais la licence GFDL pour la partie interessant wikipedia. L'article original de 37 pages à été rédigé au format OpenDoc (sous Open Office 2.0). Patience, vous l'aurez bientôt à dispo... PS: bravo pour la re-rédaction de l'article, l'explication est maintenant juste ;)

[modifier] Complément

La distance de Levenstein (en fait : Damerau et Levenstein) peut être complétée par 3 opérateurs (Source : Senui, Kripsundar et Srihari) qui prennent en compte les écarts à 2 caractères : division, fusion et substitution par paire.

Sur le même principe que l'algorithme : d[i,j]= min {

 d[i-1,j-1] + Cout_Substitution(Str1[i],Str2[j])
 d[i-1,j]   + Cout_Insertion(Str1[i])
 d[i,j-1]   + Cout_Suppression(Str2[j])
 d[i-2,j-1] + Cout_Division(Str1[i-1],Str1[i],Str2[j])
 d[i-1,j-2] + Cout_Fusion(Str1[i],Str2[j-1],Str2[j])
 d[i-2,j-2] + Cout_Inversion(Str1[i-1],Str1[i],Str2[j-1],Str2[j])  }

où

 d[0,0]=0
 d[i,0]=Somme{k=1 à i : Cout_Insertion(Str1[k]) }
 d[0,j]=Somme{k=1 à j : Cout_Suppression(Str2[k]) }

NB : Document sur ce sujet sur le site de l'IRISA, à Rennes, dans le cadre d'une recherche sur la reconnaissance de l'écriture manuscrite.

Je mets à suivre un code Visual Basique (pour Excel 97) de cette fonction qui prend en compte les coûts suivants :

 la suppression ou l'insertion d'un blanc "coûte" moins qu'une autre lettre
 la fusion ou la division de lettre identiques (ex: "mm" en "m") "coûte" moins
 l'inversion de deux lettres (ex : "ma" en "am") "coûte" moins

Les fonction de substitution, fusion et division doivent pouvoir être améliorées en fonction de la proximité des touches, de la phonétique, etc...

       Const Dummy_max_value As Double = 999
       Public Function Insert_penalty(a As String) As Double
       
           Const C_Insert_penalty As Double = 1
           Const C_Insert_blank_penalty As Double = 0.5
           
                   If (Mid(a, 1, 1) = " ") Then
                       Insert_penalty = C_Insert_blank_penalty
                   Else
                       Insert_penalty = C_Insert_penalty
                   End If
       End Function
       
        Public Function Delete_penalty(b As String) As Double
       
           Const C_Delete_penalty As Double = 1
           Const C_Delete_blank_penalty As Double = 0.5
           
                   If (Mid(b, 1, 1) = " ") Then
                       Delete_penalty = C_Delete_blank_penalty
                   Else
                       Delete_penalty = C_Delete_penalty
                   End If
       End Function
      
       Public Function Substitute_penalty(a As String, b As String) As Double
       
           Const C_Substitute_penalty As Double = 1
           
                   If (Mid(a, 1, 1) = Mid(b, 1, 1)) Then
                       Substitute_penalty = 0
                   Else
                       Substitute_penalty = C_Substitute_penalty
                   End If
       End Function
      
       Public Function Divide_penalty(a1 As String, a As String, b As String) As Double
       
           Const C_Divide_penalty As Double = 0.5
           
                   If (Mid(a1, 1, 1) = Mid(a, 1, 1)) And (Mid(a, 1, 1) = Mid(b, 1, 1)) Then
                       Divide_penalty = C_Divide_penalty
                   Else
                       Divide_penalty = Dummy_max_value
                   End If
       End Function
      
        Public Function Fusion_penalty(a As String, b1 As String, b As String) As Double
       
           Const C_Fusion_penalty As Double = 0.5
           
                   If (Mid(b1, 1, 1) = Mid(b, 1, 1)) And (Mid(a, 1, 1) = Mid(b, 1, 1)) Then
                       Fusion_penalty = C_Fusion_penalty
                   Else
                       Fusion_penalty = Dummy_max_value
                   End If
       End Function
     
        Public Function Inverte_penalty(a1 As String, a As String, b1 As String, b As String) As Double
       
           Const C_Inverte_penalty As Double = 0.5
           
                   If (Mid(b1, 1, 1) = Mid(a, 1, 1)) And (Mid(a1, 1, 1) = Mid(b, 1, 1)) Then
                       Inverte_penalty = C_Inverte_penalty
                   Else
                       Inverte_penalty = Dummy_max_value
                   End If
       End Function
           
      Public Function LevenshteinDistance(a As String, b As String) As Double

           Dim len_a As Integer, len_b As Integer
           len_a = Len(a)
           len_b = Len(b)
           Dim d() As Double
           ReDim d(-1 To len_a, -1 To len_b) As Double
           Dim i As Integer
           Dim j As Integer
           Dim Insert_cost As Double
           Dim Delete_cost As Double
           Dim Substitute_cost As Double
           Dim Divide_cost As Double
           Dim Fusion_cost As Double
           Dim Inverte_cost As Double
           Dim Min_cost As Double
           Dim Test_cost As Double
           
           LevenshteinDistance = Dummy_max_value
           
           For i = -1 To len_a
               d(i, -1) = Dummy_max_value
           Next i
           For j = -1 To len_b
               d(-1, j) = Dummy_max_value
           Next j
           d(0, 0) = 0
           For i = 1 To len_a
               d(i, 0) = d(i - 1, 0) + Insert_penalty(Mid(a, i, 1))
           Next i
           For j = 1 To len_b
               d(0, j) = d(0, j - 1) + Delete_penalty(Mid(b, j, 1))
           Next j

            For i = 1 To len_a
               For j = 1 To len_b
                   ' insert cost
                       Insert_cost = Insert_penalty(Mid(a, i, 1))
                   ' delete cost
                       Delete_cost = Delete_penalty(Mid(b, j, 1))
                   ' substitute cost
                       Substitute_cost = Substitute_penalty(Mid(a, i, 1), Mid(b, j, 1))
                   ' fusion cost
                   If j = 1 Then
                       Fusion_cost = Dummy_max_value
                   Else
                       Fusion_cost = Fusion_penalty(Mid(a, i, 1), Mid(b, j - 1, 1), Mid(b, j, 1))
                   End If
                   ' divide cost
                   If i = 1 Then
                       Divide_cost = Dummy_max_value
                   Else
                       Divide_cost = Divide_penalty(Mid(a, i - 1, 1), Mid(a, i, 1), Mid(b, j, 1))
                   End If
                   ' inverte cost
                   If (j = 1) Or (i = 1) Then
                       Inverte_cost = Dummy_max_value
                   Else
                       Inverte_cost = Inverte_penalty(Mid(a, i - 1, 1), Mid(a, i, 1), Mid(b, i - 1, 1), Mid(b, j - 1, 1))
                   End If
                   
                   ' min computation
                   Min_cost = d(i - 1, j) + Insert_cost
                   Test_cost = d(i, j - 1) + Delete_cost
                   If Test_cost < Min_cost Then
                       Min_cost = Test_cost
                   End If
                   Test_cost = d(i - 1, j - 1) + Substitute_cost
                   If Test_cost < Min_cost Then
                       Min_cost = Test_cost
                   End If
                   Test_cost = d(i - 2, j - 1) + Divide_cost
                   If Test_cost < Min_cost Then
                       Min_cost = Test_cost
                   End If
                   Test_cost = d(i - 1, j - 2) + Fusion_cost
                   If Test_cost < Min_cost Then
                       Min_cost = Test_cost
                   End If
                   Test_cost = d(i - 2, j - 2) + Inverte_cost
                   If Test_cost < Min_cost Then
                       Min_cost = Test_cost
                   End If
                   d(i, j) = Min_cost
               Next j
           Next i

           LevenshteinDistance = d(len_a, len_b)
           
       End Function

[modifier] status ébauche

Pourquoi cet article a toujours le status d'ébauche? ne peut-on pas concidérer qu'il est assez complet pour être un rticle à par entière, même s'il n'est pas totalement exhaustif (est-ce le cas?) ni un AdQ? --Dude 27 juin 2006 à 17:02 (CEST)