Ich hab' noch mal ein bisschen mit dem Algorithmus herumgespielt. Hier die Ergebnisse meiner Tests, für den Fall, dass du doch beim Levenshtein bleiben willst.
Erstens kann man ihn so umschreiben, dass der Speicherbedarf linear ist (Laufzeit ist allerdings immer noch quadratisch).
Zweitens ist die Zuweisung bei der Prüfung auf Länge 0 nicht korrekt, da hier ein Unterschied von 100% zurückgeliefert werden sollte und nicht die Länge des jeweils anderen Strings. Das ist wohl ein Überbleibsel vom Originalalgorithmus gewesen.
Bei deiner Funktion ist es übrigens (im Gegensatz zur originalen Levenshtein-Distanz) nicht egal, in welcher Reihenfolge man die Parameter angibt. Für die Originalfunktion gilt D(a,b)=D(b,a) - du nimmst aber als Quotienten für die Prozentberechnung immer die zweiten Parameter. Hier solltest du den längeren der beiden Parameter nehmen, dann liegt der berechnete Wert immer zwischen 0 und 100.
Außerdem hat es sich bei mir als nicht Laufzeitrelevant herausgestellt, wenn man die Parameter als
const deklariert.
Ergebnis:
Delphi-Quellcode:
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 // <-- ist noch der alte!
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;
(Edit: korrigiert)
Durch den Wegfall der Doppelindizierung ist diese Version bei mir 2-3 mal schneller als die ursprüngliche mit zweidimensionalem Array.
Und nun noch eine Optimierung. Ich denke, du rufst jeweils Levenshtein(a, b) auf und falls das Ergebnis unter einem gewissen Prozentwert liegt gehst du davon aus, dass es sich um denselben Text handelt.
Hier kannst du dir die Tatsache zu Nutzen machen, dass die absolute Levenshtein-Distanz (ich nenne sie mal so) immer mindestens so groß ist wie der Längenunterschied der beiden Strings.
Wenn deine Toleranzgrenze also bei 5% liegt und der String, mit dem du alle anderen vergleichen willst 50 Zeichen lang ist, dann darf die absolute Levenshtein Distanz den Wert (5 * 50 div 100) = 2 nicht übersteigen. Du musst also nur mit Strings mit einer Länge von 48 bis 52 vergleichen.
Denn: 47 zu 50 Zeichen haben die Mindestdistanz von 3, also (3 * 100 div 50) = 6%.
Bei einem String mit weniger als 20 Zeichen musst du bei 5% Toleranz schon genau die Länge haben (bzw. sogar genau die Zeichenfolge treffen).
Das kann die Anzahl der zu vergleichenden Strings drastisch reduzieren und bei einer Datenbankabfrage könntest du die Längenbeschränkung ebenfalls schon in das SELECT-Statement einbauen.