1. Accueil
  2. Delphi / Pascal
  3. Sources Delphi / Pascal
  4. Sources Texte
  5. Distance levenshtein (distance entre deux chaines)

Distance levenshtein (distance entre deux chaines)

Soyez le premier à donner votre avis sur cette source.

Vue 9 758 fois - Téléchargée 714 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
DevNul Messages postés 9 Date d'inscription vendredi 14 février 2003 Statut Membre Dernière intervention 21 mars 2008
21 mars 2008 à 11:44
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.
VBsnail Messages postés 13 Date d'inscription mercredi 22 février 2006 Statut Membre Dernière intervention 19 mars 2008
20 mars 2008 à 23:00
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 ?
DevNul Messages postés 9 Date d'inscription vendredi 14 février 2003 Statut Membre Dernière intervention 21 mars 2008
27 nov. 2007 à 04:09
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)