(PHP 3 >= 3.0.17, PHP 4 >= 4.0.1, PHP 5)
levenshtein -- Berechnet die Levenshtein-Distanz zwischen zwei StringsDie 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.
Siehe auch soundex(), similar_text() und metaphone().
Zurück | Zum Anfang | Weiter |
join | Nach oben | localeconv |