levenshtein

(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().

Hosting by: hurra.com
Generated: 2007-01-26 18:01:01