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 1 von 4  1 23     Letzte » 
Nicolai1234

Registriert seit: 21. Feb 2004
1.008 Beiträge
 
Turbo Delphi für Win32
 
#1

Levenshtein-Distanz

  Alt 11. Dez 2005, 00:22
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
  Mit Zitat antworten Zitat
Benutzerbild von mael
mael

Registriert seit: 13. Jan 2005
391 Beiträge
 
Delphi XE3 Professional
 
#2

Re: Levenshtein-Distanz

  Alt 11. Dez 2005, 01:47
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.
HxD, schneller Hexeditor:
http://mh-nexus.de/hxd
  Mit Zitat antworten Zitat
Benutzerbild von Flocke
Flocke

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

Re: Levenshtein-Distanz

  Alt 11. Dez 2005, 02:35
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.
Volker
Besucht meine Garage
Aktuell: RtfLabel 1.3d, PrintToFile 1.4
  Mit Zitat antworten Zitat
Robert Marquardt
(Gast)

n/a Beiträge
 
#4

Re: Levenshtein-Distanz

  Alt 11. Dez 2005, 06:46
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.
  Mit Zitat antworten Zitat
Nicolai1234

Registriert seit: 21. Feb 2004
1.008 Beiträge
 
Turbo Delphi für Win32
 
#5

Re: Levenshtein-Distanz

  Alt 11. Dez 2005, 11:26
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
  Mit Zitat antworten Zitat
Benutzerbild von SirThornberry
SirThornberry
(Moderator)

Registriert seit: 23. Sep 2003
Ort: Bockwen
12.235 Beiträge
 
Delphi 2006 Professional
 
#6

Re: Levenshtein-Distanz

  Alt 11. Dez 2005, 11:44
eventuell würde es schon etwas bringen die function als methode zu nutzen, und dann
var D:array[0..255,0..255] of integer; im private zu definieren. Damit müsste nicht jedes mal speicher dafür angelegt werden
Jens
Mit Source ist es wie mit Kunst - Hauptsache der Künstler versteht's
  Mit Zitat antworten Zitat
Nicolai1234

Registriert seit: 21. Feb 2004
1.008 Beiträge
 
Turbo Delphi für Win32
 
#7

Re: Levenshtein-Distanz

  Alt 11. Dez 2005, 12:08
Zitat von SirThornberry:
eventuell würde es schon etwas bringen die function als methode zu nutzen, und dann
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?
  Mit Zitat antworten Zitat
Benutzerbild von mael
mael

Registriert seit: 13. Jan 2005
391 Beiträge
 
Delphi XE3 Professional
 
#8

Re: Levenshtein-Distanz

  Alt 11. Dez 2005, 12:38
Zitat von Nicolai1605:
Zitat von SirThornberry:
die function als methode zu nutzen, und dann
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...
HxD, schneller Hexeditor:
http://mh-nexus.de/hxd
  Mit Zitat antworten Zitat
Benutzerbild von Flocke
Flocke

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

Re: Levenshtein-Distanz

  Alt 11. Dez 2005, 13:22
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.
Volker
Besucht meine Garage
Aktuell: RtfLabel 1.3d, PrintToFile 1.4
  Mit Zitat antworten Zitat
Nicolai1234

Registriert seit: 21. Feb 2004
1.008 Beiträge
 
Turbo Delphi für Win32
 
#10

Re: Levenshtein-Distanz

  Alt 11. Dez 2005, 17:29
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.
  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 12:18 Uhr.
Powered by vBulletin® Copyright ©2000 - 2023, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2021 by Daniel R. Wolf