levenshtein
(PHP 4 >= 4.0.1, PHP 5)
levenshtein — Calcula la distancia Levenshtein entre dos cadenas
Descripción
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.
Example#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().