levenshtein
(PHP 4 >= 4.0.1, PHP 5, PHP 7, PHP 8)
levenshtein — Berechnet die Levenshtein-Distanz zwischen zwei Strings
Beschreibung
string
$string1,string
$string2,int
$insertion_cost = 1,int
$replacement_cost = 1,int
$deletion_cost = 1): int
Die Levenshtein-Distanz bezeichnet die minimale Anzahl von Zeichen, die Sie
ersetzen, einfügen oder löschen müssen, um string1
in string2 umzuwandeln. Die Komplexität des Algorithmus
ist O(m*n), wobei n und
m die Länge von string1 und
string2 darstellen (recht gut, im Vergleich zu
similar_text(), das O(max(n,m)**3) ist,
aber trotzdem immer noch aufwendig).
Wenn insertion_cost,
replacement_cost und/oder
deletion_cost ungleich 1 sind,
passt sich der Algorithmus an, um die günstigsten Transformationen zu
wählen. Wenn z.B. $insertion_cost + $deletion_cost <
$replacement_cost, werden keine Ersetzungen durchgeführt, sondern
stattdessen Einfügungen und Löschungen.
Parameter-Liste
-
string1 -
Eine der Zeichenketten, für die die Levenshtein-Distanz zu berechnen ist.
-
string2 -
Eine der Zeichenketten, für die die Levenshtein-Distanz zu berechnen ist.
-
insertion_cost -
Definiert die Kosten des Einfügens.
-
replacement_cost -
Definiert die Kosten des Ersetzens.
-
deletion_cost -
Definiert die Kosten des Löschens.
Rückgabewerte
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.
Changelog
| Version | Beschreibung |
|---|---|
| 8.0.0 | Vor dieser Version musste levenshtein() entweder mit zwei oder fünf Argumenten aufgerufen werden. |
Beispiele
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() - Berechnet die Laut-Ähnlichkeit eines Strings
- similar_text() - Berechnet die Ähnlichkeit zweier Zeichenketten
- metaphone() - Berechnet den Metaphone-Schlüssel eines Strings
