Marcos Ramírez

Hacía tiempo que no escribia, mucho curro, y muchos lios… asi que hoy que he aprendido algo nuevo interesante, aprovecho para volver a postear.

Levenshtein, es una función que calcula la distancia entre dos cadenas, ¿que quiere decir esto?, pues que pasandole dos cadenas, te dice el nivel de proximidad (similitud) de una frente a la otra, lo cual, permite hacer cosas como el famoso “quiso decir” de google, aquí os dejo unos ejemplillos:

Supongamos que tenemos una web con N usuarios registrados, y una opción de buscar usuarios por su nombre de usuario, lo normal, seria usar un MATCH AGAINST, o un LIKE de SQL, lo cual, es perfectamente válido, pero con levenshtein, obtendremos unos valores mucho más fiables (casi seguro), el coste que tiene es que deberemos pasarle el listado completo de usuarios, lo cual repercute en el rendimiento, aunque yo las pruebas que he hecho en el trabajo, comprobando recursivamente 7000 entradas, contra otras tantas miles de posibilidades, apenas tomó 3 segundos, sin optimizar, por tanto, lo veo posible.

A lo que vamos, queremos darle el nombre de usuario más aproximado al que encontró:

<?php$Usuarios=leeusers(); // Leemos _TODOS_ los nombres de usuario.
$usuarioabuscar=’pepito’; // el usuario a buscar
$distancia = -1; // establecemos una distancia inicial negativa (nula).
foreach ($Usuarios as $usuario) { //establecemos la distancia para cada usuario, recorriendo el array
    $lev = levenshtein($usuarioabuscar, $usuario);
    if ($lev == 0) { // Si la distancia es 0 (coincidencia exacta), salimos del array
        $cercano = $usuario;
        $distancia = 0;
        break;   
    }   
    if ($lev <= $distancia || $distancia < 0) { // si no, segumos buscando el mas cercano
        $cercano  = $usuario;
        $distancia = $lev;
    }
}
//mostramos resultados
echo “Buscaba: $usuarioabuscar \n”;

//Si hay coincidencia exacta…
if ($distancia == 0) {
    echo “Usuario encontrado: $cercano\n”;
} else { //si no, mostramos el mas cercano.
    echo “Usuario no encontrado, ¿quiso decir: $cercano? \n”;
}
?>

Fácil, ¿verdad?, pues, con esto, como veis, se pueden hacer muchas cosas, que lo disfruteis! :)

Y para más info, la web de PHP (de donde he cogido este ejemplo base/basico)