Archive for the ‘String Ähnlichkeit’ tag
„Meinten Sie“: Eingaben verbessern mit levenshtein() und soundex()
Wer kennt es nicht: Wenn man in ein Suchfeld einen Suchbegriff eingibt, sich dabei jedoch vertippt oder es keine Suchergebnisse gibt, bekommt man manchmal einen alternativen Suchenbegriff vorgeschlagen, der mehr Ergebnisse liefert oder den falsch eingegebenen Begriff berichtigt. „Meinten Sie vielleicht“ oder „Did you mean“.
Doch wie funktioniert das?
Am einfachsten erledigt man diese Aufgabe mit der PHP-Funktion simliar_text() . Dieser Funktion übergibt man 2 Strings und erhält einen Ähnlichkeitswert, der die Anzahl der gleichen Buchstaben beschreibt. Alternativ kann man auch einen Prozentwert erhalten. Problem bei dieser Funktion: Sie ist langsam, die Laufzeit ist kubisch (n³).
Die aktuellere Funktion heißt levenshtein() und berechnet die Levenshtein-Distanz. Diese Distanz ist die minimale Anzahl an Einfüge-, Lösch- und Tausch-Operationen, um einen String in einen anderen zu verwandeln. Die Laufzeit dieser Funktion ist quadratisch (n²), allerdings gibt es auch Probleme: Es werden nur Strings mit maximal 255 Zeichen unterstützt. Falls auch längere Strings verglichen werden sollen, empfehle ich die Kommentare auf der PHP-Seite, denn dort stehen Quelltexte zum Nachbauen der Levenshtein-Distanz in PHP ohne diese Beschränkung, dort steht auch die Berechnung der prozentualen Gleichheit. Man sollte sich allerdings im Klaren sein, dass PHP-Code natürlich langsamer ist als die native PHP-C-Funktion.
Die levenshtein()-Funktion ist übrigens case-sensitiv, man sollte also überlegen die Parameter vorher in Kleinbuchstaben umzuwandeln (strtolower()).
Um noch bessere Ergebnisse oder Performance zu erhalten kann man auch die folgenden Funktionen hinzuziehen:
- soundex() – Berechnung der Laut-Ähnlichkeit eines Strings. Mit Hilfe dieser Funktion kann man also bestimmen, ob sich 2 Worte ähnlich anhören! Für die deutsche Sprache ist die Funktion nicht ideal, in den Kommentaren stehen Verbesserungen und Alternativen. Ausprobieren!
- metaphone() – Tut das selbe wie soundex(), doch kennt diese Funktion die Besonderheiten der englischen Aussprache. Besser ist jedoch DoubleMetaPhone, zu finden in den Kommentaren (lieber die PECL-Extension nutzen als die PHP-Klasse, um Performance zu steigern).
- Die MySQL-Funktionen SOUNDEX() und „SOUNDS LIKE„, mit denen man die Berechnung der Datenbank überlassen kann.
Tolle Möglichkeiten, seine Suche zu verbessern und „fuzzy-like“ zu machen. Einziges Problem ist die Performance.
