int levenshtein (string str1, string str2)
int levenshtein (string str1, string str2, int cost_ins, int cost_rep, int cost_del)
int levenshtein (string str1, string str2, function cost)
Diese Funktion errechnet die Differenz zwischen den als Argumente übergebenen zwei Strings. Ist einer der Strings länger als die zulässigen 255 Zeichen, wird -1 zurück gegeben.
Die Levenshtein-Differenz ist definiert als die minimale Anzahl an Zeichen, die ersetzt, eingefügt oder gelöscht werden müssen um den str1 nach str2 umzusetzen. Die Komplexität des Algorithmus ist O(m*n), wobei n und m der Länge der Strings str1 und str2 (viel besser als bei der Funktion similar_text(), wo sie O(max(n,m)**3) beträgt).
Siehe auch soundex(), similar_text() und metaphone().