levenshtein

Descrizione

int levenshtein ( string str1, string str2 [, int cost_ins [, int cost_rep, int cost_del]] )

Questa funzione restituisce la distanza Levenshtein tra due stringhe o -1 se uno degli argomenti è più lungo del limite di 255 caratteri.

La distanza Levenshtein è definita come il numero minimo di caratteri da sostituire, inserire o cancellare per trasformare str1 in str2. La complessità dell'algoritmo è O(m*n), dove n e m sono rispettivamente la lunghezza di str1 e di str2 (valore piuttosto buono se confrontato con similar_text(), che è O(max(n,m)**3), ma comunque costoso).

Nella sua versione più semplice la funzione richiede come parametri due stringhe e calcola il numero di caratteri da inserire, sostituire o rimuovere necessari a trasformare str1 in str2.

La seconda variante utilizza tre parametri addizionali che definiscono il costo delle operazioni di inserimento, sostituzione e di cancellazione. Questa versione è più generale e adattabile della precedente, ma non è altrettanto efficiente.

Esempio 1. Esempio di uso di levenshtein() <?php // input parola errata $input = 'carrrot';   // matrice di parole con cui verificare $words  = array('apple','pineapple','banana','orange',                 'radish','carrot','pea','bean','potato');   // non ancora trovata la distanza più breve $shortest = -1;   // loop su tutte le parole per trovare la più simile foreach ($words as $word) {       // calcola la distanza tra la parola di input     // e la corrente     $lev = levenshtein($input, $word);       // è la parola esatta?     if ($lev == 0) {           // la più simile è questa         $closest = $word;         $shortest = 0;           // esce dal loop, l'abbiamo trovata         break;     }       // se la distanza è inferiore rispetto alla precendete più corta     // o non ne abbiamo ancora trovata una     if ($lev <= $shortest || $shortest < 0) {         // imposta la parola più simile e la distanza più breve         $closest  = $word;         $shortest = $lev;     } }   echo "Input word: $input\n"; if ($shortest == 0) {     echo "Exact match found: $closest\n"; } else {     echo "Did you mean: $closest?\n"; }   ?> Il precedente esempio visualizzerà: Input word: carrrot Did you mean: carrot?

Vedere anche soundex(), similar_text() e metaphone().