Calcula la distància Levenshtein entre dues cadenes de text.
En Teoria de la informació i Ciències de la Computació es diu Distància de Levenshtein, distància d'edició, o distància entre paraules, al nombre mínim d'operacions requerides per transformar una cadena de caràcters en una altra. S'entén per operació, bé una inserció, eliminació o la substitució d'un caràcter. Aquesta distància rep aquest nom en honor al científic rus Vladimir Levenshtein. És útil en programes que determinen com de similars són dues cadenes de caràcters, com és el cas dels correctors d'ortografia.
La complexitat de l'algorisme és O (m * n), on n i m són les longituds de la cadena1 i la cadena2 (per tant, el rendiment és bastant bo si se la compara amb el de la funció similar_text (), que és O (max (n , m) ** 3), però tot i així es tracta d'una funció que pot penalitzar el rendiment global del script).
$diccionari = array(
"php", "javascript", "css"
);
$paraula = "japhp";
$best_match = $diccionari[0];
$match_value = levenshtein($diccionari[0], $paraula);
foreach($diccionari as $w) {
$value = levenshtein($paraula, $w);
if( $value < $match_value ) {
$best_match = $w;
$match_value = $value;
}
}
print "Et refereixes a la paraula '$best_match'?";