levenshtein

levenshtein -- Calcula la distancia Levenshtein entre dos cadenas

Descripción

int levenshtein ( string cad1, string cad2)

Esta función devuelve la distancia Levenshtein entre las dos cadenas argumento , ó -1 si alguna de las cadenas tiene más de 255 caracteres .

La distancia Levenshtein se define como el mínimo número de caracteres que se tienen que sustituir , insertar o borrar para transformar cad1 en cad2 . La complejidad del algoritmo es O( m*n ) , donde n y m son las longitudes de cad1 y cad2 (bastante bueno si se la compara con similar_text( ) , que es O(max(n,m)**3) , pero aún es cara ) .

Vea también soundex( ) , similar_text( ) y metaphone( ) .