PHP-Klasse für das Erstellen von Hashes nach der Kölner Phonetik

Einer unserer Kunden hatte einen besonderen Wusch 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 das Kölner Modells entschieden, da er mit Umlauten kein Probleme hat und Eigenschaften der Deutschen Sprache besser abbildet.

Phoneme

Unsere Phoneme-Klasse ist einfach und auf Geschwindigkeit hin optimiert. Sie gibt für Worte Intergerwerte zurück. Zum Beispiel 66832 für Mannschaft und 668326 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 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, "c" => 4, "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 &amp;&amp; $word[$i] . $word[$i + 1] == "cr") {
                $value[$i] = 4;
            }
            if (isset($word[$i + 1]) &amp;&amp; isset(self::$eLeading[$word[$i] . $word[$i + 1]])) {
                $value[$i] = self::$eLeading[$word[$i] . $word[$i + 1]];
            }
            if ($i != 0 &amp;&amp; (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);
    }
 

Referenz

Kommentar schreiben


Sicherheitscode
Aktualisieren