|
Distanza di LevenshteinNella 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
Per esempio, per trasformare "bar" in "biro" occorrono due modifiche:
Non è possibile trasformare la prima parola nella seconda con meno di due modifiche, quindi la distanza di Levenshtein fra "bar" e "biro" è 2. AlgoritmoUn 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). ImplementazioneImplementazione matricialeQuesto è 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 memoriaSegue 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;
}
LimitiLa distanza di Levenshtein ha alcuni semplici limiti superiori ed inferiori:
Note
Bibliografia
Altri progetti
Collegamenti esterni
|
