in Programmierung

Ähnlichkeitssuche

In meinen Logfiles tauchen immer wieder Suchanfragen auf, die falsch geschrieben sind. Ein Beispiel: „Öhrenstöcker Straße“ anstatt von „Oehrenstöcker Straße“ oder „Lindenstrasse“ anstatt von „Lindenstraße“. Natürlich könnte ich die offensichtlichen „Verschreiber“ herausfiltern, aber sobald es zu Buchstabendrehern oder Vertippern kommt, hab ich ein Problem.

Gott sei Dank, kann man in MySQL ähnliche Werte in der Datenbank suchen. Dazu muss als erstes die Spalte, in der gesucht wird Volltext-Indiziert werden. Anschließend kann man mit den Ausdruck [cci lang=“mysql“]MATCH() AGAINST ()[/cci] suchen.

Bei mir sieht das dann ungefähr so aus:

[cc lang=“mysql“]
SELECT DISTINCT `name` AS `name` FROM `object`
WHERE MATCH(`name`) AGAINST (’suchstring‘);
[/cc]

Nun hatte ich das Problem, dass ich in mehreren Spalten unabhängig voneinander suchen muss. Daher jage je eine Suchanfrage über jede Spalte (durch [cci lang=“mysql“]LIMIT 0,3[/cci] kommen immer nur die drei wahrscheinlichsten Ergebnisse heraus). Am Ende will ich auch diese Ergebnisse noch einmal filtern. Dazu verwende ich die Funktion [cci lang=“php“]levenshtein();[/cci]. Mit ihr vergleiche ich alle Ergebnisse mit dem eingegebenen (fehlerhaften) String und gebe die drei Ergebnisse als „Meinten Sie evtl. das:“ zurück, deren Ergebnis am nächsten bei Null liegt.

[cc lang=“php“]
//$q = vorverarbeitete Suchanfrage
$didyoumean = array();
$result = mysql_query(„SELECT DISTINCT `name` AS `name` FROM `object` WHERE MATCH(`name`) AGAINST (‚$q‘) LIMIT 0,3″);
while($row = mysql_fetch_assoc($result))
$didyoumean[] = $row[’name‘];
// […] Das selbe nochmal für mehrere andere Spalten in unterschiedlichen Tabellen

$didyoumean2 = array(array(-1,““),array(-1,““),array(-1,““));
foreach($didyoumean as $d) {
$lev = levenshtein($q, $d);
//Was nicht passieren sollte:
if ($lev == 0) {
$didyoumean2[2] = $didyoumean2[1];
$didyoumean2[1] = $didyoumean2[0];
$didyoumean2[0] = array(0,$d);
}
elseif(($didyoumean2[0][0]==-1)||($didyoumean2[0][0]>$lev)) {
$didyoumean2[2] = $didyoumean2[1];
$didyoumean2[1] = $didyoumean2[0];
$didyoumean2[0] = array($lev,$d);
}
elseif(($didyoumean2[1][0]==-1)||($didyoumean2[1][0]>$lev)) {
$didyoumean2[2] = $didyoumean2[1];
$didyoumean2[1] = array($lev,$d);
}
elseif(($didyoumean2[2][0]==-1)||($didyoumean2[2][0]>$lev))
$didyoumean2[2] = array($lev,$d);
}
$didyoumean3 = array();
foreach($didyoumean2 as $d)
if($d[0]>=0)
$didyoumean3[] = $d[1];
if(count($didyoumean3)>0){
$return[‚didyoumean‘] = „Meinten Sie evtl.:

    „;
    foreach($didyoumean3 as $d)
    $return[‚didyoumean‘] .= „

  • $d
  • „;
    $return[‚didyoumean‘] .= „

„;
}
[/cc]
Mal schauen, ob die Nutzer es benutzen ;).