Thema: Delphi Levenshtein-Distanz

Einzelnen Beitrag anzeigen

Benutzerbild von negaH
negaH

Registriert seit: 25. Jun 2003
Ort: Thüringen
2.950 Beiträge
 
#18

Re: Levenshtein-Distanz

  Alt 12. Dez 2005, 10:30
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
  Mit Zitat antworten Zitat