La distanza di Levenshtein, a cosa serve? (1° parte)

In teoria dell’informazione e informatica , la distanza di Levenshtein è un’unità di misura per calcolare la differenza tra due stringhe. In altre parole, la distanza di Levenshtein tra due parole A e B è il numero minimo di modifiche di un carattere singolo (inserimento, cancellazione, sostituzione) necessario per modificare la parola A nella parola B. Con edit distance ci si riferisce spesso alla distanza di Levenshtein. La funzione prende il nome dal suo creatore Vladimir Levenshtein, scienziato russo specializzato in teoria dell’informazione, che la scoprì nel 1965.

Esempio

Calcolare la distanza di Levenshtein tra “kitten” e “sitting”. Ovviamente la risposta è 3, poiché sono necessarie tre modifiche per trasformare una parola nell’altra e non c’è altro modo per farlo con meno di tre modifiche:

1. kitten → sitten (sostituzione di “k” con”s”)
2. Sitten → Sittin (sostituzione di “e” con “i”)
3. Sittin → sitting (inserimento di “g” alla fine).

Alcune precisazioni

La distanza di Levenshtein ha alcuni limiti superiori e inferiori. Questi includono:

• La lunghezza è sempre almeno la differenza della lunghezza delle due stringhe.
• La lunghezza può essere al massimo uguale alla lunghezza della stringa più lunga.
• È zero se, e solo se, le stringhe sono uguali.
• Se le stringhe sono le stesse dimensioni, la distanza di Hamming è un limite superiore alla distanza Levenshtein.
• La distanza di Levenshtein tra due stringhe non può essere maggiore della somma delle loro distanze di levenshtein da una terza stringa (disuguaglianza triangolare).

Un classico utilizzo

Avete presente quando sbagliate a digitare una parola da cercare con Google? Il motore di ricerca vi consiglia una correzione della parola errata. Guardate l’esempio qui sotto, vi siete mai chiesti come fa Google a correggere le parole errate? La risposta è semplice: Levenshtein!

 

La funzione levenhstein() in PHP

In php è presente da tempo una funzione chiamata appunto levenhstein(), e viene definita di seguito:

int levenshtein(string $str1, string $str2)
// oppure
int levenshtein(string $str1, string $str2, int $cost_ins, int $cost_rep, int $cost_del)

dove:

• str1: prima stringa in ingresso da confrontare
• str2: seconda stringa in ingresso da confrontare
• cost_ins: definisce il “costo” dell’operazione di inserimento di un carattere
• cost_rep: definisce il “costo” dell’operazione di sostituzione di un carattere
• cost_del: definisce il “costo” dell’operazione di cancellazione di un carattere

continua…