levenshtein
(PHP 3 >= 3.0.17, PHP 4 >= 4.0.1, PHP 5)
levenshtein --
Berechnet die Levenshtein-Distanz zwischen zwei Strings
Beschreibung
int
levenshtein ( string str1, string str2 [, int cost_ins, int cost_rep, int cost_del] )
Die Funktion gibt die Levenshtein-Distanz zwischen den beiden
Argument-Strings oder -1 zurück, sofern eines der Argumente länger als 255
Zeichen ist.
Die Levenshtein-Distanz bezeichnet die minimale Anzahl von Zeichen, die
Sie ersetzen, einfügen oder löschen müssen, um str1
in str2 umzuwandeln. Die Komplexität des Algorithmus
ist 0(m*n), wobei n und
m die Länge von str1 und
str2 darstellen (deutlich besser, wenn man mit
similar_text() vergleicht, was mit 0(max(n,m)**3) daher
kommt, aber trotzdem immer noch teuer).
In ihrer einfachsten Form erhält die Funktion nur die zwei Strings als
Parameter und berechnet nur die Anzahl der Einfügungen, Ersetzungen und
Löschungen, die benötigt werden, um str1 in
str2 zu überführen.
Eine zweite Variante verwendet drei zusätzliche Parameter, die die Kosten
von Einfügungen, Ersetzungen und Löschungen festlegen. Dies ist eine
allgemeingültigere und anpassungsfähigere Version als Variante eins, aber
nicht so effizient.
Beispiel 1. levenshtein()-Beispiel
<?php
// eingegebenes falsch geschriebenes Wort
$input = 'carrrot';
// Wörterarray als Vergleichsquelle
$words = array('apple','pineapple','banana','orange',
'radish','carrot','pea','bean','potato');
// noch keine kürzeste Distanz gefunden
$shortest = -1;
// durch die Wortliste gehen, um das ähnlichste Wort zu finden
foreach ($words as $word) {
// berechne die distanz zwischen Inputwort und aktuellem Wort
$lev = levenshtein($input, $word);
// auf einen exakten Treffer prüfen
if ($lev == 0) {
// das nächste Wort ist das Wort selbst (exakter Treffer)
$closest = $word;
$shortest = 0;
// Schleife beenden, da wir einen exakten Treffer gefunden haben
break;
}
// Wenn die Distanz kleiner ist als die nächste gefundene kleinste Distanz
// ODER wenn ein nächstkleineres Wort noch nicht gefunden wurde
if ($lev <= $shortest || $shortest < 0) {
// setze den nächstliegenden Treffer und die kürzestes Distanz
$closest = $word;
$shortest = $lev;
}
}
echo "Eingegebenes Wort: $input\n";
if ($shortest == 0) {
echo "Exakter Treffer gefunden: $closest\n";
} else {
echo "Meinten Sie: $closest?\n";
}
?>
|
Das oben gezeigte Beispiel erzeugt folgende
Ausgabe: Eingegebenes Word: carrrot
Meinten Sie: carrot? |
|
Siehe auch
soundex(),
similar_text() und
metaphone().