Distanza di Levenshtein
Nella teoria dell'informazione e nella teoria dei linguaggi, la distanza di Levenshtein, o distanza di edit, è una misura per la differenza fra due stringhe. Introdotta dallo scienziato russo Vladimir Levenshtein nel 1965[1], 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.
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 ad 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, ad 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 ed 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- ^ 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 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).
