Soyez le premier à donner votre avis sur cette source.
Vue 9 758 fois - Téléchargée 714 fois
unit UnitLevenshtein; interface uses Math; type IntegerArray = Array of Integer; function Levenshtein(strWord1, strWord2: String; CoutSubst: Integer = 1): Integer; implementation function Levenshtein(strWord1, strWord2: String; CoutSubst: Integer = 1): Integer; Var Matrix : array[0..2] of IntegerArray; L,C,H,W,R: Integer; // Ligne, Colone, Heigt, Width Begin H := Length(strWord1); W := Length(strWord2); SetLength(Matrix[0], H + 1); SetLength(Matrix[1], H + 1); For L := 0 to H do Matrix[0, L] := L; For C := 1 to W do Begin Matrix[1, 0] := C; For L := 1 to H do Begin R := Min(Matrix[0, L]+1, Matrix[1, L-1]+1); If strWord1[L] = strWord2[C] then Matrix[1,L] := Min(R, Matrix[0,L-1]) Else Matrix[1,L] := Min(R, Matrix[0,L-1] + CoutSubst); End; Matrix[2] := Matrix[0]; Matrix[0] := Matrix[1]; Matrix[1] := Matrix[2]; End; Levenshtein := Matrix[0,H]; End; end.
21 mars 2008 à 11:44
La taille en elle même est un faux probléme. Le soucis vient de la structure de la chaine qui peut être une phrase et non un mots. Cette forme de distance convient, en gros, pour comparer des mots non composé. Si tu désire comparer des phrase il existe d'autre algorythme. Ma métode pour comparer des adresse postal a été de créer une matrice de comparaison mot à mot contenant les valeurs des distance LEVENSHTEIN obtenue. Ensuite parcourir cette matrice a la recherche du meilleur chemin (celui ayant maximisant le score obtenue par sommation des distance).
L'inconveniant de cette seconde matrice est sa naïveté qui coute ennormemant en ressource machine.
20 mars 2008 à 23:00
L'article sur Wiki indique que cet algo convient aux chaînes courtes.
Peux-tu indiquer la taille des chaînes que tu as traitées, et jusqu'où tu pense qu'on peut aller ?
27 nov. 2007 à 04:09
J'ai du chercher une méthode pour comparer des chaines lors d'une mission pour un gros client. J'ai un peut suivit la vois de Forman en 1er lieux, puis j'ai vue que le resultat n'était pas à la hauteur de ce que je désirait. Il pouvais "se planté" en considérant le meilleur candidat sans que ce ne soit le "vrai" cas.
La distance de Levenshtein est une formule permetant de connaitre le nombre d'opperation de substitution, d'insertion ou de suppression permetant de passé d'une chaine a l'autre ;). Ilpeut donc y'avoirdenombreux candidat exéco pouvant ensuite être présenté a l'humain pour qu'il termine le travaille.
Sur ce @+
Vous n'êtes pas encore membre ?
inscrivez-vous, c'est gratuit et ça prend moins d'une minute !
Les membres obtiennent plus de réponses que les utilisateurs anonymes.
Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.
Le fait d'être membre vous permet d'avoir des options supplémentaires.