PHP-Klasse für das Erstellen von Hashes nach der Kölner Phonetik
Einer unserer Kunden hatte einen besonderen Wunsch für den Relaunch. Er wollte eine intelligente Suche in die Webseite integriert haben. Allzu häufig hatten Besucher Probleme Autoren oder Buchtitel zu finden, weil sie den genauen Namen nicht kannten.
Es gibt zahlreiche Verfahren für eine Unscharfe-Suche. Viele eignen sich nicht für Shops, Sammlungen oder andere kleine Datenbanken. Suchmaschinen können z.B. auf riesige Datenmengen zugreifen und mit Häufigkeiten oder alternativen Schreibweisen arbeiten. Andere Verfahren, bei denen Abweichung bzw. Unterschiede heuristisch verglichen werden (z.B. Levenshtein), sind sehr rechenaufwendig.
Am ehestem eignen sich Verfahren, bei denen der Text in Phoneme gewandelt und dann eine Kennzahl oder Schlüssel (hash) gebildet wird. PHP hat mit (soundex und methaphone) bereits Funktionen für Ermittlung von Phonemschlüsseln eingebaut. Wir haben uns letztendlich für den Algorithmus des Kölner Modells entschieden, da er mit Umlauten keine Probleme hat und Eigenschaften der deutschen Sprache besser abbildet.
Unsere Phoneme-Klasse ist einfach und auf Geschwindigkeit hin optimiert. Sie gibt für Worte Integerwerte zurück. Zum Beispiel 66832 für Mannschaft und 668326 für Mannschaften. Zu kurze Worte werden ignoriert.
Wie implementieren?
Es sollte einleuchten, dass man nicht erst beim Ausführen der Suche beginnt die Schlüssel zu bilden. Wir speichern alle Schlüssel der Buchtitel und Autorennamen in Hashtabellen ab, wenn die Daten angelegt werden. Nun müssen wir nur den Suchtext in Worte zerlegen und in den Tabellen nach Übereinstimmungen suchen. Da die Schlüssel aus Integerwerten bestehen, die in den Hashtabellen indiziert sind, ist das Verfahren gnadenlos schnell.
An der Schnellsuche oben auf www.gmeiner-verlag.de kann man die Routine in Aktion testen. Dabei wird man vielleicht merken, dass Worte angezeigt werden, die scheinbar überhaupt nicht mit dem Begriff übereinstimmen. Das liegt zum einen daran, dass zuerst auch klassisch in Untertiteln und anderen Quellen gesucht wird. Zum anderen können gerade kurze Worte bei so einem einfachen Verfahren den gleichen Schlüssel haben. Das Ergebnis wird außerdem um so präziser je vollständiger das Wort ist. Der Effekt tritt auf, weil wir uns entschieden haben nur nach Deckungsgleichheit zu suchen. Bei einem Schlüssel von 123 werden keine Ergebnisse angezeigt, die mit 123 beginnen.
Der Code
Interessierte können den kompletten Code als Open Source hier » downloaden. Das Paket besteht aus einer statischen PHP-Klasse "phonemes" und einem Beispiel.
/** * @file phonemes.php * * Berechnung des phonetischen Hashes nach dem Modell der Kölner Phonetik * Rewrite der Variante von Nicolas Zimmer * http://de.wikipedia.org/wiki/Kölner_Phonetik * * @package gmeiner - http://www.feenders.de * @copyright Copyright (C) Computer - Daten - Netze : Feenders * @license GNU/GPL, see LICENSE * @created 24.01.14 * @version 1.0 * @author Dirk Hoeschen (hoeschen at feenders.de) */ class phonemes { //Ausnahmeregeln static $eLeading = array("ca" => 4, "ch" => 4, "ck" => 4, "cl" => 4, "co" => 4, "cq" => 4, "cu" => 4, "cx" => 4, "dc" => 8, "ds" => 8, "dz" => 8, "tc" => 8, "ts" => 8, "tz" => 8); static $eFollow = array("sc", "zc", "cx", "kx", "qx"); //Kodierungstabelle static $codingTable = array("a" => 0, "e" => 0, "i" => 0, "j" => 0, "o" => 0, "u" => 0, "y" => 0, "b" => 1, "p" => 1, "d" => 2, "t" => 2, "f" => 3, "v" => 3, "w" => 3, "g" => 4, "k" => 4, "q" => 4, "x" => 48, "l" => 5, "m" => 6, "n" => 6, "r" => 7, "c" => 8, "s" => 8, "z" => 8); /** * Erzeuge Hashwerte für einen String und trage sie in ein Array ein * * @param string $text * @return array format $[word]=>hashvalue * @access public */ public static function getHashesFromString($text) { $text = str_replace("-", " ", $text); $words = preg_split("/ /", trim($text)); $hashes = array(); if (count($words) >= 1) { foreach ($words AS $word) { $word = self::cleanString($word); if (!empty($word) AND strlen($word) > 3) { $hashes[$word] = self::getCologneHash($word); } } } return $hashes; } /** * Konvertiert einen String in ASCII zahlen und ziffern * @param string $word * @return string mixed * @access public */ public static function cleanString($word) { $word = mb_strtolower($word); // Umwandlung: v->f, w->f, j->i, y->i, ph->f, ä->a, ö->o, ü->u, ß->ss, é->e, è->e, ê->e, à->a, á->a, â->a, ë->e $word = str_replace(array("ç","v","w","j","y","ph","ä","ö","ü","ß","é","è","ê","à","á","â","ë"), array("c","f","f","i","i","f","a","o","u","ss","e","e","e","a","a","a","e"), $word); // Nur Buchstaben (keine Zahlen, keine Sonderzeichen) $word = preg_replace('/[^a-z]/', '', $word); return $word; } /** * Berechnung des phonetischen Hashes nach dem Modell der Kölner Phonetik * * @param string $word string to be analyzed * @return string $value represents the Kölner Phonetik value * @access public */ public static function getCologneHash($word) { if (empty($word)) return false; $len = strlen($word); $value = array(); for ($i = 0; $i < $len; $i++) { // ausnahmen if ($i == 0 && $word[$i] . $word[$i + 1] == "cr") { $value[$i] = 4; } if (isset($word[$i + 1]) && isset(self::$eLeading[$word[$i] . $word[$i + 1]])) { $value[$i] = self::$eLeading[$word[$i] . $word[$i + 1]]; } if ($i != 0 && (in_array($word[$i - 1] . $word[$i], self::$eFollow))) { $value[$i] = 8; } // normales encoding if (!isset($value[$i])) { if (isset(self::$codingTable[$word[$i]])) { $value[$i] = self::$codingTable[$word[$i]]; } } } // nullen entfernen $codes = array_shift($value); foreach ($value AS $code) { if ($code != 0 ) { $codes .= $code; } } // doppelte werte entfernen return preg_replace("/(.)\\1+/", "\\1", $codes); }