Fuzzy-Suche mit PHP

Erfolgreicher suchen

Inhalte auch finden, wenn der Suchbegriff nicht exakt passt: Mit Fuzzy-Technologien erzielen Ihre User bessere Trefferquoten und finden Ihren Content zuverlässiger.

Die Fuzzy-Logik ist seit Jahren eine beliebte Technologie, die in vielen elektronischen Geräten wie beispielsweise Waschmaschinen zum Einsatz kommt. Dort testet Fuzzy-Logik etwa die Verschmutzung von Kleidung, berechnet daraus die Laufzeit des Waschprogramms und hilft so, Energie zu sparen.Einen komplett anderen Einsatzzweck erfüllt Fuzzy bei der Bestimmung von Suchergebnissen. Hier unterstützt die Technik dabei, die besten Treffer auf Basis der Eingabe zu finden.

Sie erleben die Technologie im täglichen Einsatz, wenn Sie beispielsweise Google nutzen. Dort werden Sie - abhängig von Ihrer Eingabe - immer wieder gefragt: "Meinten Sie: ...?".

Fuzzy-Suche bietet eine technische Basis, eine bestimmte Zeichenkette in einer längeren Zeichenkette oder sogar in einem Text zu finden. Dabei wird jedoch kein genauer Vergleich der beiden Strings gemacht, sondern eine unscharfe Suche durchgeführt, die auch ähnlich klingende Worte finden soll. Damit können beispielsweise Tippfehler einfach eliminiert werden.

Mathematik

Dem Ganzen liegen komplexe mathematische Algorithmen zugrunde. Die beiden wichtigsten in diesem Zusammenhang sind der Soundex-Algorithmus für die englische Sprache und die Levenshtein-Distanz, die auch universeller eingesetzt werden kann. Die Levenshtein-Distanz definiert die minimale Anzahl an Schritten - Einfügen, Ersetzen, Löschen - um eine Zeichenkette in eine andere zu überführen. Folgende Schritte sind beispielsweise notwendig, um aus dem Torwart-Titan Kahn das Wort Kohle zu machen:

• 1. Ersetzen: Kahn - Kohn • 2. Ersetzen: Kohn - Kohl • 3. Einfügen: Kohl - Kohle

Damit beträgt die Levenshtein-Distanz also 3. Je niedriger diese Zahl, desto ähnlicher sind sich die beiden Worte. Die Haupteinsatzgebiete dieses Algorithmus sind zum einen Rechtschreibprüfungen, aber auch die Suche nach Dubletten, beispielsweise in Adressbeständen.

Eine Optimierung der Levenshtein-Distanz ist der Algorithmus von Damerau- Leveshtein. Dieser benötigt zum Erkennen von verdrehten Paaren nur einen Schritt und nicht wie bei der Levenshtein-Distanz 2. Die Distanz zwischen den beiden Worten Kahn und Kanh beträgt bei Levenshtein 2. Hier können Sie mit Damerau-Leveshtein einen Schritt sparen, denn die Distanz beträgt nur 1 und ist somit, abhängig von der Zeichenkette, bis zur Hälfte schneller.

Soundex-Algorithmus

Das zweite Verfahren, welches bei der Suche nach phonetisch ähnlich klingenden Begriffen eingesetzt wird, ist der Soundex-Algorithmus. Er wird vorrangig für die englische Sprache verwendet, bringt jedoch auch häufig im Deutschen brauchbare Ergebnisse.

Der Algorithmus wandelt ein Wort in eine Kombination aus einem Buchstaben und drei Ziffern um. Alle weiteren Informationen werden vernachlässigt. Gleiches gilt für die Vokale A, E, I, O und U sowie die Konsonanten H, W und Y und die Umlaute Ä, Ö und Ü. Das ß wird als einfaches S dargestellt. Lediglich beim ersten Buchstaben des Worts wird eine Ausnahme gemacht - siehe Beispiel weiter unten.

Das Wort Internet sieht nach der Verarbeitung wie folgt aus: Das I wird als Buchstabe gesetzt, das N wird zur 5, das T zur 3, das E verworfen und das R zur 6. Damit liefert Soundex als Ergebnis I536.

Ausnahmeregeln

Neben diesen Grundregeln gibt es noch eine Reihe zusätzlicher Bestimmungen, Beispiel Ferrari: • Doppelte Buchstaben sind wie ein einzelner zu behandeln. F - F E entfällt R - 6 R entfällt A entfällt R - 6 I entfällt • entfälltSind weniger als 3 Buchstaben vorhanden, werden die fehlenden Stellen mit null aufgefüllt, sodass Ferrari zu F660 wird. Sind zu viele Stellen vorhanden, wird, wie beim Beispiel Internet gesehen, der überflüssige Inhalt nach der dritten Stelle weggelassen. • Folgen in einem Wort zwei Buchstaben mit gleichem Wert aufeinander, also beispielsweise ein K auf ein C, so sind diese wie gleiche Buchstaben zu behandeln. So wird aus dem Co-Trainer der deutschen Nationalmannschaft Flick der Code F420. • Eine Ausnahme zu den Regeln 2 und 3 ist gegeben, falls diese beiden Konsonanten durch einen Vokal getrennt sind, wie bereits im Beispiel von Ferrari zu sehen war.

Umsetzung in PHP

Wenn Sie sich jetzt schon Sorgen gemacht haben, wie Sie diese doch nicht gerade einfachen Algorithmen in PHP umsetzen sollen, können wir Entwarnung geben. Da diese sehr häufig für die Suche in Verwendung sind, gibt es von beiden bereits eine Standard-Implementierung ab PHP3 beziehungsweise PHP4 für Levenshtein.

In einem ersten Beispiel werden mithilfe der soundex-Funktion zwei eingegebene Worte untersucht und das Ergebnis ausgegeben. Die HTML-Seite wurde so einfach wie möglich gehalten und ruft über ein <form> zwei Worte ab und übergibt diese an compare.php.

Innerhalb von compare.php werden die beiden übergebenen Werte wort1 und wort2 an zwei gleichnamige Variablen übergeben. Diese werden mithilfe der soundex()- Funktion miteinander verglichen:

Weisen die beiden Worte den gleichen soundex()-Wert auf, so sind Sie entweder gleich oder klingen ähnlich.