Distance levenshtein (distance entre deux chaines)

Soyez le premier à donner votre avis sur cette source.

Vue 8 986 fois - Téléchargée 635 fois

Télécharger le projet
Commenter

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.
Télécharger le projet

Codes Sources

A voir également

Ajouter un commentaire

Commentaires

Signaler
DevNul
Messages postés
9
Date d'inscription
vendredi 14 février 2003
Statut
Membre
Dernière intervention
21 mars 2008
 -
Salut VBSNAIL,
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.
Signaler
VBsnail
Messages postés
13
Date d'inscription
mercredi 22 février 2006
Statut
Membre
Dernière intervention
19 mars 2008
 -
J'en apprend touts les jours sur VbFrance !!

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 ?
Signaler
DevNul
Messages postés
9
Date d'inscription
vendredi 14 février 2003
Statut
Membre
Dernière intervention
21 mars 2008
 -
Je verais pour virer les EXE... mais ma source n'est pas du tout la même que celle de Forman ;)
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 @+
S'inscrire maintenant

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.

Du même auteur (DevNul)