Nella teoria dell'informazione e in linguistica, la distanza di Levenshtein, o distanza di edit[1], è una misura per la differenza fra due stringhe. Introdotta dallo scienziato russo Vladimir Levenshtein nel 1965[2], serve a determinare quanto due stringhe siano simili. Le sue applicazioni vanno da semplici algoritmi di controllo ortografico alla ricerca per similarità su collezioni di immagini, suoni, testi, ecc.
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 simbolo,
- la sostituzione di un simbolo con un altro, o
- l'inserimento di un simbolo.
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" è .
Algoritmo
modificaUn 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 ] ) // per ogni i1 e i2, d[i1,i2] conterrà la distanza di Levenshtein tra // i primi i1 caratteri di str1 e i primi i2 caratteri di str2; // 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 - 1 ] = str2[ i2 - 1 ] then cost:= 0
d[ i1, i2 ] := d[ i1-1, i2-1 ]
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 ]
È possibile ridurre l'occupazione di memoria del precedente algoritmo osservando che a ogni passo dell'iterazione è sufficiente mantenere due righe della matrice, quella corrente e quella precedente. Usando questo accorgimento è possibile ridurre l'occupazione di memoria da O(mn) a O(m).
Implementazione
modificaImplementazione matriciale
modificaQuesto è il codice C dell'implementazione dell'algoritmo della distanza di Levenshtein mediante matrici:
int Levenshtein_distance(char *x, char *y) {
int m = strlen(x);
int n = strlen(y);
register int i, j;
int distance;
int **d = (int**) malloc((m + 1) * sizeof(int*));
for(i = 0; i <= m; i++)
d[i] = (int*) malloc((n + 1) * sizeof(int));
for(i = 0; i <= m; i++)
d[i][0] = i;
for(j = 1; j <= n; j++)
d[0][j] = j;
for(i = 1; i <= m; i++) {
for(j = 1; j <= n; j++) {
if(x[i - 1] != y[j - 1]) {
int k = minimum(
d[i][j - 1],
d[i - 1][j],
d[i - 1][j - 1]
);
d[i][j] = k + 1;
} else {
d[i][j] = d[i - 1][j - 1];
}
}
}
distance = d[m][n];
for(i = 0; i <= m; i++)
free(d[i]);
free(d);
return distance;
}
int minimum(int a, int b, int c) {
/* funzione che calcola il minimo di 3 valori */
int min = a;
if (b < min) min = b;
if (c < min) min = c;
return min;
}
Algoritmo in as3:
function levenshteinDistance(s1:String,s2:String):int
{
var m:int=s1.length;
var n:int=s2.length;
var matrix:Array=new Array();
var line:Array;
var i:int;
var j:int;
for (i=0;i<=m;i++)
{
line=new Array();
for (j=0;j<=n;j++)
{
if (i!=0)line.push(0)
else line.push(j);
}
line[0]=i
matrix.push(line);
}
var cost:int;
for (i=1;i<=m;i++)
for (j=1;j<=n;j++)
{
if (s1.charAt(i-1)==s2.charAt(j-1)) cost=0
else cost=1;
matrix[i][j]=Math.min(matrix[i-1][j]+1,matrix[i][j-1]+1,matrix[i-1][j-1]+cost);
}
return matrix[m][n];
}
Implementazione ottimizzata in termini di memoria
modificaSegue l'implementazione, ottimizzata in termini di memoria, dell'algoritmo della distanza di Levenshtein. Come detto in precedenza, per calcolare la distanza di Levenshtein basta mantenere, a ogni passo iterativo, la riga corrente della matrice e quella immediatamente precedente.
int Levenshtein_distance(char *x, char *y) {
int m = strlen(x);
int n = strlen(y);
register int i, j;
int distance;
int *prev = malloc((n + 1) * sizeof(int));
int *curr = malloc((n + 1) * sizeof(int));
int *tmp = 0;
for(i = 0; i <= n; i++)
prev[i] = i;
for(i = 1; i <= m; i++) {
curr[0] = i;
for(j = 1; j <= n; j++) {
if(x[i - 1] != y[j - 1]) {
int k = minimum(curr[j - 1], prev[j - 1], prev[j]);
curr[j] = k + 1;
} else {
curr[j] = prev[j - 1];
}
}
tmp = prev;
prev = curr;
curr = tmp;
memset((void*) curr, 0, sizeof(int) * (n + 1));
}
distance = prev[n];
free(curr);
free(prev);
return distance;
}
Limiti
modificaLa distanza di Levenshtein ha alcuni semplici limiti superiori e inferiori:
- è almeno la differenza fra le lunghezze delle due stringhe;
- è 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, cioè pari alla lunghezza delle stringhe;
- il limite superiore è pari alla lunghezza della stringa più lunga.
Note
modifica- ^ Per la precisione, la edit distance andrebbe indicata come distanza di Damerau-Levenshtein che ammette anche l'operazione di trasposizione: ad es. la permutazione di due simboli.
- ^ Si veda l'articolo originale in russo.
Bibliografia
modifica- (RU) В.И. Левенштейн, Двоичные коды с исправлением выпадений, вставок и замещений символов, in Доклады Академий Наук СCCP, vol. 163, n. 4, 1965, pp. 845-8. Traduzione: (EN) Levenshtein VI, Binary codes capable of correcting deletions, insertions, and reversals, in Soviet Physics Doklady, vol. 10, 1966, pp. 707-10.
- (EN) Eric Sven Ristad, Peter N. Yianilos, Learning String Edit Distance, 1997. URL consultato il 22 giugno 2010.
Altri progetti
modifica
Wikibooks contiene testi o manuali in lingua inglese sulla distanza di Levenshtein
Collegamenti esterni
modifica- (EN) Descrizione dell'algoritmo di Levestein, su levenshtein.net.
- (EN) Classroom Demonstration Tool for the Levenshtein Edit Distance Algorithm, su miislita.com. URL consultato il 22 giugno 2010 (archiviato dall'url originale il 14 aprile 2010).
