Ähnlichkeitssuche für Arrays (Levenshtein)

[Enrico]

Hallo,

Ich möchte mich intensiv mit dem Thema "Ähnlichkeitssuche" beschäftigen und bin dabei auf den Levenshtein-Algorithmus gestossen, der Ähnlichkeiten beliebiger Strings berechnen kann.

Was ich allerdings nicht verstehe, ist folgendes:

Vergleich 'a' mit 'a'  = Ergebnis 0 (Übereinstimmung)
Vergleich 'a' mit 'b'  = Ergebnis 1 (Abweichung um 1)
Vergleich 'a' mit 'c'  = Ergebnis 1 (Abweichung um 1)
Vergleich 'a' mit 'cc' = Ergebnis 2 (Abweichung um 2)

Was sagt mir die Abweichung nun genau aus ?

Ich dachte mir, dass hier die Abweichung im Alphabet gemeint ist.

Enrico

[Cheatah]

Hi,

Was sagt mir die Abweichung nun genau aus ?

komisch. Ich habe Google mit "Levenshtein" gefüttert und wurde bereits beim ersten Link fündig. Gab es bei Dir andere Ergebnisse?

Ich dachte mir, dass hier die Abweichung im Alphabet gemeint ist.

Wie ähnlich sind sich "a" und "ä"? Oder "i" und "y"?

Cheatah

P.S.: Wo genau siehst Du eigentlich den Zusammenhang zwischen einem speziellen Algorithmus und einer speziellen Sprache?

[Enrico]

Hallo Cheatah,

Is ja jut :o)

Hab dann kurz darauf herausgefunden, dass der Wert besagt, wie viele Vorgänge notwendig sind, um einen String in einen anderen umzuwandeln.

Wie könnte man da nun aufbauen, um u.U. auch falsch geschriebene Wörter (sei es absichtlich oder unabsichtlich) herauszufinden, d.h. bei welchem Wert der Abweichung sollte man die Grenze setzen ?

Einen entsprechenden Code zur Berechnung der Abweichung habe ich bereits. Mir geht es jetzt nur noch darum, die "Gierigkeit" des Skriptes einzuschränken.

Enrico

[Cheatah]

Hi,

Wie könnte man da nun aufbauen, um u.U. auch falsch geschriebene Wörter (sei es absichtlich oder unabsichtlich) herauszufinden, d.h. bei welchem Wert der Abweichung sollte man die Grenze setzen ?

das hängt von vielen Faktoren ab; und möglicherweise ist dazu auch mehr als nur ein Wert (bzw. Algorithmus) nötig. Als erstes: Woher weißt Du eigentlich, mit welchem Wort Du vergleichen musst? Wie falsch ist beispielsweise der Satz "Mir fehlen die Wirte"[1]?

Einen entsprechenden Code zur Berechnung der Abweichung habe ich bereits. Mir geht es jetzt nur noch darum, die "Gierigkeit" des Skriptes einzuschränken.

Wie bewertest Du den Unterschied zwischen "Haus" und "haus"? Zwischen "Weg" und "weg"? "Floß" und "floss"? "Wach-Stube" und "Wachs-Tube"? "Arbeiter" und "Abreiter"? Wie falsch darf man "Heizölrückstoßabdämpfung" schreiben? Wie falsch "Zytotoxizität"[2]?

Cheatah

[1] Ein typischer I/O-Error.
[2] Wichtig für jeden, der das letzte Wort[3] haben möchte.
[3] Laut Duden.