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).
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 :
- creare una matrice (m +1)×(n +1) chiamata M;
- porre Mi,0 = i per 0 ≤ i ≤ m;
- porre M0,j = j per 0 ≤ j ≤ n;
- 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 }
- produrre in output Mm,n
Riferimenti:
[1] Michael Gilleland, Merriam Park Software, Levenshtein Distance Algorithm, http://www.merriampark.com/ld.htm
COMMENTS