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 (255 caratteri dovrebbero essere più che sufficienti per il dizionario di confronto, e poi nessuno svolgerebbe seriamente una analisi genetica con il PHP).

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.

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