Discussion :

[Finidrigoler]

Bonjour,


je recherche une fonction pour calculer la distance levenshtein entre deux chaines.

pour ceux qui ne savent pas ce que c'est, une description de ce que fait cet algo est disponible ici :

http://sql.developpez.com/soundex/
( vers le milieu de page )


si quelqu'un possede cette fonction dans sa boite a outils...

merci

[KiLVaiDeN]

Pourquoi ne pas écrire l'algorithme toi même ?

Je comprend que ça serait plus facile d'obtenir la fonction toute faite, mais quand même, ce n'est pas très dur, voici la page qui décrit l'algo.

A+

[slimjoe]

Salut!

Google est notre ami

Voici un lien intéressant que j'ai trouvé :

http://www.cs.pitt.edu/~kirk/cs1501/...20Distance.htm

On y décrit l'algo et on le traduit en JAVA, C++ et VB. Te reste qu'à le traduire en Delphi (et une fois fait, je suggère que tu nous partages ton travail, peut-être alors verras-tu ce dernier dans les pages "sources" de ce forum )

Bon dev!

[EDIT]
oops! KiLVaiDeN avait eu le lien avant moi.

[Finidrigoler]

si je savais ( ou plutot, me sentait capable de .. ) le faire, je l'aurais biensur fais.


je ne me sentais pas capable de le retranscrire en delphi ( je debute )


mais je vais essayer quand même.

[Finidrigoler]

au cas ou ça interesserait quelqu'un ( oui finalement, j'ai reussi )

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
 
function  Minimum (a:integer; b:integer; c:integer):integer;
var mi:integer;
begin
mi := a;
 
if (b < mi) THEN mi := b;
if (c < mi) THEN mi := c;
 
result:=mi;
end;
 
function Levensthein ( s:String;t:String) :integer;
var 
d:array of array of integer;
n,m,j,i:integer;
s_i,t_j:char;
cost:integer;
begin
 
    n := length (s);
    m := length (t);
    if (n = 0) THEN result:=m;
    if (m = 0) THEN result:=n;
 
	setLength(d,n+1, m+1);
 
	i := 0;
 
  while i <= n DO begin
	d[i][0] := i;
	i:=i+1;
	end;
 
	j := 0;
 
  while j <= m DO begin
  d[0][j] := j;
	j:=j+1;
	end;
 
	 i := 1;
  while i <= n DO
	begin
  s_i := s[i-1];
 
	  j := 1;
    while j <= m DO
	  begin
 
       t_j := t[j - 1];
        if (s_i = t_j) THEN begin cost := 0;end
        else cost := 1;
 
        d[i][j] := Minimum (d[i-1][j]+1, d[i][j-1]+1, d[i-1][j-1] + cost);
		j:=j+1;
      end;
 
	i:=i+1;
    end;
    Result:=d[n][m];
end;//LEVENSTHEIN

[KiLVaiDeN]

Félicitations, tu dois en éprouver une certaine fierté, non ?

Je te souhaite une bonne continuation

[slimjoe]

[Finidrigoler]

Merci, bon dev a vous

et j'avoue que ça ne m'a pas fais de mal de chercher moi même

[utilisateur_λ]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
 
function  Minimum( Val1, Val2, Cost: Integer): Integer;
begin
  Result := Cost;
  if Result > Val1 then
    Result := Val1;
  if Result > Val2 then
    Result := Val2;
end;
 
function FastLevensteinDistance( AText1: String; AText2: String; AMaxDistance: Integer): Integer;
var Matrix: array of Integer;
    Len1, Len2, i, j, ActualCost, NextCost, LastCost: Integer;
begin
  Len1 := Length( AText1);
  Len2 := Length( AText2);
  if Len1 = 0 then begin
      Result := Len2;
      Exit;
    end;
  if Len2 = 0 then begin
      Result := Len1;
      Exit;
    end;
  SetLength( Matrix, Len2 + 1);
  try
    LastCost := Len2;
    for j := 1 to Len2 - 1 do
      Matrix[ j] := j;
    for i := 1 to Len1 do begin
        LastCost := i;
        ActualCost := Len2;
        for j := 1 to Len2 do begin
            NextCost := Minimum( Matrix[ j] + 1, LastCost + 1, Matrix[ j - 1] + IfThen( AText1[ i] = AText2[ j], 0, 1));
            Matrix[ j - 1] := LastCost;
            LastCost := NextCost;
            ActualCost := FastMin( ActualCost, LastCost);
          end;
        if ActualCost > AMaxDistance then begin
            Result := AMaxDistance + 1;
            Exit;
          end else
            Matrix[ Len2] := LastCost;
      end;
    Result := LastCost;
  finally
    SetLength( Matrix, 0);
  end;
end;

"AMaxDistance" donne la distance au delà de la quelle le mot n'est plus intéressant.


La source est ici (c'est du perl ).