Levenshtein-Distanz

Sinex

Grünschnabel
Ich habe hier eine Implementierung für die Lvenshtein-Distanz in Delphi gefunden: http://www.delphipraxis.net/post471225.html

function Levenshtein(const str1, str2: string): integer;
var
delta: array of integer;
len1, len2: integer; // length of str1, str2
idx1, idx2: integer; // index into str1, str2
clast, cnew: integer; // last/next cost
begin
len1 := Length(str1);
len2 := Length(str2);
if (len1 = 0) and (len2 = 0) then
Result := 0
else if (len1 = 0) or (len2 = 0) then
Result := 100
else
begin
SetLength(delta, len2 + 1);

for idx2 := 0 to len2 do
delta[idx2] := idx2;

for idx1 := 1 to len1 do
begin
clast := delta[0];
delta[0] := idx1;

for idx2 := 1 to len2 do
begin
cnew := clast + Ord(str1[idx1] <> str2[idx2]);
if delta[idx2] + 1 < cnew then
cnew := delta[idx2] + 1;
if delta[idx2 - 1] + 1 < cnew then
cnew := delta[idx2 - 1] + 1;
clast := delta[idx2];
delta[idx2] := cnew;
end;
end;

Result := delta[len2] * 100 div len2;
(* Alternativ:
if len2 > len1 then
Result := delta[len2] * 100 div len2
else
Result := delta[len2] * 100 div len1;
*)
end;
end;

Ich verstehe nun einige Sachen nicht:
1. delta[0] := idx1; //wieso? auf delta[0] wird doch nie zugegriffen
2. cnew := clast + Ord(str1[idx1] <> str2[idx2]); müsste doch dann beim Schleifendurchlauf den Wert immer weiter erhöhen, ausser ich vergleich 'ttttt' mit 'tttttttt', wie verhindern diese beiden vergleiche dies (3.)
3. Warum vergleich ich gerade mit delta[idx2] + 1und delta[idx2 - 1] + 1 ?

Sinex
 

vop

Erfahrenes Mitglied
Hi

Ich empfehle dir, den Code mal im Debugger Schritt für Schritt durchzugehen, dann siehst du wie er arbeitet.
vop