(PHP 4 >= 4.0.1, PHP 5)
levenshtein — Cálculo de la distancia Levenshtein entre dos strings
$str1
, string $str2
)$str1
, string $str2
, int $cost_ins
, int $cost_rep
, int $cost_del
)
La distancia Levenshtein se define como el número mínimo de
caracteres que se tienen que sustituir, insertar o borrar para transformar
str1 en str2.
La complejidad del algoritmo es O(m*n),
donde n y m son la
longitud de str1 y
str2 (bastante bueno en comparación con
similar_text(), la cual es O(max(n,m)**3),
pero sigue siendo costoso).
En su forma más simple la función tomará sólo los dos
strings como parámetros y calculará sólo el número de
operaciones de insertar, reemplazar y eliminar, necesarias para transformar
str1 en str2.
Una segunda variante tomará tres parámetros adicionales que definen el costo de las operaciones de insertar, reemplazar y eliminar. Esto es más general y adaptable que la primera variante, pero no tan eficiente.
str1Uno de los strings a ser evaluados para la distancia Levenshtein.
str2Uno de los strings a ser evaluados para la distancia Levenshtein.
cost_insDefine el costo de inserción.
cost_repDefine el costo de reemplazo.
cost_delDefine el costo de eliminación.
Esta función devuelve la distancia Levenshtein entre los dos strings argumentos ó -1, si uno de los strings argumentos es mayor que el límite de 255 caracteres.
Ejemplo #1 Ejemplo de levenshtein()
<?php
// palabra de entrada mal escrita
$input = 'carrrot';
// array de palabras contra las cuales verificar
$words = array('apple','pineapple','banana','orange',
'radish','carrot','pea','bean','potato');
// no se ha encontrado la distancia más corta, aun
$shortest = -1;
// bucle a través de las palabras para encontrar la más cercana
foreach ($words as $word) {
// calcula la distancia entre la palabra de entrada
// y la palabra actual
$lev = levenshtein($input, $word);
// verifica por una coincidencia exacta
if ($lev == 0) {
// la palabra más cercana es esta (coincidencia exacta)
$closest = $word;
$shortest = 0;
// salir del bucle, se ha encontrado una coincidencia exacta
break;
}
// si esta distancia es menor que la siguiente distancia
// más corta o si una siguiente palabra más corta aun no se ha encontrado
if ($lev <= $shortest || $shortest < 0) {
// establece la coincidencia más cercana y la distancia más corta
$closest = $word;
$shortest = $lev;
}
}
echo "Input word: $input\n";
if ($shortest == 0) {
echo "Exact match found: $closest\n";
} else {
echo "Did you mean: $closest?\n";
}
?>
El resultado del ejemplo sería:
Input word: carrrot Did you mean: carrot?