PHPGangsta - Der praktische PHP Blog

PHP Blog von PHPGangsta


„Meinten Sie“: Eingaben verbessern mit levenshtein() und soundex()

with 12 comments

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.

Written by Michael Kliewe

Januar 21st, 2010 at 8:52 am

12 Responses to '„Meinten Sie“: Eingaben verbessern mit levenshtein() und soundex()'

Subscribe to comments with RSS or TrackBack to '„Meinten Sie“: Eingaben verbessern mit levenshtein() und soundex()'.

  1. Ein weitere Möglichkeit ist Suchbegriffe per Enchant (http://de.php.net/enchant) od Pspell (http://de.php.net/pspell) zu korrigieren. Dann ist allerdings noch nicht sichergestellt, dass zu dem Begriff tatsächlich Suchergebnisse existieren.

    Der korrekte Weg wäre natürlich auf Basis vorhandener Daten mit Hilfe von Trigrams u. ä. sein eigenes Wörterbuch zu erstellen.

    Jan

    21 Jan 10 at 09:38

  2. Ein super Beitrag, danke für die Info! Kann ich bestimmt mal brauchen, hab mir zu dem Thema auch einen c’t Artikel aufgehoben!
    Tobi

    Tobi

    21 Jan 10 at 09:53

  3. Genau diese Funktionalität bietet die serverseitige JAVA Lösung namen SOLR welche auf der Apache Lucene aufbaut.

    http://lucene.apache.org/solr/

    Es gibt dort bereits fertige Klassen zum Ansteuern aus PHP heraus:

    http://wiki.apache.org/solr/SolPHP

    Außerdem sehr zu empfehlen der Artikel der IBM dazu :

    http://www.ibm.com/developerworks/opensource/library/os-php-apachesolr/

    DarkVamp

    21 Jan 10 at 11:28

  4. Aber wie bildest du die Wörter zum testen? Schon beim Bilden der Wörter könnte man ja eine Ähnlichkeit einfließen lassen, oder?

    David

    21 Jan 10 at 12:31

  5. Reztilhcs

    22 Jan 10 at 14:06

  6. @DarkVamp: Ja, ein Index-Server kann das natürlich auch, und wahrscheinlich auch besser und schneller, hätte ich wahrscheinlich nennen sollen, da hast du Recht. Wollte auch eigentlich nur diese eher unbekannten PHP-Funktionen (bzw. MySQL-Funktionen) vorstellen 😉

    @David: Kommt drauf an, wenn das Textfeld für einen Benutzernamen gedacht ist, ist die Menge der zu vergleichenden Worte halt die Benutzerliste. Je nachdem wofür man es braucht. Ähnliche Worte direkt mit abzuspeichern würde ich allerdings nicht bevorzugen.

    @Reztilhcs: Auch interessant, aber nur PHP4?

    Michael Kliewe

    22 Jan 10 at 14:53

  7. Übrigens hatte ich schonmal einen anderen Indexer (Lucene) vorgestellt, der auch „fuzzy-search“ beherrscht, und den man dann mit Zend_Search_Lucene befüllen und abfragen kann.

    https://www.phpgangsta.de/die-eigene-suchmaschine-in-php-leicht-gemacht-lucene

    http://lucene.apache.org/java/2_3_2/queryparsersyntax.html#Fuzzy%20Searches

    Michael Kliewe

    22 Jan 10 at 14:55

  8. […] PHP Gangsta hat einen Artikel über Suchbegriffs-Vorschläge geschrieben. Es wird erklärt, wie man so etwas in PHP umsetzt und viel wichtiger noch, wie man […]

  9. In meiner Erfahrung ist die MySQL-Funktion MATCH() AGAINST() für solche Zwecke optimal. Sie findet wie similar_text() ähnliche Texte/Worte (und manchmal auch total unähnliche) und ist dabei verdammt schnell.

    Um doppelte Sprüche zu finden mache ich eine Vorsortierung mittels MATCH-AGAINST und dann mit dem Rest (ca. 10-200 Ergebnisse von knapp 30.000) ein similar_text(). Damit fahre ich ganz gut und es ist relativ schnell.

    http://dev.mysql.com/doc/refman/5.1/en/fulltext-search.html

    Xian

    26 Jan 10 at 07:23

  10. Zumindest den Leventsheim-Abstand muss ich hier etwas relativieren. Also einmal ist die Laufzeit nicht O(n²), sondern O(n*m), was aber eigentlich wurscht ist, wenn man für n einfach das längere Wort nimmt. In dem Fall gilt O(n²) wieder.
    Diese Laufzeit gilt allerdings nur, wenn man bereits zwei konkrete Wörter vorliegen hat. Will man ähnliche Wörter zu einem Wort finden, muss man ja zusätzlich noch alle Kandidaten durchgehen, wodurch nochmal ein x dazu kommt, also eher O(n² * x) = O(x³).
    Auch das ist recht relativ: Ähnlichkeitsvergleiche sind immer doof, wenn man nicht auf „bekante Tippfehler“-Wörterbücher zurückgreift 😉

    KingCrunch

    26 Jan 10 at 13:19

  11. Die Laufzeit eines Algorithmus/Funktion wird immer nur durch einen Durchlauf bestimmt. Wenn der Programmierer meint, die Funktion selbst nochmal 10.000 fach aufzurufen macht das den Algorithmus selbst nicht langsamer.
    Aber in gewissem Sinne hast du Recht und nochmal betont, dass es nicht sonderlich gut ist, tausende oder Millionen Wörter mit diesen beiden Funktionen (simliar_text und levenshtein) zu vergleichen, da sie einfach zu langsam sind.

    Werde mir die Tage mal MATCH AGAINST näher anschauen, Danke für den Tip.

    Michael Kliewe

    26 Jan 10 at 13:57

  12. PHP Implementierung der Kölner Phonetik:

    http://www.x3m.ch/xlab/index.php/phonetik-fuer-die-deutsche-sprache.html

    (Die URL hat geändert. Siehe Kommentar von Reztilhcs, 22.01.2010)

    Andy Theiler

    10 Nov 10 at 10:49

Leave a Reply

You can add images to your comment by clicking here.