levenshtein

Descripción

int levenshtein ( string cadena1, string cadena2 [, int cost_ins [, int cost_rep, int cost_del]] )

Esta función devuelve la distancia Levenshtein entre las dos cadenas indicadas, ó -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 cadena1 en cadena2. La complejidad del algoritmo es O(m*n), donde n y m son las longitudes de cadena1 y cadena2 (por tanto, el rendimiento es bastante bueno si se la compara con el de la función similar_text(), que es O(max(n,m)**3), pero aún así se trata de una función que puede penalizar el rendimiento global del script).

La forma más simple de utilizar la función es indicar 2 cadenas como parámetros y realizar el cálculo del número de operaciones de inserción, reemplazamiento y borrado que son necesarias para convertir la cadena1 en la cadena2.

Una forma alternativa de uso es la que tiene en cuenta 3 parámetros, siendo el tercer el que define el coste que tienen las operaciones de inserción, reemplazamiento y borrado. Esta forma es más genérica y más adaptativa, pero es menos eficiente.

Ejemplo 1. Ejemplo de levenshtein() <?php // Palabra escrita incorrectamente $palabra_original = 'zanahorria'; // Array de palabras para comprobar las palabras $palabras  = array('manzana','pina','platano','naranja',                 'rabano','zanahoria','guisante','alubia','patata'); // No se ha encontrado todavia la distancia mas corta $distancia_mas_corta = -1; // Recorrer $palabras para encontrar la mas corta foreach ($palabras as $palabra_actual) {     // Calcular la distancia entre la $palabra_original y la $palabra_actual     $lev = levenshtein($palabra_original, $palabra_actual);     // comprobar si son iguales (distancia 0)     if ($lev == 0) {         // se trata de la palabra mas proxima (de hecho, las 2 coinciden)         $palabra_mas_cercana = $palabra_actual;         $distancia_mas_corta = 0;         // salir del bucle porque ya se ha encontrado una coincidencia         break;     }     // si la distancia es menor que la siguiente distancia mas corta encontrada, o si     // si no se ha encontrado la palabra con la distancia mas corta     if ($lev <= $distancia_mas_corta || $distancia_mas_corta < 0) {         // establece la palabra mas cercana y la distancia mas corta         $palabra_mas_cercana  = $palabra_actual;         $distancia_mas_corta = $lev;     } } echo "Palabra introducida: $palabra_original\n"; if ($distancia_mas_corta == 0) {     echo "Se ha encontrado una coincidencia exacta: $palabra_mas_cercana\n"; } else {     echo "Quiso decir: $palabra_mas_cercana?\n"; } ?> El resultado del ejemplo seria: Palabra introducida: zanahorria Quiso decir: zanahoria?

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