(PHP 3 >= 3.0.17, PHP 4 >= 4.0.1, PHP 5)
levenshtein --
Calcula la distancia Levenshtein entre dos cadenas
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().