Erfolgreicher suchen

Teil 2: Fuzzy-Suche mit PHP

28.8.2008 von Redaktion pcmagazin

ca. 3:15 Min
Ratgeber
  1. Fuzzy-Suche mit PHP
  2. 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.

Fuzzy-Suche mit PHP
Wenn Sie eine prozentuale Übereinstimmung anzeigen möchten, bietet Ihnen similar_text die richtigen Möglichkeiten.
© Archiv

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.

Fuzzy-Suche mit PHP
Adam Charnock beschreibt, wie Sie Fuzzy für eine komplette Website verwenden können.
© Archiv

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" .

Mehr lesen

Chronologische Liste und Netflix-Links

Marvel-Filme- und -Serien: Das ist die richtige Reihenfolge

Neuerscheinungen in der Übersicht

Netflix: Neue Filme und Serien

Vorschau auf Film- und Serien-Highlights

Amazon Prime Video: Neuheiten

Weiter zur Startseite  

Mehr zum Thema

internet, webdesign, adobe,  Illustrator, CS6

Webdesign

Webdesign in Adobe Illustrator CS6

Adobe Illustrator wird im Webdesign immer beliebter. Wie Sie das Tool richtig einsetzen, erfahren Sie hier.

Facebook stellte die neue Suche

Facebook

Facebooks Social Graph Search

Was sind die Implikationen für Unternehmen und Endanwender bei Facebooks neuer Suche Graph Search?

Der BGH erklärt das Internet zur Lebensgrundlage.

Online-Recht

Darauf müssen Sie bei den AGB achten

Allgemeine Geschäftsbedingungen liest sich niemand gerne durch. Sie sind jedoch notwendig und äußerst sinnvoll. Worauf sie achten sollten.

Online-Urheberrecht: Unser Ratgeber bietet Tipps für das Cloud-Recht.

Online-Recht in der Cloud

Wie sieht das Urheberrecht in der Wolke aus?

Dateien werden immer häufiger in der Cloud bereitgestellt. Rechtlich ist das jedoch durchaus problematisch. Wir klären über das Urheberrecht in der…

Logistik im E-Commerce: Prozesse rund um die Logistik.

E-Commerce-Logistik

Logistik im E-Commerce

Für den Erfolg eines Online-Shops sind zahlreiche Faktoren verantwortlich. Neben Produktvielfalt und Darstellung der Waren gehört auch die Logistik.