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.