String Funzioni
PHP Manual

levenshtein

(PHP 4 >= 4.0.1, PHP 5)

levenshtein Calcola la distanza Levenshtein tra due stringhe

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.

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


String Funzioni
PHP Manual