levenshtein
(PHP 3 >= 3.0.17, 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.
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().