Levenshtein-Distanz

[Nicolai1234]

Hallo,
ich bin gerade dabei ein Programm meines Vaters zu überarbeiten. Er benutzte eine Funktion zur prozentualen Abweichung zweier Strings an Hand der Levenshtein Distanz, von der er leider nicht mehr weiß, woher er sie hat.
Die Funktion sieht wie folgt aus:

Delphi-Quellcode:

function Levenshtein(S,T:String):integer;

  var D:array[0..255,0..255] of integer;
      M:Integer;           // length of t
      N:Integer;           // length of s
      I:Integer;           // iterates through s
      J:Integer;           // iterates through t
      SI:Char;             // ith character of s
      TJ:Char;             // jth character of t
      Cost:Integer;        // cost
  begin
    N:=Length(S);
    M:=Length(T);
    if (N=0) then begin
      Result:=M;
      Exit;
    end;
    if (M=0) then begin
      Result:=N;
      Exit;
    end;

    for I:=0 to N do D[I,0]:=I;
    for J:=0 to M do D[0,J]:=J;
    for I:=1 to N do begin
      SI:=S[I];
      for J:=1 to M do begin
        TJ:=T[J];
        if (SI=TJ) then Cost:=0
        else Cost:=1;

        if (D[I-1,J-1]+Cost >= D[I,J-1]+1) then
           begin
           if (D[I-1,J]+1 >= D[I,J-1]+1) then
           D[I,J]:= D[I,J-1]+1
           else
           D[I,J]:= D[I-1,J]+1
           end
        else
           begin
           if (D[I-1,J]+1 >= D[I-1,J-1]+Cost)then
           D[I,J]:= D[I-1,J-1]+Cost
           else
           D[I,J]:= D[I-1,J]+1

        end;
      end;
    end;
    Result:=D[N,M]*100 div M;

  end;

Leider ist diese nicht besonders schnell, da sie in diesem Programm rund 12 Millionen mal hintereinander aufgerufen werden muss. Ich frage mich, ob es schnelle bzw. bessere Funktionen gibt, die diese Arbeit erledigen. Oder aber was man an der oberen noch verbessern könnte.

Zitat:

19 x 99 Dezibel(A) - ein gesicherter Befund der Lärmwirkungsforschung?
19x99 dB (A) - gesicherter Befund Lärm-wirkungs-Forschung

Es geht in diesem Programm darum, Strings wie diese als gleich zu erkennen. Da hilft das einfache Soundex leider nicht mehr weiter.

Naja, vielleicht habt ihr ja eine Idee...

Vielen Dank im voraus
Nicolai

[mael]

Allgemein ist der Algorithmus wohl kaum zu optimieren.
Die Laufzeit ist ungefähr: (N + M) + (N*M)
(mit N = Length(S) und M = Length(T))

N+M sind die beiden ersten for-Schleifen.
N*M sind die verschachtelten for-Schleifen (die sind das eigentliche Problem).
Dabei ist das was in den for-Schleifen steht jetzt nicht wahnsinnig zeitaufwändig, das Problem ist eher die verschachtelte Schleife an sich. Ob man da im Allgemeinen die Funktion vereinfachen kann bezweifle ich.

Dafür müßte man genaueres über die Eingabedaten wissen. So ist eventuell einer der beiden Strings immer gleich und es läßt sich ein Teil der Rechnung nur einmal machen, anstatt bei jedem Funktionsaufruf, bzw. vielleicht sogar N*M zu N machen (deutlich schneller).
Hängt aber wie gesagt von den Eingabedaten ab.

Poste am besten mal den Quelltext der die Funktion aufruft und typische Eingabebeispiele.

EDIT: Eine andere Möglichkeit ist natürlich den Algorithmus genauer zu studieren und zu hoffen einen besseren Ansatz zu finden (aber Webrecherchen legen nahe, daß das nicht trivial ist).
Konkrete Anwendungsbeispiele sind eventuell einfacher zu optimieren.

[Flocke]

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 beiden Strings und arbeitet dann rekursiv auf den beiden verbleibenden Hälften weiter.

[Robert Marquardt]

Es gibt noch ein paar Optimierungen.

Delphi-Quellcode:

      SI:=S[I];
      for J:=1 to M do begin
        TJ:=T[J];
        if (SI=TJ) then Cost:=0
        else Cost:=1;

Besser

Delphi-Quellcode:

   for J := 0 to M do
   begin
     Cost := Ord(S[I] <> T[J]);

SI und TJ sind Unsinn, wenn sie nur einmal gebraucht werden.
Den schoenen Trick mit Ord sollte man immer parat haben.

[Nicolai1234]

Zitat:

Zitat von mael

Poste am besten mal den Quelltext der die Funktion aufruft und typische Eingabebeispiele.

Also das Programm bekommt eine Textdatei, die ungefähr so aussieht:

Zitat:

1~806~ Complex fluid behavior: Coupling of the shear stress with order parameter tensors of ranks two and three in nematic liquid crystals and in tetradic fluids~1
2~1272~ Applied Rheology~4
3~765~ "www.mathematik.de - ein Mathematik-Portal für die Öffentlichkeit"~1
4~1286~ - Gemeinsame Präsentation Berliner Kreis - Fachgebietsbroschüren~15
5~1221~ Das Krankenhaus auf dem Weg zum virtuellen Unternehmen - Unternehmensentwicklung vom und zum Taylorismus?~1
6~812~ Klein, kleiner, am größten ? Bauinnovationen durch Werkstoff-wissen-schaft,~1
7~1001~ Untersuchung der Laufrad-Spirale-Interaktion einer radialen Kreiselpumpe mit Hilfe instationärer Strömungsberechnung~1
8~1158~'Orientalische' Spuren im Berlin der zwanziger Jahre~1
9~1068~()-2 Menthylindenyl and ()-2-Menthyl-4,7-dimethylindenyl Complexes of Rhodium, Iridium, Cobalt, and Molybdenum.~3
10~785~(Adalbert Reif im Gespräch mit Carola Sachse) Zwischen Anpassung und Machbarkeitswahn~3
11~1068~(C9H7)YbI(DME)2, the First Indenyl Half-Sandwich Complex of Divalent Ytterbium.~3
12~747~(Diffusion in Metallic Melts: The Shear Cell Technique)(With K.H.Kraatz, A.Griesche, G.Frohberg)~1
13~993~(chines.:)Humanistic factors an technology: Facts, artifacts and interpretation.~5
14~876~,~5
15~872~.~5
16~785~...denn zu Hause fällt die Decke auf den Kopf~3
17~785~...letztlich ging es doch voran!~2
18~812~.: Die Leistungssteigerung von Beton durch Kunststoffasern~5
19~1068~1,4-Diaza-1,3-diene (DAD) complexes of early transition elements.Syntheses, structures and molecular dynamics of mono- and bis(5-cyclopentadienyl)titanium-,zirconium- and hafnium(DAD) complexe~3
20~849~1. Intern. LITE-Show~12
21~723~1. The Rise of Metazoans: An integrated geophysiological analysis of their hydrothermal vent environments on the South China (Yangtze) Plate. 2. Transfer Mechanism of peri-Proto-Gondwana Basement Te~1
22~1280~1. Vibro-acoustics of beam-plate configurations~1
23~669~1.3 µm InAs/GaAs quantum dot lasers and VCSELs grown by molecular beam epitaxy~3
24~669~1.3 µm resonant-cavity InGaAs/GaAs quantum dot light-emitting devices~3
25~669~1.3 µm vertical microcavities with InAs/InGaAs quantum dots and devices based on them~3
26~669~1300 nm GaAs-based microcavity LED incorporating InAs/GaInAs quantum dots~3
27~983~160-Gb/s All-Optical Demultiplexing Using a Gain-Transparent Ultrafast-Nonlinear Interferometer (GT-UNI)~3
28~946~19 x 99 Dezibel(A) - ein gesicherter Befund der Lärmwirkungsforschung?~5
29~946~19x99 dB (A) - gesicherter Befund der Lärmwirkungsforschung~3

Nun geht es darum, selbe Titel zu finden (3. Spalte (durch Tilde getrennt)).
Es handelt sich dabei um ca. 6000 Zeilen.

Augerufen wird die Funktion mit jedem der 6000 Titel, da er jeden Titel mit jedem wieder vergleicht.

Nicolai

[SirThornberry]

eventuell würde es schon etwas bringen die function als methode zu nutzen, und dann

Delphi-Quellcode:

var D:array[0..255,0..255] of integer;

im private zu definieren. Damit müsste nicht jedes mal speicher dafür angelegt werden

[Nicolai1234]

Zitat:

Zitat von SirThornberry

eventuell würde es schon etwas bringen die function als methode zu nutzen, und dann

Delphi-Quellcode:

var D:array[0..255,0..255] of integer;

im private zu definieren. Damit müsste nicht jedes mal speicher dafür angelegt werden

Wahrscheinlich bin ich momentan etwas durcheinander... Jedenfalls verstehe ich nicht, was du damit meinst... Einfach die Variablen als globale Variablen Deklarieren?

[mael]

Zitat:

Zitat von Nicolai1605

Zitat:

Zitat von SirThornberry

die function als methode zu nutzen, und dann

Delphi-Quellcode:

var D:array[0..255,0..255] of integer;

im private zu definieren. Damit müsste nicht jedes mal speicher dafür angelegt werden

Wahrscheinlich bin ich momentan etwas durcheinander... Jedenfalls verstehe ich nicht, was du damit meinst... Einfach die Variablen als globale Variablen Deklarieren?

Er meint die Variable D in den private-Abschnitt einer Klasse verschieben (z.B. den private-Bereich von TForm1). Die Funktion müßte dann zur Methode "function TForm1.Levenshtein" werden um auf die Variable D zugreifen zu können.

Zu den Eingabedaten:
Hmm, das ist leider relativ allgemein, vielleicht kann man irgendwie ausnutzen, daß der erste String mit allen nachfolgenden Strings verglichen wird, also über "längere Zeit gleich bleibt".
Irgendwie läßt sich vielleicht dadurch etwas initialisieren und die Schleife vereinfachen.
Dafür muß ich den Algo aber erst mal genau untersuchen...

[Flocke]

Zitat:

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.

[Nicolai1234]

Also ich habe jetzt erstmal die oben genannten Änderungen eingebaut. Jetzt führt er pro Sekunde die Funktion 20.000 mal aus. Das ist schon recht ordentlich, wenn auch keine große Steigerung.

[Chewie]

Wenn es des Programm erlaubt, könnte man durch Einsatz eines Multiprozessor-Systems die Leistungsfähigkeit vervielfachen, wenn man schon nichts mehr am Algorithmus verbessern kann.

[stoxx]

Zitat:

Nun geht es darum, selbe Titel zu finden (3. Spalte (durch Tilde getrennt)).
Es handelt sich dabei um ca. 6000 Zeilen.

Augerufen wird die Funktion mit jedem der 6000 Titel, da er jeden Titel mit jedem wieder vergleicht.

Genau das ist das Problem, bei diesem "naiven" Algorithmus.
Der Weg wäre, dass Du Deine Textdatei aufbereitest.
Lösungen würde Dir wahrscheinlich die Bioinformatik liefern. Aber mit 16, könnte ich mir das arg schwierig für Dich vorstellen.
Suffix Trees sind Deine ersten Stichworte für google ...

vlg stoxx

[glkgereon]

Man müsste auch nicht jedes mit jedem vergleichen (6000 * 6000) sondern könnte bereits verglichene rausnehmen, und damit nur die Hälfte durchlaufen müssen (6000*3000).
und das macht schon mal eine ganze menge^^

[Nicolai1234]

Zitat:

Zitat von glkgereon

Man müsste auch nicht jedes mit jedem vergleichen (6000 * 6000) sondern könnte bereits verglichene rausnehmen, und damit nur die Hälfte durchlaufen müssen (6000*3000).
und das macht schon mal eine ganze menge^^

Hehe, das mache ich sogar^^

Zitat:

Lösungen würde Dir wahrscheinlich die Bioinformatik liefern. Aber mit 16, könnte ich mir das arg schwierig für Dich vorstellen.
Suffix Trees sind Deine ersten Stichworte für google ...

MAch das mal nicht vom Alter abhängig. Ich wäre trotzdem über Hilfe dankbar...

[glkgereon]

Zitat:

Zitat von Nicolai1605

Zitat:

Zitat von glkgereon

Man müsste auch nicht jedes mit jedem vergleichen (6000 * 6000) sondern könnte bereits verglichene rausnehmen, und damit nur die Hälfte durchlaufen müssen (6000*3000).
und das macht schon mal eine ganze menge^^

Hehe, das mache ich sogar^^

Ja, ich hatte mich schon gewundert das du es nicht machst...hatte dich wohl mist-verstanden^^

kannst du denn nicht vorher schon was filtern?
zum beispiel könnte man eventuell ganz grob nach der länge gucken, da diese ja sehr unterschiedlich zu sein scheint...

[negaH]

Der Hinweis von Stoxx ist schon richtig hat aber auch einen Hacken in deinem speziellen Fall.

Die Komplexität deiner Suche ist O(n^2) also ziemlich mies. Tries wiederum haben eine Komplexität vergleichbar mit binärer Suche von O(n*ln(n)) also schon viel viel besser.

Der Hacken an der Sache ist deine Levinstein Distanz, diese ist nämlich kontraher zu den auf exakter Suche basierenden Tries. Ich persönlich kenne keinen Trie der mit der Levinstein Distanz = also unscharferm Vergleich funktionieren würde. Tries sind auf exakte 1 zu 1 Vergleiche angewiesen.

Ein zweites Problem besteht darin das du deine DB aus der Textdatei in ein anderes Format bringen müsstest.

Es gibt aber noch andere Verfahren als die Levinstein Distanz. Essentiell ist es für dich wichtig einen dieser Algos auszuwählen die es ermöglichen offline deine 6000 Datensätze der DB vorrauszuberechnen und diese dann in einem Trie speichern zu können. Der Suchvergleich würde als erstes dein Suchwort ebenfalls, nun online, konvertieren und dann kannst du mit dem unscharfen Vergleich suchen.

Gruß Hagen

[Robert Marquardt]

Das mit der Laenge ist eine offensichtliche Optimierung.
Also nicht Prozentzahlen liefern, die sowieso ungenau sind, sondern eine Mindestaehnlichkeit mit in die Funktion geben.
Unterscheiden sich die Wortlaengen um mehr als diese Mindestaehnlichkeit, so kann man sich weitere Pruefungen sparen.
Das funktinoiert allerdings nur wenn das Kosteninkrement immer 1 ist.

[negaH]

Also fragen wir uns was macht die Levenshtein Distanz ?

Sie berechnet die Anzahl der nötigen Editierungen zwischen String A und B, also wieviele Editierungen sind nötig um vom String a zu b zu kommen. Das ist IDEAL für uns ;)

Du hast eine DB mit 6000 Titeln und möchtest sehr sehr schnell ein Suchtitel mit diesen vergleichen. Zur Zeit vergleichst du also Suchtitel A mit 6000 B's.

Dazu erechnest du LevD(Suchttitel, 6000* DBTitel) korekt ?

Was wäre wenn du aber einen "Zwischenschritt" einbaust. Angenommen die Titel in der DB haben maximale Länge 60 Zeichen. Du erzeugst nun eine DB mit der Levenshtein-Distanz von dem 60 Zeichen Wort "AAAAAAAAAA.." zu den Titeln. Wir erzeuigen also X = LevD(DBTitel, "AAAAAAAAA...") und speichert diese Zahl in der DB. Die DB wird sortiert nach diesem Wert.

Bei der Suche vom Titel, zb. "Test" erzeugst du die Distanz mit Y = LevD("AAAAAAAAAAA", "Test"); und suchst in der DB per binärer Suche den Wert X - Y = 0.

Der Trick ist also LevD(A, B) = LevD(A, C) - LevD(B, C).
X = LevD(A, C) kann offline für jeden Titel A mit dem festen Wert C erfolgen. Die DB kann sortiert werden nach X.
Y = LevD(B, C) wird online zur Suche erzeugt und Y kann nun per schneller binärer Suche in der DB per Vergleich zu X gesucht werden.

Probier mal ob das so geht, ist nur so eine Idee von mir.

Gruß Hagen

[glkgereon]

hmm...
wenn ich das richtig verstanden habe hört sich das gut an.

Du willst also einen "Referenzwert" erstellen ("AAA...") und alle Werte mit diesem vergleichen, und diesen Wert zwischenspeichern.
Dann müsste man nur noch, wie bisher, die bereits berechneten Werte vergleichen, was um ein vielfaches schneller wäre.

war das deine idee?

[stoxx]

Zitat:

Der Trick ist also LevD(A, B) = LevD(A, C) - LevD(B, C).

Hallo Hagen, das kann aber nicht ganz stimmen.

a := 'AAAAAB';
b := 'AAAAAC';
c := 'AAAAAA';

LevD(A,B) = 1;
LevD(A,C) = 1;
LevD(B,C) = 1;

LevD(A,B) <> LevD(A, C) - LevD(B, C)

1 <> 1 - 1
1 <> 0

Suffix Tries sind wie Du schon richtig sagst, nur zur exakten Stringgsuche geeignet, ich bin auf dem Gebiet leider noch nicht so fit, ich weiß aber, dass die Bioinformatik auch Algorithmen zur unscharfen Suche benötigt und verwendet.

[Nicolai1234]

Danke erstml für die Tipps.
Gibt es eigentlich noch andere Algorithmen mit denen man diese Aufgabe erledigen könnte? Oder ist die Levenshtein-Distanz schon das "Optimum"?

[marabu]

Hallo Nicolai,

Zitat:

Zitat von Nicolai1605

Gibt es eigentlich noch andere Algorithmen mit denen man diese Aufgabe erledigen könnte? Oder ist die Levenshtein-Distanz schon das "Optimum"?

die Levenshtein-Distanz (LevD) ist die Edit-Distanz-Metrik schlechthin. Die Frage ist nur, ob es das ist, was du brauchst. Um das zu entscheiden ist deine Problembeschreibung noch zu dürftig. Werden da Schreibfehler gesucht? Sind die Texte ein OCR-Produkt? Kurz, wie enstehen die Daten? LevD liefert dir Gleichheit durch Ähnlichkeit bei frei wählbarer Schranke. Welche Aktionen sollen dadurch begründet werden?

Text-Ähnlichkeit ist ein Forschungsgebiet der KI. Die Algorithmen werden von Computer-Linguisten zur Analyse von geschriebenen Sprachen verwendet.

Ein Link der jede Menge Stichwörter zum Weitersuchen bringen könnte: klick

Grüße vom marabu

[Nicolai1234]

Zitat:

Zitat von marabu

Werden da Schreibfehler gesucht? Sind die Texte ein OCR-Produkt? Kurz, wie enstehen die Daten? LevD liefert dir Gleichheit durch Ähnlichkeit bei frei wählbarer Schranke. Welche Aktionen sollen dadurch begründet werden?

Die Daten werden von Menschen manuell eingegeben. In diesem Fall sind es die Autoren selber, die ihre Buchtitel etc. eingeben. Das Programm hat dann die Aufgabe doppelte Einträge zu finden, falls ein Autor sein Buch zweimal (in ähnlicher Schreibweise) eingegeben hat oder falls 2 Autoren den selben Titel eingeben. (es ist durchaus so, dass diese Menschen versuchen, das System bewusst zu betrügen. Klingt seltsam, ist aber wahr) Also kann man nicht auf das bessere Verhalten bei den Eingaben hoffen^^

[glkgereon]

Dann scheint diese Methode sinnvoll zu sein.

Müssen diese 12 Millionen mal denn "immer" d.h. regeläßig durchlaufen werden?

vielleicht wäre es eine Überlegung wert, es einfach so zu lassen, falls das nur einmal der Fall wäre, und danach immer nur einmal alle^^

[alzaimar]

Noch ein Tip, sogar ganz in der Nähe ...
http://www.delphipraxis.net/internal...ct.php?t=51913
Das sieht doch ganz gut aus...

[stoxx]

also ich hätte da noch eine Idee.
Ähnlichkeiten heißen ja in Deinem Fall, dass einzelne Wörter komplett gleich sind. Nur etwas anders dargestellt, einmal mit Leerzeichen einmal hinten, einmal vorne.
Deshalb folgender Vorschlag.

1. den Suchstring teilst Du in einzelne Wörter auf
2. diese Worter suchst Du einzeln hintereinander in der Textdatei, und zwar auf exaktes Vorkommen.
3. Du überprüfst nur die Zeilen auf die Levenstein Distanz, wo die Wörter vorkommen. ( ich würde mit dem Wort anfangen, dass die wenigsten Vorkommen liefert und nur bis zu einer bestimmten Anzahl)

der 2. Schritt klingt zunächst kompliziert, ist aber über diese Suffix Trees lösbar und schnell realisierbar.
(eine Suchanfrage bei google hängt ja auch nicht von der Größe des Internets ab)

[Phoenix]

Also für eine einmalige Bereinigung der Datenbank von doubletten ist das imho nicht so performance-Kritisch.

Wichtig wäre, bei der Eingabe eines neuen Titels diesen direkt nach der Eingabe gegen die bestehende Datenbank zu prüfen. Ist es eine doublette wird der Eintrag verweigert oder der Eintrag gleich intern als Doublette markiert und kann dann vor der nächsten komplett-Bereinigung einfacher entfernt werden. Vor allem muss in diesem Fall ja nur ein einzelner Eintrag gegen die DB verglichen werden und nicht gleich alle miteinander.

[Nicolai1234]

Zitat:

Zitat von Phoenix

Also für eine einmalige Bereinigung der Datenbank von doubletten ist das imho nicht so performance-Kritisch.

Wichtig wäre, bei der Eingabe eines neuen Titels diesen direkt nach der Eingabe gegen die bestehende Datenbank zu prüfen. Ist es eine doublette wird der Eintrag verweigert oder der Eintrag gleich intern als Doublette markiert und kann dann vor der nächsten komplett-Bereinigung einfacher entfernt werden. Vor allem muss in diesem Fall ja nur ein einzelner Eintrag gegen die DB verglichen werden und nicht gleich alle miteinander.

Das ist leider aus diversen Gründen nicht möglich. Die Eingaben müssen alle auf einmal überprüft werden.

[stoxx]

Zitat:

Zitat von Nicolai1605

Das ist leider aus diversen Gründen nicht möglich. Die Eingaben müssen alle auf einmal überprüft werden.

von meiner Idee hälst Du wohl nix ? durchdenke das nochmal ! ;-)
Ich denke, so würde das richtig gut funktionieren.
Also nur die Zeilen zu prüfen, wo überhaupt die Wörter vorkommen.
Das Wort "Lärmwirkungsforschung" kommt vielleicht nur in einer einzigen Zeile vor, also brauchst Du den aktuell durchlaufenen Eintrag nur mit dieser einzigen Zeile überprüfen, ob sie ähnlich ist, nicht mit allen Zeilen.
Das war die Idee dahinter..

[Nicolai1234]

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

[stoxx]

Zitat:

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.