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

Hi

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

Sagt dir Dynamische Programmierung etwas? Vielleicht hilft es, mal die Tabelle aufzuzeichnen anhand eines Beispiels aufzuzeichnen: http://www-igm.univ-mlv.fr/~lecroq/seqcomp/node2.html

Macht der Code überhaupt, was er soll?