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, 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:

1. "bar" → "bir" (sostituzione di 'a' con 'i')
2. "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.

Bibliografia

• (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

Altri progetti

• Wikibooks

• Wikibooks contiene testi o manuali sulla distanza di Levenshtein

Collegamenti esterni

• (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).