Edit Distance o Levenshtein Distance: un algoritmo di similarità tra stringhe

In questo posto vedremo l’algoritmo di Editi Distance [1] detto anche di Levenshtein Distance. La edit distance, o distanza di Levenshtein, tra due stringhe s1 e s2 il minimo numero di sostituzioni, cancellazioni o inserimenti che occorre effettuare per ottenere s1 da s2. Ad esempio, la distanza tra gtgcca e ggcga è 2 (bisogna inserire una t nella seconda stringa e sostituire la penultima g con c per ottenere la prima stringa).

L’edit distance rappresenta il costo dell’allineamento ottimo di due stringhe, quando tale costo è misurato attribuendo a due simboli a e b, uno dei quali può essere un gap (cioè un “buco”), il valore seguente:

dove il simbolo − denota, appunto, un gap. Il costo complessivo dell’allineamento è dato dalla somma dei costi di ciascuna posizione. Ad esempio, un allineamento ottimo, di costo 2, delle due stringhe precedenti è

gtgcca

g-gcga

Un allineamento non ottimo potrebbe essere

gtgcc-a

gg-c-ga

di costo 4 (potete contare quattro differenze).

L’algoritmo per calcolare l’edit distance (e quindi un allineamento ottimo) tra due stringhe si basa sull’osservazione seguente. Siano s1 = a1 ···am e s2 =b1 ···bn due stringhe. Denotiamo con e(i , j ) l’edit distance tra i due prefissi p1 = a1 ···ai e p2 = b1 ···bj di s1 e s2 rispettivamente. Se e(i −1, j −1), e(i −1, j ) ed e(i , j −1) sono noti, allora si può calcolare e(i , j ). Ciascuno dei tre valori corrisponde infatti a un allineamento ottimo:

  • e(i −1, j −1) è il costo dell’allineamento ottimo di s1 ··· ai-1 e b1 ··· bj-1
  • e(i −1, j ) è il costo dell’allineamento ottimo di a1 ··· ai-1 e b1 ··· bj
  • e(i , j −1) è il costo dell’allineamento ottimo di a1 ··· ai e b1 ··· bj-1

Ognuno dei tre allineamenti può essere esteso a un allineamento tra a1 ··· ai e b1 ··· bj :

  • allineando ai con bj
  • allineando ai con un gap
  • allineando un gap con bj

Per mantenere l’ottimalità, bisognerà scegliere l’operazione che consente di ottenere l’allineamento di costo minimo. Notate che il generico valore e(i , j ) dipende solamente da e(i −1, j −1), e(i , j −1) ed e(i −1, j ), e può essere calcolato usando la seguente equazione:

Possiamo disporre questi valori in una matrice (assumiamo di contare le righe e le colonne a partire da zero)  (m +1)×(n +1) (dove ε denota la stringa vuota):

È evidente che l’allineamento di una stringa vuota con una stringa x1 ··· xi ha costo i bisogna inserire i caratteri nella stringa vuota per ottenere x1 ··· xi ):

e(0, i) = e(i ,0) = i

In particolare, l’allineamento tra due stringhe vuote ha costo zero:

e(0,0) = 0

La matrice pertanto può essere riscritta cosí:

Sulla base delle osservazioni precedenti, la matrice può essere costruita riga per riga,  ossia da sinistra a destra e dall’alto in basso. Il valore e(m,n) rappresenta l’edit distance tra s1 e s2. Di seguito viene riportato una possibile implementazione dell’algoritmo per il calcolo dell’edit distance tra s1 = a1 ···am e s2 = b1 ···bn :

  1. creare una matrice (m +1)×(n +1) chiamata M;
  2. porre Mi,0 = i per 0 ≤ i m;
  3. porre M0,j = j per 0 ≤  j n;
  4. per ogni riga i, con i che varia da 1 a m:

a)      per ogni colonna  j, con j che varia da 1 a n:

i.se ai è uguale a bj , porre c = 0, altrimenti porre c = 1

ii.porre Mi,j = min{Mi-1,j-1 + c , Mi,j-1 + 1 , Mi-1,j + 1 }

  1. produrre in output Mm,n

Riferimenti:

[1] Michael Gilleland, Merriam Park Software, Levenshtein Distance Algorithm, http://www.merriampark.com/ld.htm

1 Stella2 Stelle3 Stelle4 Stelle5 Stelle (2 voti, media: 4,50 di 5)
Loading...
You can leave a response, or trackback from your own site.

Leave a Reply

*