Fuzzy-Vergleiche

Das Suchen und Finden von Informationen ist wesentlicher Bestandteil vieler Webapplications und Webseiten. Wenn es sich bei den zu findenden Werten um exakte Größen wie Zahlen, Datum oder feste Begriffe handelt, ist das Suchen in einer Datenbank eine Kleinigkeit. Was aber, wenn die Begriffe schwammig oder in verschiedenen Konjungationen oder Deklinationen vorliegen können oder man Vertipper und Rechtschreibfehler verarbeiten möchte?

Bei einem solchen Problem, kommt die unscharfe Suche, die ‚Fuzzy-Suche‘, zum Einsatz. Für alle, die sich damit auseinandersetzen möchten, eine eigene unscharfe Suche entwickeln möchten, habe ich ein kleines Script geschrieben, um einen unscharfen Vergleich zweier Wörter durchführen zu können und damit die richtige Suchstrategie für die eigene Anwendung entwickeln zu können.

Das Script gibt es als PHP-File zum Download und als funktionstüchtige Version auf dieser Seite.

Hier die Funktionen im Einzelnen:

Soundex:
Die PHP-Funktion soundex() ist ein Algorithmus um die Lautähnlichkeit eines Wortes zu berechnen. Der Wert, den man erhält, besteht aus dem Anfangsbuchstaben des zu untersuchenden Wortes und drei Ziffern, unabhängig davon, wie lang das Wort ist. Die Funktion ist für die englische Sprache entwickelt, liefert aber auch für das Deutsche einigermaßen brauchbare Ergebnisse.

Kölner Phonetik:
Ist ebenfalls ein phonetischer Algorithmus, der allerdings für die deutsche Sprache konzipiert wurde. Im Gegensatz zu soundex ist seine Länge beliebig und wird ausschließlich aus Ziffern gebildet.

Similar Text:
Die PHP-Funktion similar_text() vergleicht zwei Strings miteinander, in meinem Beispielscript habe ich die Ausgabe als prozentualen Wert gewählt.

Levenshtein-Distanz:
Die PHP-Funktion levenshtein() berechnet, wie viele Schritte mit Löschen, Ersetzen oder Einfügen von Zeichen notwendig sind, um vom ersten String zum zweiten zu gelangen. Der Wert ist 0, wenn beide Strings gleich sind.

Porter-Stemmer:
Ein Porter-Stemmer ist ein Verfahren, um aus einem Wort die Normalform, den Wortstamm, abzuleiten. Es ist KEIN lexikalisches oder grammatikalisches Verfahren, deshalb ist das Ergebnis auch nur eine Näherung an den richtigen Grundstamm. Das Ergebnis benutzt man, um damit genauer Suchen zu können. Wenn jemand nach ‚Autos‘ sucht, aber in der DB nur ‚Auto‘ hinterlegt ist, kommt man mit dem Porter-Stemmer an die Grundform. Der hier verwendete Porter-Stemmer ist für die englische Sprache, für andere Sprachen findet man unter http://snowball.tartarus.org/ Stemmer, die in diesem Script verwendete PHP-Implementierung stammt von http://tartarus.org/~martin/PorterStemmer/.

Wie ich oben schon schrieb, dient dieses Script nur dazu, eine Suchstrategie für ein Vorhaben zu entwickeln, wie man vorgeht, muss man von Fall zu Fall entscheiden. Hier mal ein kurzes Beispiel:

Über das Input-Feld einer Webseite soll nach Städtenamen gesucht werden, mehrsprachige Eingaben sind zulässig. In dem DB-Table mit den Städtenamen speichert man nicht nur den eigentlichen Namen, sondern auch direkt den SoundEx-Wert. Der String aus dem Input-Feld wird in einen SoundEx-Wert gewandelt, mit dem man dann die DB durchsucht. So führt die Suche nach Moskau, Moskow, Moskwa, … zu einem Datensatz: ‚Moskau‘.

// Variablen
$com = filter_input(INPUT_GET, „com“, FILTER_SANITIZE_STRING);
$word1 = filter_input(INPUT_POST, „word1“, FILTER_SANITIZE_STRING);
$word2 = filter_input(INPUT_POST, „word2“, FILTER_SANITIZE_STRING);$query_string = $_SERVER[ ‚QUERY_STRING‘ ];
$query_string = ereg_replace(„com = compare“, „“, $query_string);

// Formular
echo “

Bitte geben Sie zwei Wörter ein. Nach dem Absenden des Formulars werden die Wörter auf Ähnlichkeit geprüft.

„;

if ($com == „compare“){
// SoundEx
echo “


Vergleich mit SoundEx:

„;
echo “

SoundEx-Wert Wort 1: “ . soundex($word1) . “

„;
echo “

SoundEx-Wert Wort 2: “ . soundex($word2) . “

„;
if (soundex($word1) == soundex($word2)) {
echo “

Die Wörter klingen ähnlich oder sind gleich.

„;
}
else {
echo “

Die beiden Wörter klingen nicht ähnlich.

„;
}

// Koelner Phonetik
echo “


Vergleich mit Kölner-Phonetik:

„;

/**
* A function for retrieving the Kölner Phonetik value of a string
*
* As described at http://de.wikipedia.org/wiki/Kölner_Phonetik
* Based on Hans Joachim Postel: Die Kölner Phonetik.
* Ein Verfahren zur Identifizierung von Personennamen auf der
* Grundlage der Gestaltanalyse.
* in: IBM-Nachrichten, 19. Jahrgang, 1969, S. 925-931
*
* This program is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, version 3.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* @package phonetics
* @version 1.0
* @link http://www.einfachmarke.de/development
* @license GPL 3.0
* @copyright 2008 by einfachmarke.de
* @author Nicolas Zimmer
*/

function cologne_phon($word){

/**
* @param string $word string to be analyzed
* @return string $value represents the Kšlner Phonetik value
* @access public
*/

//prepare for processing
$word=strtolower($word);
$substitution=array(„ä“=>“a“,“ö“=>“o“,“ü“=>“u“,“ß“=>“ss“,“ph“=>“f“);
foreach ($substitution as $letter=>$substitution) {
$word=str_replace($letter,$substitution,$word);
}

$len=strlen($word);

//Rule for exeptions
$exceptionsLeading=array(
4=>array(„ca“,“ch“,“ck“,“cl“,“co“,“cq“,“cu“,“cx“),
8=>array(„dc“,“ds“,“dz“,“tc“,“ts“,“tz“)
);

$exceptionsFollowing=array(„sc“,“zc“,“cx“,“kx“,“qx“);

//Table for coding
$codingTable=array(
0=>array(„a“,“e“,“i“,“j“,“o“,“u“,“y“),
1=>array(„b“,“p“),
2=>array(„d“,“t“),
3=>array(„f“,“v“,“w“),
4=>array(„c“,“g“,“k“,“q“),
48=>array(„x“),
5=>array(„l“),
6=>array(„m“,“n“),
7=>array(„r“),
8=>array(„c“,“s“,“z“),
);

for ($i=0;$i<$len;$i++){
$value[$i]=““;

//Exceptions
if ($i==0 AND $word[$i].$word[$i+1]==“cr“) $value[$i]=4; //cr is treated differently at the start only

foreach ($exceptionsLeading as $code=>$letters) {
if (in_array($word[$i].$word[$i+1],$letters))$value[$i]=$code;
}

if ($i!=0 AND (in_array($word[$i-1].$word[$i],$exceptionsFollowing))) $value[$i]=8;

//Normal encoding
if ($value[$i]==““){
foreach ($codingTable as $code=>$letters) {
if (in_array($word[$i],$letters))$value[$i]=$code;
}
}
}

//delete double values
$len=count($value);

for ($i=1;$i<$len;$i++){
if ($value[$i]==$value[$i-1]) $value[$i]=““;
}

//delete vocals
for ($i=1;$i>$len;$i++){//omitting first characer code and h
if ($value[$i]==0) $value[$i]=““;
}

$value=array_filter($value);
$value=implode(„“,$value);

return $value;
}

echo “

Kölner-Phonetik-Wert Wort 1: “ . cologne_phon($word1) . “

„;
echo “

Kölner-Phonetik-Wert Wort 2: “ . cologne_phon($word2) . “

„;

// Similar Text
echo “


Vergleich mit SimilarText:

„;
similar_text($word1, $word2, $percent);
echo “

Die Wörter sind zu “ . $percent . „% gleich.

„;

// Levenshtein-Distanz
echo “


Vergleich nach Levenshtein-Distanz:

„;
echo “

Der Abstand der Wörter beträgt “ . levenshtein($word1, $word2) . „.

„;

// Porter-Stemmer
echo “


Porter-Stemmer (Normalformreduktion)*:

„;

echo “

Wort 1: “ . PorterStemmer::Stem($word1) . “

„;
echo “

Wort 2: “ . PorterStemmer::Stem($word2) . “

„;

echo “

* Funktioniert hier nur mit englischen Wörtern.

„;
}

echo “


„;

/**
* Copyright (c) 2005 Richard Heyes (http://www.phpguru.org/)
*
* All rights reserved.
*
* This script is free software.
*/

/**
* PHP5 Implementation of the Porter Stemmer algorithm. Certain elements
* were borrowed from the (broken) implementation by Jon Abernathy.
*
* Usage:
*
* $stem = PorterStemmer::Stem($word);
*
* How easy is that?
*/

class PorterStemmer
{
/**
* Regex for matching a consonant
* @var string
*/
private static $regex_consonant = ‚(?:[bcdfghjklmnpqrstvwxz]|(?<=[aeiou])y|^y)‘;

/**
* Regex for matching a vowel
* @var string
*/
private static $regex_vowel = ‚(?:[aeiou]|(?

/**
* Stems a word. Simple huh?
*
* @param string $word Word to stem
* @return string Stemmed word
*/
public static function Stem($word)
{
if (strlen($word) <= 2) {
return $word;
}

$word = self::step1ab($word);
$word = self::step1c($word);
$word = self::step2($word);
$word = self::step3($word);
$word = self::step4($word);
$word = self::step5($word);

return $word;
}

/**
* Step 1
*/
private static function step1ab($word)
{
// Part a
if (substr($word, -1) == ’s‘) {

self::replace($word, ’sses‘, ’ss‘)
OR self::replace($word, ‚ies‘, ‚i‘)
OR self::replace($word, ’ss‘, ’ss‘)
OR self::replace($word, ’s‘, “);
}

// Part b
if (substr($word, -2, 1) != ‚e‘ OR !self::replace($word, ‚eed‘, ‚ee‘, 0)) { // First rule
$v = self::$regex_vowel;

// ing and ed
if ( preg_match(„#$v+#“, substr($word, 0, -3)) && self::replace($word, ‚ing‘, “)
OR preg_match(„#$v+#“, substr($word, 0, -2)) && self::replace($word, ‚ed‘, “)) { // Note use of && and OR, for precedence reasons

// If one of above two test successful
if ( !self::replace($word, ‚at‘, ‚ate‘)
AND !self::replace($word, ‚bl‘, ‚ble‘)
AND !self::replace($word, ‚iz‘, ‚ize‘)) {

// Double consonant ending
if ( self::doubleConsonant($word)
AND substr($word, -2) != ‚ll‘
AND substr($word, -2) != ’ss‘
AND substr($word, -2) != ‚zz‘) {

$word = substr($word, 0, -1);

} else if (self::m($word) == 1 AND self::cvc($word)) {
$word .= ‚e‘;
}
}
}
}

return $word;
}

/**
* Step 1c
*
* @param string $word Word to stem
*/
private static function step1c($word)
{
$v = self::$regex_vowel;

if (substr($word, -1) == ‚y‘ && preg_match(„#$v+#“, substr($word, 0, -1))) {
self::replace($word, ‚y‘, ‚i‘);
}

return $word;
}

/**
* Step 2
*
* @param string $word Word to stem
*/
private static function step2($word)
{
switch (substr($word, -2, 1)) {
case ‚a‘:
self::replace($word, ‚ational‘, ‚ate‘, 0)
OR self::replace($word, ‚tional‘, ‚tion‘, 0);
break;

case ‚c‘:
self::replace($word, ‚enci‘, ‚ence‘, 0)
OR self::replace($word, ‚anci‘, ‚ance‘, 0);
break;

case ‚e‘:
self::replace($word, ‚izer‘, ‚ize‘, 0);
break;

case ‚g‘:
self::replace($word, ‚logi‘, ‚log‘, 0);
break;

case ‚l‘:
self::replace($word, ‚entli‘, ‚ent‘, 0)
OR self::replace($word, ‚ousli‘, ‚ous‘, 0)
OR self::replace($word, ‚alli‘, ‚al‘, 0)
OR self::replace($word, ‚bli‘, ‚ble‘, 0)
OR self::replace($word, ‚eli‘, ‚e‘, 0);
break;

case ‚o‘:
self::replace($word, ‚ization‘, ‚ize‘, 0)
OR self::replace($word, ‚ation‘, ‚ate‘, 0)
OR self::replace($word, ‚ator‘, ‚ate‘, 0);
break;

case ’s‘:
self::replace($word, ‚iveness‘, ‚ive‘, 0)
OR self::replace($word, ‚fulness‘, ‚ful‘, 0)
OR self::replace($word, ‚ousness‘, ‚ous‘, 0)
OR self::replace($word, ‚alism‘, ‚al‘, 0);
break;

case ‚t‘:
self::replace($word, ‚biliti‘, ‚ble‘, 0)
OR self::replace($word, ‚aliti‘, ‚al‘, 0)
OR self::replace($word, ‚iviti‘, ‚ive‘, 0);
break;
}

return $word;
}

/**
* Step 3
*
* @param string $word String to stem
*/
private static function step3($word)
{
switch (substr($word, -2, 1)) {
case ‚a‘:
self::replace($word, ‚ical‘, ‚ic‘, 0);
break;

case ’s‘:
self::replace($word, ’ness‘, “, 0);
break;

case ‚t‘:
self::replace($word, ‚icate‘, ‚ic‘, 0)
OR self::replace($word, ‚iciti‘, ‚ic‘, 0);
break;

case ‚u‘:
self::replace($word, ‚ful‘, “, 0);
break;

case ‚v‘:
self::replace($word, ‚ative‘, “, 0);
break;

case ‚z‘:
self::replace($word, ‚alize‘, ‚al‘, 0);
break;
}

return $word;
}

/**
* Step 4
*
* @param string $word Word to stem
*/
private static function step4($word)
{
switch (substr($word, -2, 1)) {
case ‚a‘:
self::replace($word, ‚al‘, “, 1);
break;

case ‚c‘:
self::replace($word, ‚ance‘, “, 1)
OR self::replace($word, ‚ence‘, “, 1);
break;

case ‚e‘:
self::replace($word, ‚er‘, “, 1);
break;

case ‚i‘:
self::replace($word, ‚ic‘, “, 1);
break;

case ‚l‘:
self::replace($word, ‚able‘, “, 1)
OR self::replace($word, ‚ible‘, “, 1);
break;

case ’n‘:
self::replace($word, ‚ant‘, “, 1)
OR self::replace($word, ‚ement‘, “, 1)
OR self::replace($word, ‚ment‘, “, 1)
OR self::replace($word, ‚ent‘, “, 1);
break;

case ‚o‘:
if (substr($word, -4) == ‚tion‘ OR substr($word, -4) == ’sion‘) {
self::replace($word, ‚ion‘, “, 1);
} else {
self::replace($word, ‚ou‘, “, 1);
}
break;

case ’s‘:
self::replace($word, ‚ism‘, “, 1);
break;

case ‚t‘:
self::replace($word, ‚ate‘, “, 1)
OR self::replace($word, ‚iti‘, “, 1);
break;

case ‚u‘:
self::replace($word, ‚ous‘, “, 1);
break;

case ‚v‘:
self::replace($word, ‚ive‘, “, 1);
break;

case ‚z‘:
self::replace($word, ‚ize‘, “, 1);
break;
}

return $word;
}

/**
* Step 5
*
* @param string $word Word to stem
*/
private static function step5($word)
{
// Part a
if (substr($word, -1) == ‚e‘) {
if (self::m(substr($word, 0, -1)) > 1) {
self::replace($word, ‚e‘, “);

} else if (self::m(substr($word, 0, -1)) == 1) {

if (!self::cvc(substr($word, 0, -1))) {
self::replace($word, ‚e‘, “);
}
}
}

// Part b
if (self::m($word) > 1 AND self::doubleConsonant($word) AND substr($word, -1) == ‚l‘) {
$word = substr($word, 0, -1);
}

return $word;
}

/**
* Replaces the first string with the second, at the end of the string. If third
* arg is given, then the preceding string must match that m count at least.
*
* @param string $str String to check
* @param string $check Ending to check for
* @param string $repl Replacement string
* @param int $m Optional minimum number of m() to meet
* @return bool Whether the $check string was at the end
* of the $str string. True does not necessarily mean
* that it was replaced.
*/
private static function replace(&$str, $check, $repl, $m = null)
{
$len = 0 – strlen($check);

if (substr($str, $len) == $check) {
$substr = substr($str, 0, $len);
if (is_null($m) OR self::m($substr) > $m) {
$str = $substr . $repl;
}

return true;
}

return false;
}

/**
* What, you mean it’s not obvious from the name?
*
* m() measures the number of consonant sequences in $str. if c is
* a consonant sequence and v a vowel sequence, and indicates arbitrary
* presence,
*
* gives 0
* vc gives 1
* vcvc gives 2
* vcvcvc gives 3
*
* @param string $str The string to return the m count for
* @return int The m count
*/
private static function m($str)
{
$c = self::$regex_consonant;
$v = self::$regex_vowel;

$str = preg_replace(„#^$c+#“, “, $str);
$str = preg_replace(„#$v+$#“, “, $str);

preg_match_all(„#($v+$c+)#“, $str, $matches);

return count($matches[1]);
}

/**
* Returns true/false as to whether the given string contains two
* of the same consonant next to each other at the end of the string.
*
* @param string $str String to check
* @return bool Result
*/
private static function doubleConsonant($str)
{
$c = self::$regex_consonant;

return preg_match(„#$c{2}$#“, $str, $matches) AND $matches[0]{0} == $matches[0]{1};
}

/**
* Checks for ending CVC sequence where second C is not W, X or Y
*
* @param string $str String to check
* @return bool Result
*/
private static function cvc($str)
{
$c = self::$regex_consonant;
$v = self::$regex_vowel;

return preg_match(„#($c$v$c)$#“, $str, $matches)
AND strlen($matches[1]) == 3
AND $matches[1]{2} != ‚w‘
AND $matches[1]{2} != ‚x‘
AND $matches[1]{2} != ‚y‘;
}
}

?>

 


~8KB
Testscript für Fuzzy-Vergleiche

Coding, Download, PHP, Webapplication, Webentwicklung