Thema: Delphi Levenshtein-Distanz

Einzelnen Beitrag anzeigen

Benutzerbild von Flocke
Flocke

Registriert seit: 9. Jun 2005
Ort: Unna
1.172 Beiträge
 
Delphi 10.2 Tokyo Professional
 
#9

Re: Levenshtein-Distanz

  Alt 11. Dez 2005, 13:22
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.
Volker
Besucht meine Garage
Aktuell: RtfLabel 1.3d, PrintToFile 1.4
  Mit Zitat antworten Zitat