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
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 ] )
// 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
Implementazione matriciale
Questo è 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
Segue 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
La 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
Bibliografia
Altri progetti
Collegamenti esterni
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
