Ergebnis der Suchanfrage

• Forum: Sonstige Fragen zu Delphi

  Re: Levenshtein-Distanz

    Delphi
    by Flocke, 14. Dez 2005
  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%...
• Forum: Sonstige Fragen zu Delphi

  Re: Levenshtein-Distanz

    Delphi
    by Flocke, 11. Dez 2005
  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:
  
  
  function FindeLaengsteUebereinstimmung(const s1, s2: string;
  var Pos1, Pos2,...
• Forum: Sonstige Fragen zu Delphi

  Re: Levenshtein-Distanz

    Delphi
    by Flocke, 11. Dez 2005
  Hier noch mal eine Definition.
  
  Vielleicht hilft ein heuristischer Ansatz. Ich habe hier (bzw. hier) mal eine Pascal-Diff-Unit gepostet, die zwei Dateien zeilenweise miteinander vergleicht. Die könnte man so abändern, dass man zwei Strings zeichenweise vergleicht.
  
  Der Algo hat eine gewisse Ähnlichkeit zum Quicksort. Ganz simpel ausgedrückt: man sucht sich die längste Übereinstimmung in den...