AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren
Thema durchsuchen
Ansicht
Themen-Optionen

Levenshtein-Distanz

Ein Thema von Nicolai1234 · begonnen am 10. Dez 2005 · letzter Beitrag vom 14. Dez 2005
 
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, 12: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
 


Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 14:59 Uhr.
Powered by vBulletin® Copyright ©2000 - 2025, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024-2025 by Thomas Breitkreuz