Zitat von
SirThornberry:
Damit müsste nicht jedes mal speicher dafür angelegt werden
Der Speicher wird nicht angelegt, es wird einfach 262144 von ESP abgezogen und fertig - das verbraucht zwar Stackspeicher aber fast keine Laufzeit.
@Nicolai1605:
Wenn ich heute etwas Zeit hätte, dann würde ich den oben geschilderten heuristischen Ansatz auf dein Problem umformulieren. Vom Verfahren her so:
Delphi-Quellcode:
function FindeLaengsteUebereinstimmung(const s1, s2: string;
var Pos1, Pos2, Len: integer): boolean;
begin
// Suche die längste Übereinstimmung zwischen den beiden Strings
// und liefere "Pos1"=deren Position in "s1", "Pos2"=deren Position
// in "s2" und "Len"=deren Länge.
// Ergebnis: true falls es eine Übereinstimmung gibt, sonst "false"
end;
function Levenshtein(const s1, s2: string): integer;
var
Pos1, Pos2, Len: integer;
begin
if s1 = s2 then
Result := 0
else if (s1 = '') or (s2 = '') then
Result := 1
else if not FindeLaengsteUebereinstimmung(s1, s2, Pos1, Pos2, Len) then
Result := 1
else
Result := Levenshtein(Copy(s1, 1, Pos - 1), Copy(s1, 1, Pos2 - 1) +
Levenshtein(Copy(s1, Pos1 + Len, Length(s1) - Pos1 - Len),
Copy(s2, Pos2 + Len, Length(s2) - Pos2 - Len);
end;
Das Ganze kann man natürlich noch optimieren und auch einen Zweig der Rekursion durch eine Schleife auflösen. Der Ansatz könnte aber schon schneller sein - insbesondere wenn man "FindeLaengsteUebereinstimmung" durch ein Hash-Array (Zeichen aus s1 -> Mögliche Stellen in s2) optimiert.