AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren

Levenshtein-Distanz

Ein Thema von Nicolai1234 · begonnen am 11. Dez 2005 · letzter Beitrag vom 15. Dez 2005
Antwort Antwort
Seite 4 von 4   « Erste     234
Benutzerbild von stoxx
stoxx

Registriert seit: 13. Aug 2003
1.111 Beiträge
 
#31

Re: Levenshtein-Distanz

  Alt 13. Dez 2005, 14:45
Zitat von Nicolai1605:
Aber was wäre, wenn sich jemand bei einem längeren Wort verschreibt. Dann sind auch 2 einzelne Wörter nicht mehr exakt gleich. Daher war ich ein wenig irritiert. Vielleicht habe ich das aber auch falsch verstanden...
ja .. deswegen prüfst Du ja alle Wörter des Buchtitels auf dessen Vorkommen im gesamten Text.
Wenn derjenige sich dann in jedem Wort verschreibt, geht das natürlich nicht ...
Phantasie ist etwas, was sich manche Leute gar nicht vorstellen können.
  Mit Zitat antworten Zitat
Benutzerbild von stoxx
stoxx

Registriert seit: 13. Aug 2003
1.111 Beiträge
 
#32

Re: Levenshtein-Distanz

  Alt 13. Dez 2005, 14:47
der Vorteil wäre sogar noch, wenn jemand den gesamten Satz umbauen würde, dann würdest Du das eventueall auch finden können.
Wenn z.B. 95 prozent der Wörter des Buchtitels in einer anderen Zeile vorkommen, könnte man auch sagen, dass es der gleiche buchtitel ist
Phantasie ist etwas, was sich manche Leute gar nicht vorstellen können.
  Mit Zitat antworten Zitat
Benutzerbild von Flocke
Flocke

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

Re: Levenshtein-Distanz

  Alt 15. Dez 2005, 00:13
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.
Volker
Besucht meine Garage
Aktuell: RtfLabel 1.3d, PrintToFile 1.4
  Mit Zitat antworten Zitat
Themen-Optionen Thema durchsuchen
Thema durchsuchen:

Erweiterte Suche
Ansicht

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 16:17 Uhr.
Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz