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