- Admissibilité
- Neutralité
- Droit d'auteur
- Article de qualité
- Bon article
- Lumière sur
- À faire
- Archives
- Commons
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)
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)
- 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
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 ;)
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
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)
- Pour commencer, et pour la forme, en français, on ne dit pas status d'ébauche, mais statut d'ébauche. En effet, status d'ébauche, c'est de l'anglais.
- ·
- Sur le fond, je trouve cet article très lacunaire:
- quand l'algorithme a été découvert?
- Sur le plan de la mise en pratique:
- Fonctionne-t-il sur des chaînes de caractères de taille variable (exemple: utf-8)?
- Est-il nécessaire d'appliquer une même Normalisation Unicode (NFC/NFD/...) sur chacune des deux chaînes à comparer?