Architettura degli elaboratoriArchitettura degli elaboratori
Laboratorio di architettura degli elaboratori - AViReS Lab · PDF fileLaboratorio di...
2
Laboratorio di architettura degli elaboratori Esercizio 1 - String edit distance Date due stringhe S e T, ` e posibile far s` ı che le due stringhe coincidano in seguito a opportune modifiche, dove con modifica si intende la cancellazione, l’inseri- mento o la sostituzione di un carattere. Se ad esempio S=’gatto’, T=’getto’, le due stringhe coincidono in seguito alla sostituzione di un carattere (’a’ → ’e’ in S, o analogamente ’e’ → ’a’ in T). Allo stesso modo, date S=’auto’, T=’aiuto’, le due stringhe coincidono in seguito ad un inserimento in S (o, analogamente, una cancellazione in T). In generale esistono pi` u modi per trasformare una stringa in un’altra, ad esempio ’gatto’ pu` o essere banalmente trasformato in ’getto’ con 10 modifiche: la cancellazione di tutte le lettere di ’gatto’ e l’inserimento di tutte le lettere di ’getto’. La distanza di Levenshtein, detta anche string edit distance, ` e il numero minimo di modifiche necessarie per far s` ı che due stringhe coincidano. La distanza di Levenshtein pu` o essere definita ricorsivamente come d(, )=0 d(S, )= d(, S)= |S| d(S + c 1 ,T + c 2 )= min( d(S, T ) + 0 se c 1 = c 2 , +1 se c 1 6= c 2 , d(S + c 1 ,T )+1, d(S, T + c 2 )+1 ) dove ` e la stringa vuota. Tuttavia il calcolo della distanza di Levenshtein mediante un programma ricorsivo risulta essere estremamente inefficace, a causa del tempo di computazione che cresce esponenzialmente col numero di caratteri nelle due stringhe. Fortunatamente esiste un approccio pi` u efficace, basato sulla cosiddetta programmazione dinamica : Se |S| = m, |T | = n,` e sufficiente costruire una matrice D di dimensioni m +1 × n + 1 tale che D(0,0) = 0 D(i,0) = i, per i = 1..m D(0,j) = j, per j = 1..n 1
Transcript of Laboratorio di architettura degli elaboratori - AViReS Lab · PDF fileLaboratorio di...
Laboratorio di architettura degli elaboratori
Esercizio 1 - String edit distance
Date due stringhe S e T, e posibile far sı che le due stringhe coincidano in seguitoa opportune modifiche, dove con modifica si intende la cancellazione, l’inseri-mento o la sostituzione di un carattere. Se ad esempio S=’gatto’, T=’getto’, ledue stringhe coincidono in seguito alla sostituzione di un carattere (’a’ → ’e’ inS, o analogamente ’e’→ ’a’ in T). Allo stesso modo, date S=’auto’, T=’aiuto’, ledue stringhe coincidono in seguito ad un inserimento in S (o, analogamente, unacancellazione in T). In generale esistono piu modi per trasformare una stringain un’altra, ad esempio ’gatto’ puo essere banalmente trasformato in ’getto’ con10 modifiche: la cancellazione di tutte le lettere di ’gatto’ e l’inserimento ditutte le lettere di ’getto’. La distanza di Levenshtein, detta anche string editdistance, e il numero minimo di modifiche necessarie per far sı che due stringhecoincidano.
La distanza di Levenshtein puo essere definita ricorsivamente come
d(ε, ε) = 0d(S, ε) = d(ε, S) = |S|d(S + c1, T + c2) = min(
d(S, T ) + 0 se c1 = c2,+1 se c1 6= c2,
d(S + c1, T ) + 1,d(S, T + c2) + 1
)
dove ε e la stringa vuota. Tuttavia il calcolo della distanza di Levenshteinmediante un programma ricorsivo risulta essere estremamente inefficace, a causadel tempo di computazione che cresce esponenzialmente col numero di caratterinelle due stringhe. Fortunatamente esiste un approccio piu efficace, basato sullacosiddetta programmazione dinamica:
Se |S| = m, |T | = n, e sufficiente costruire una matrice D di dimensionim+ 1× n+ 1 tale che
D(0,0) = 0D(i,0) = i, per i = 1..mD(0,j) = j, per j = 1..n
1
tutte le altre celle della matrice possono essere riempite riga per riga, usandol’assegnamento
se S(i) == T(j) costo = 0; altrimenti costo = 1;D(i,j) = min( D(i-1,j-1)+costo, D(i,j-1) + 1, D(i-1,j) + 1)
con 0 < i ≤ m, 0 < j ≤ n. Una volta riempita tutta la matrice, l’elementoD(m,n) contiene la distanza di Levenshtein delle due stringhe S e T.
Figura 1: Matrice D per le parole Levenshtein e Meilenstein; in evidenza le mosse cheportano alla soluzione finale (distanza di Levenshtein: 4)
Si realizzi un programma in assembly che richieda in input due stringhe Se T, e scriva in output la distanza di Levensthein delle due stringhe usando ilmetodo di programmazione dinamica sopra descritto.
2
