Cadenas
PHP Manual

levenshtein

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

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


Cadenas
PHP Manual