Soundex
vs. Levenshtein
Tatsächlich sind diese Algorithmen keine
Alternative. Soundex beschreibt das Verfahren, das ähnlich
phonetische Wörter vergleicht, wogegen Levenshtein eine
Distanz zwischen zwei Strings berechnet.
Die Anwendung von Soundex besteht aus 2
Schritten: der Verschlüsselung des Strings und dem genauen
Match dieser Kodierung.
Dieses Verfahren teilt alle Strings in
Äquivalenz-Klassen, d.h. in separate Mengen von
Wörtern. Deshalb kann man jedes Wort finden, das sich in der
derselben Klasse befindet, aber kein Wort, das in einer
„ähnlichen“ Klasse ist, oder genauer: der
Soundex hat kein Konzept von „Nähe“.
Dagegen lässt der Levenshtein-Algorithmus
eine kontinuierliche Bewertung der Ähnlichkeit zweier
Wörter zu. Natürlich kostet das erheblichen
Rechenaufwand, während der Soundex eine extrem schnelle Suche
ermöglicht, indem einfach eine Hashtabelle generiert wird.
Bisher gelang nur der Firma Exorbyte eine
hochperformante Implementierung des
Levenshtein Algorithmus. Mit Exorbytes
Software kann die
Levenshtein Distanz auch bei Millionen von
Wörtern innerhalb von Millisekunden berechnet werden. Dies
erlaubt sogar interaktive
Suchanwendung basierend auf Ajax.
|
