Teil 2: Fuzzy-Suche mit PHP
- Fuzzy-Suche mit PHP
- Teil 2: Fuzzy-Suche mit PHP
Levenshtein-Distanz Als Ergebnis der Levenshtein-Funktion wird Ihnen der Abstand zwischen zwei Werten zurückgeliefert. Ist dieser 0, so handelt es sich um den gleichen Begriff, bekommen Sie als Ergebnis -1 zurückgeliefert, ist mindestens eine der beiden Zeichenketten über 255 Zeichen lang....
Levenshtein-Distanz
Als Ergebnis der Levenshtein-Funktion wird Ihnen der Abstand zwischen zwei Werten zurückgeliefert. Ist dieser 0, so handelt es sich um den gleichen Begriff, bekommen Sie als Ergebnis -1 zurückgeliefert, ist mindestens eine der beiden Zeichenketten über 255 Zeichen lang.
Im Beispiel geben Sie einen Namen ein und die Liste vergleicht mit der Namensliste eines Arrays. Wird eine Ähnlichkeit festgestellt, so werden Sie darauf aufmerksam gemacht, ebenso bei einem Treffer.
Die Eingabe kommt wieder von einem einfach gehaltenen Formular und wird als wort1 übergeben. Im Beispiel findet ein Vergleich des eingegebenen Wortes gegen ein Array statt. Gewöhnlich wird dies eher eine Abfrage gegen einen Datenbankwert sein - die Abstraktion soll lediglich das Vorgehen in diesem Kontext verdeutlichen.
$torhueter = array('Kahn','Lehmann', 'Köpke','Immel', 'Schumacher','Maier','Hildebrand','Enke');
$kurz = -1;
foreach ($torhueter as $goalie) {
$lev = levenshtein($input, $goalie);
// Treffer???
if ($lev == 0) {
$treffer = $goalie;
$kurz = 0;
break;
}
if ($lev <= $kurz || $kurz < 0) {
$treffer = $goalie;
$kurz = $lev;
}
}Mithilfe der foreach-Schleife wird das Array schrittweise durchgegangen und ein Vergleich der Eingabe zum Begriff aus dem Array durchgeführt. Handelt es sich dabei um einen exakten Treffer, so wird der Variablen treffer der entsprechende Wert zugewiesen, die Hilfsvariable kurz auf null gesetzt und die Schleife verlassen.
Ansonsten wird überprüft, ob der zuvor ermittelte Wert der Hilfsvariable kurz kleiner ist als der jetzige Wert (genauere Übereinstimmung) und in diesem Fall der Wert des Arrays der Variablen treffer zugewiesen, die ermittelte Levenshtein-Distanz der Variablen kurz.
Übereinstimmung in Prozent
Gerade bei der Suche mit Suchstrings geben viele Suchmaschinen eine Trefferrelevanz aus. Dies können Sie beispielsweise an dem Übereinstimmungsgrad Ihres Suchstrings mit den Inhalten einer Webseite ermitteln. Bei diesem Vorgehen unterstützt Sie die PHP-Funktion similar_text().
Diese gibt es in zwei Varianten - die eine gibt Ihnen die Anzahl der gleichen Buchstaben, die andere die prozentuale Übereinstimmung an. Geben Sie lediglich die beiden Begriffe oder Sätze als Variablen mit, erhalten Sie die Anzahl der übereinstimmenden Zeichen als Ergebnis.
Nutzen Sie auch die dritte Variable, dann erhalten Sie darüber die prozentuale Übereinstimmung der beiden Zeichenketten. Das vorherige Beispiel ist für die Funktion similar_text() wie folgt anzupassen:
foreach ($torhueter as $goalie) {
similar_text($input, $goalie, $percent);
$percent = round($percent);
// Treffer???
if ($percent == 100) {
$treffer = $goalie;
$kurz = 0;
break;
}
if ($percent >= $kurz || $kurz < 0) {
$treffer = $goalie;
$kurz = $percent;
}
}Der Aufruf von similar_text erfolgt mit der Eingabe aus dem Formular und dem Wert aus dem Array. Der Rückgabewert in Prozent wird in die dritte Variable geschrieben. Da wir nur an ganzzahligen Werten interessiert sind, wird das Ergebnis im nächsten Schritt entsprechend auf- oder abgerundet. Entspricht der Wert einem Volltreffer - also 100 Prozent - wird die Suche abgebrochen und das Ergebnis in die Variable treffer geschrieben.
Ansonsten wird weitergesucht und bei einem besseren Ergebnis der bestmögliche Treffer bis zu diesem Zeitpunkt in der Variable treffer hinterlegt und die prozentuale Übereinstimmung der Variable kurz zugewiesen.
Laufzeiten
Damit haben Sie die notwendigen Grundlagen, um diese Suchfunktionen auch auf Inhalte Ihrer SQL-Datenbank anzuwenden. Ohne diese Funktionen wäre mit reinem SQL lediglich eine LIKE-Abfrage möglich, die jedoch bei Performanz und Effizienz weit hinter diesem Lösungsansatz steht.
Planen Sie jedoch, mit unserem Ansatz beispielsweise eine komplexere Suche über eine komplette Website zu implementieren, sind eine Reihe weiterer Vorarbeiten notwendig, da ansonsten auch die drei Funktionen schnell an die Grenzen ihrer Leistungsfähigkeit stoßen.
Fuzzy für komplette Websites
Einen interessanten Ansatz für dieses Problem beschreibt Adam Charnock in seinem Blog. Er geht dabei darauf ein, wie eine Fuzzy-Suche für eine komplette Wiki-Seite zu implementieren ist. Dabei filtert er als Erstes die entscheidenden Worte einer Webseite aus den Inhalten heraus - unter Nutzung eines Spiders - und legt diese inklusive soundex()-Wert in einer Datenbank ab.
In einem zweiten Schritt stellt er die Verbindung zwischen den Worten in der Datenbank und den Inhalten seiner Seiten dar. Wird nun nach einem Wort gesucht, wird als Erstes der Soundex-Wert ermittelt, dieser anschließend mit der Worttabelle und anschließend mit den zugehörigen Verlinkungen verglichen. So kann er nicht nur genaue, sondern auch etwas unschärfere Treffer liefen.
Interessant sind in diesem Zusammenhang vor allem die Skripte für den Spider und die Generierung der Wortliste aus einer HTML-Seite.
Den vollständigen Workshop finden Sie auf seinem Blog unter "fuzzy searching in php" .
