Distance levenshtein (distance entre deux chaines)
Soyez le premier à donner votre avis sur cette source.
Vue 9 448 fois - Téléchargée 693 fois
Description
Une implémantation de la distance Levenshtein. Plus de renseignemant ici : http://fr.wikipedia.org/wiki/Distance_de_Levenshtein
Source / Exemple :
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.
Codes Sources
A voir également
- Distance de levenshtein
- Levenshtein distance - Meilleures réponses
- Distance levenshtein - Meilleures réponses
- IRC : La distance levenshtein vs les fautes de frappe - CodeS SourceS - Guide
- C# / .NET : Levenshtein (distance de), algorithme - CodeS SourceS - Guide
- Base de données distance entre villes - Guide
- Api calcul distance entre deux villes - Guide
- Distance qu'a parcourue la souris (mètrique) - Codes sources - Visual Basic / VB.NET (Souris, Clavier, etc…)
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.
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 ?
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.