Distance levenshtein (distance entre deux chaines)

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

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)