Levenshtein-Distanz

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