Implementación de "quiso decir" similar al de google

Uno de los avances más importantes que hizo que la utilidad de google como buscador es el apartado "quiso decir".

Si nos equivocamos en una palabra se nos indica (con bastante acierto) lo que queríamos decir, es más, muchas veces no nos preocupamos de escribir bien la consulta sabiendo que se nos va a corregir bien.

¿Cómo se implementa algo así? Pues realmente no es algo muy complejo.

Primero necesitamos una medida de cómo de lejana es una palabra con respecto a otra, se puede usar la distancia de Levenshtein, en el enlace a la wikipedia hay también implementaciones de esta medida en numerosos lenguajes.

En php además tenemos la ventaja de tener implementada ya la función.

Veamos un ejemplo de como usarla.

<?php

$input='peujot';

$dictionary=array('seat','ford','honda','mercedes',
        'bmw','citroen','peugeot','fiat','ferrari');

$shortest=-1;

foreach($dictionary as $word){
        $lev=levenshtein($input, $word);

        if($lev==0){
                $closest=$word;
                $shortest=0;
                break;
        }

        if($lev<=$shortest || $shortest<0){
                $closest=$word;
                $shortest=$lev;
        }
}

echo "Ha introducido: $input <br/>";
if($shortest==0){
        echo "Palabra correcta <br/>";
}
else{
        echo "Quiso decir: $closest <br/>";
}

En este código se toma como entrada $input y se busca la palabra conocida más cercana (según la distancia Levenshtein).