Levenshtein-Distanz

[stoxx]

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 ...

[stoxx]

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

[Flocke]

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.