Distanza di Levenshtein
Da Wikipedia, l'enciclopedia libera.
Nella teoria dell'informazione e nella teoria dei linguaggi, la distanza di Levenshtein, o edit distance, è una misura per la differenza fra due stringhe. Introdotta dallo scienziato russo Vladimir Levenshtein nel 1965, serve a determinare quanto due stringhe siano simili. Viene applicata per esempio per semplici algoritmi di controllo ortografico e per fare ricerca di similarità tra immagini, suoni, testi etc..
La distanza di Levenshtein tra due stringhe A e B è il numero minimo di modifiche elementari che consentono di trasformare la A nella B. Per modifica elementare si intende
- la cancellazione di un carattere,
- la sostituzione di un carattere con un altro, o
- l'inserimento di un carattere.
Per esempio, per trasformare "bar" in "biro" occorrono due modifiche:
- "bar" -> "bir" (sostituzione di 'a' con 'i')
- "bir" -> "biro" (inserimento di 'o')
Non è possibile trasformare la prima parola nella seconda con meno di due modifiche, quindi la distanza di Levenshtein fra "bar" e "biro" è 2.
[modifica] Algoritmo
Un algoritmo usato comunemente per calcolare la distanza di Levenshtein richiede l'uso di una matrice di (n + 1) × (m + 1), dove n e m rappresentano le lunghezze delle due stringhe. Il seguente pseudocodice rappresenta una funzione LevenshteinDistance che prende come argomenti due stringhe str1 e str2 di lunghezza lenStr1 e lenStr2 e ne calcola la distanza di Levenshtein:
int LevenshteinDistance ( char str1[ 1..lenStr1 ], char str2[ 1..lenStr2 ] )
// d è una matrice di lenStr1+1 righe e lenStr2+1 colonne
declare int d[ 0..lenStr1, 0..lenStr2 ]
// i1 e i2 servono per iterare su str1 e str2
declare int i1, i2, cost
for i1 from 0 to lenStr1
d[ i1, 0 ] := i1
for i2 from 0 to lenStr2
d[ 0, i2 ] := i2
for i1 from 1 to lenStr1
for i2 from 1 to lenStr2
if str1[ i1 ] = str2[ i2 ] then cost := 0
else cost := 1
d[ i1, i2 ] = minimum(
d[ i1 - 1, i2 ] + 1, // inserimento
d[ i1 , i2 - 1 ] + 1, // cancellazione
d[ i1 - 1, i2 - 1 ] + cost // sostituzione
)
return d[ lenStr1, lenStr2 ]
[modifica] Limiti
La distanza di Levenshtein ha alcuni semplici limiti superiori ed inferiori:
- è almeno la differenza fra le lunghezze delle due stringhe;
- non supera la lunghezza della stringa più lunga;
- è 0 se e solo se le due stringhe sono identiche;
- se le lunghezze delle due stringhe sono uguali, la distanza di Levenshtein non supera la distanza di Hamming;
- per due stringhe di lunghezze diverse, il limite superiore è la distanza di Hamming aumentata dela differenza delle lunghezze.
