WOI-LevSearch
Die ungenaue Suche mit Hilfe der Levenshtein-Distanz
Filemaker Add-On WOI-LevSearch
Die ungenaue Suche mit Hilfe der Levenshtein-Distanz
Die Levenshtein-Distanz zwischen zwei Zeichenketten ist die minimale Anzahl einfügender, löschender und ersetzender Operationen, um die erste Zeichenkette in die zweite umzuwandeln. Benannt ist die Distanz nach dem russischen Wissenschaftler Wladimir Lewenstein, der sie 1965 einführte.
Wir sehen an dem Ergebnis, dass der Name „Qoute“ in Verbindung mit dem Vornamen „Emil“ nicht zum gesuchten Namen „Woide“ passt.
Eingesetzt wird der Levenshtein-Algorithmus bei Google in der Suche und z.Bsp. auch bei WORD in der Fehlerkorrektur.
Vorab ein einfaches Beispiel mit dem Namen „Miller“, welches die Wirkungsweise anschaulich zeigt.
Wenn man genau diese Buchstabenreihenfolge im Suchfeld einer Datenbank eingibt, dann findet man auch den richtigen Datensatz. Man wird aber nicht den gesuchten Datensatz finden, wenn er unter dem falsch geschriebenen
Namen „Killer“ gespeichert ist.
Wenden wir jetzt die Levenshtein-Distanz an, so ergibt sich der Wert „1“, da genau eine Operation notwendig ist, um aus „Miller“ „Killer“ zu machen, nämlich das Ersetzen des Buchstaben „M“ durch „K“.
Für die ungenaue Suche bedeutet das, dass in jedem Datensatz für das Suchfeld die Levenshtein-Distanz ermittelt wird.
Ein zweites Beispiel verdeutlicht, wie sich das Verhalten des Suchergebnisses ändert, wenn die Vorgabe der Levenshtein-Distanz erhöht wird. Bleiben wir bei dem Beispiel „Miller“ und geben die Levenshtein-Distanz mit dem Wert „3“ vor.
Das bedeutet, dass wir alle Namen finden, die sich mit genau 3 Operationen erzeugen lassen, etwa „Mother“. Dieses Add-on setzt den Algorithmus so um, dass er für jede bestehende
FileMaker -Lösung nutzbar ist, ohne dass programmiert werden muss.
Zusätzlich wurde man die Möglichkeit geschaffen, den Algorithmus noch in einem zweiten Feld zu aktivieren.
Gibt man nun die Schärfe für die Levenshtein-Distanz mit „3“ vor, dann sieht das Ergebnis so aus:
Die Ergebnisse sind nicht automatisch Wahr oder Falsch. In unserem Beispiel sehen wir, dass bei „Woyde“ zwar der Vorname fehlt, die Schreibweise aber sowohl Wahr oder Falsch sein kann, denn der Namen „Woyde“ existiert real.
Aus diesem Grund habe ich mich entschlossen, die Levenshtein Distanz auch auf das zweite Feld anzuwenden. Damit bekommen wir diese Ergebnis:
Es gibt eine Erweiterung des Algorithmus’ von Levenshtein, der auch Buchstabendreher erkennt. So wird ein Dreher nur mit einer Operation bewertet, während der Original Algorithmus 2 Operationen benötigt.
Dieser Algorithmus hat den Namen Levenshtein-Damerau. Diese Erweiterung ist für die Praxis recht hilfreich, da Eingabedreher relativ häufig und schwer auffindbar sind.
Damit diese Ergebnisse in einem Add-on für beliebige Tabellen verfügbar sind, ist eine Parametertabelle vorgeschaltet, in der die notwendigen Angaben gemacht werden können.
