Olimpiadi di Informatica 2010
Giornate preparatorie
Dipartimento di Informatica
Università di Torino
marzo 2010
14 – Programmazione dinamica:
distanza minima fra due sequenze di caratteri.
(versione 18/12/2015)
12/18/2015
E. Giovannetti -- OI09.
1
Distanza fra due sequenze di caratteri
Si considerino le seguenti tre operazioni su una sequenza di
caratteri (stringa):
• inserimento di un carattere all'interno della stringa (o in
testa alla stringa);
• cancellazione di un carattere della stringa (con compattamento della stessa);
• sostituzione di un carattere della stringa con un altro
carattere.
Date due stringhe S1 ed S2, si definiscono:
• trasformazione di S1 in S2: una sequenza di operazioni dei
tre generi precedenti che trasforma la sequenza S1 nella
sequenza S2 ;
• distanza (minima) fra S1 ed S2: lunghezza della più corta
trasformazione di S1 in S2, cioè numero mimimo di
operazioni necessario per trasformare S1 in S2.
18/12/2015 19:24
E. Giovannetti - AlgELab-09-10 - Lez.51
2
Esempio
trasformazione (non minimale) di RISOTTO in PRESTO:
1
2
3
4
5
6
7
8
cancella R
cancella I
cancella S
cancella O
cambia T in S
inserisci P
inserisci R
inserisci E
RISOTTO
ISOTTO
SOTTO
OTTO
TTO
STO
PSTO
PRSTO
PRESTO
distanza (non minima) = 8
18/12/2015 19:24
E. Giovannetti - AlgELab-09-10 - Lez.51
3
Esempi
trasformazione minimale di RISOTTO in PRESTO:
RISOTTO
inserisci P
PRISOTTO
cambia I in E
PRESOTTO
cancella O
PRESTTO (da PRESOTTO)
cancella T
PRESTO (da PRESTTO)
distanza (minima) = 4
trasformazione di STUDENTE in LAUREATO:
STUDENTE
cambia S in L
LTUDENTE
cambia T in A
LAUDENTE
cambia D in R
LAURENTE
cambia N in A
LAUREATE
cambia E in O
LAUREATO
distanza (minima) = 5
18/12/2015 19:24
E. Giovannetti - AlgELab-09-10 - Lez.51
4
Esempi
trasformazione di ACQUA in VINO:
ACQUA
cancella A
CQUA
cambia C in V
VQUA
cambia Q in I
VIUA
cambia U in N
VINA
cambia A in O
VINO
distanza (minima) = 5
18/12/2015 19:24
E. Giovannetti - AlgELab-09-10 - Lez.51
5
Esercizio
Si specifichi, usando la tecnica della programmazione dinamica, l'algoritmo che, date due stringhe, trova la più corta trasformazione da una all'altra.
18/12/2015 19:24
E. Giovannetti - AlgELab-09-10 - Lez.51
6
L’algoritmo ricorsivo
• Le due (sotto)stringhe terminano con lo stesso carattere:
b1b2...bi-1c  c1c2...cj-1c
Allora la più corta trasformazione dalla prima alla seconda
coincide con la più corta trasformazione
b1b2...bi-1  c1c2...cj-1
• Le due (sotto)stringhe terminano con caratteri diversi:
b1b2...bi-1b  c1c2...cj-1c
Allora la più corta trasformazione dalla prima alla seconda
è la più corta fra:
• b1b2...bi-1  c1c2...cj-1 seguita da CAMBIA b IN c;
• b1b2...bi-1b  c1c2...cj-1 seguita da INSERISCI c;
• b1b2...bi-1  c1c2...cj-1c seguita da CANCELLA b;
18/12/2015 19:24
E. Giovannetti - AlgELab-09-10 - Lez.51
7
Esempio: trasf(“RIS", “PRES") = trasf (“RI", “PRE")
distanze:
d(“RIS", “PRES") = d(“RI", “PRE")
stringa di arrivo
stringa di partenza
P
R
E
S
T
O
R
I
S
d
d
O
T
T
O
18/12/2015 19:24
E. Giovannetti - AlgELab-09-10 - Lez.51
8
Esempio: trasf(“RISO", “PREST")
d(“RISO", “PREST") = min(d1, d2, d3) + 1
stringa di arrivo
stringa di partenza
P
R
E
S
T
S
d1
d2
O
d3
O
R
I
T
T
O
18/12/2015 19:24
E. Giovannetti - AlgELab-09-10 - Lez.51
9
Base della ricorsione
b1b2...bi  stringa vuota
CANCELLA b1, CANCELLA b2, ... , CANCELLA bi;
stringa vuota  c1c2...cj
INSERISCI c1, INSERISCI c2, ... , INSERISCI cj;
stringa vuota  stringa vuota
TRASFORMAZIONE NULLA
Nota: Poiché in C(++) le stringhe e gli array sono indiciati a
partire da 0, il numero di passi della trasformazione
b0b1...bi  stringa vuota
è i+1;
analogamente il numero di passi della trasformazione
stringa vuota  c0c1...cj
è j+1;
18/12/2015 19:24
E. Giovannetti - AlgELab-09-10 - Lez.51
10
Trovare solo la distanza: funzione ricorsiva …
string s, t;
int m, n;
int min3(int x, int y, int z) {
int min = x <= y ? x : y;
if(z < min) min = z;
return min;
}
int dis(int i, int j) {
if(i == -1) return j+1;
if(j == -1) return i+1;
if(s.at(i) == t.at(j)) return dis(i-1,j-1);
else return
1+min3(dis(i-1,j-1),dis(i,j-1),dis(i-1,j));
}
Nel main: ...
cout << dis(m-1, n-1);
18/12/2015 19:24
E. Giovannetti - AlgELab-09-10 - Lez.51
11
… inefficiente !
• Soffre dello stesso grave difetto di fibonacci ricorsivo: il
ricalcolo degli stessi valori rende “intrattabile” la
complessità della procedura !
• Come nel caso di fibonacci, occorre memorizzare i risultati
delle chiamate ricorsive, in modo da non ricalcolare i valori
già calcolati in qualche chiamata precedente.
18/12/2015 19:24
E. Giovannetti - AlgELab-09-10 - Lez.51
12
Ricorsione con memorizzazione
• Poiché le chiamate ricorsive sono della forma dist(i, j), con
0  i  m-1, 0  j  n-1, per memorizzarne i risultati serve
una matrice di dimensioni m  n.
• Inizializziamo tutti gli elementi di tale matrice ad un valore
impossibile della distanza di editing, ad es. -1.
• Nella funzione dist, prima di andare ad eseguire il calcolo
con le chiamate ricorsive, si controlla se il corrispondente
elemento della matrice non contiene già il risultato (cioè è
diverso da -1), e in tal caso lo si restituisce senza rifare il
calcolo.
• Se invece il risultato viene calcolato, prima della return lo
si memorizza nella matrice.
18/12/2015 19:24
E. Giovannetti - AlgELab-09-10 - Lez.51
13
Ricorsione con memorizzazione: codice C++.
#define MAXL 100;
string s, t;
int m, n;
int d[MAXL][MAXL];
...
int dis(int i, int j) {
if(i == -1) return j+1;
if(j == -1) return i+1;
if(d[i][j] == -1) {
if(s.at(i)==t.at(j)) d[i][j]= dis(i-1,j-1);
else d[i][j] =
1+min3(dis(i-1,j-1),dis(i,j-1),dis(i-1,j));
}
return d[i][j];
}
18/12/2015 19:24
E. Giovannetti - AlgELab-09-10 - Lez.51
14
Versione iterativa
Come nel caso di fibonacci, l’algoritmo precedente si può
scrivere in forma iterativa: la funzione dist diventa una
procedura contenente un ciclo che calcola ad uno ad uno gli
elementi della matrice, riga per riga.
Alla fine la soluzione si troverà nell’elemento più a sinistra in
basso, che è l’ultimo calcolato.
È inoltre conveniente utilizzare una matrice (m+1)  (n+1),
dove la colonna 0 rappresenta la stringa vuota come stringa
iniziale, la riga 0 la stringa vuota come stringa finale.
Occorre allora premettere alle stringhe un carattere fittizio
(ad es. un blank):
s = “ ” + s; t = “ ” + t;
La soluzione si troverà quindi in d[m][ n].
Prima del ciclo di calcolo vero e proprio bisogna inizializzare
la prima riga e la prima colonna.
18/12/2015 19:24
E. Giovannetti - AlgELab-09-10 - Lez.51
15
Esempio: distanza("RISOTTO", "PRESTO")
stringa di arrivo
stringa di partenza
P
no
0 ins
R
del
1
I
del
2
S
del
3
O
del
4
T
del
5
T
del
6
O
del
7
18/12/2015 19:24
R
1 ins
E
2
ins 3
S
T
ins 4 ins
E. Giovannetti - AlgELab-09-10 - Lez.51
O
5 ins
6
16
Versione iterativa: codice C++.
void dist() {
// inizializzazione della riga 0 e della colonna 0
for(int i = 0; i <= m; i++) d[i][0] = i;
for(int j = 1; j <= n; j++) d[0][j] = j;
for(int i = 1; i <= m; i++) {
for(int j = 1; j <= n; j++) {
if(s.at(i) == t.at(j))
d[i][j] = d[i-1][j-1];
else
d[i][j] = 1 + min3(d[i-1][j-1], d[i][j-1], d[i-1][j] );
}
}
}
18/12/2015 19:24
E. Giovannetti - AlgELab-09-10 - Lez.51
17
Trovare la trasformazione più corta.
Se invece della sola distanza minima si vuole anche trovare la
corrispondente sequenza di operazioni che trasforma la
prima stringa nella seconda, occorre costruire, a fianco della
matrice delle distanze, una matrice delle operazioni.
Ciascun elemento della matrice contiene l’ultima operazione
della trasformazione fra le due sottostringhe corrispondenti
all’elemento.
Alla fine, partendo dall’ultimo elemento a sinistra in basso si
ricostruisce all’indietro il cammino percorso, dove la casella
precedente dipende dal contenuto della casella corrente:
• CAMBIA: vai alla casella indietro in diagonale
• CANCELLA: vai alla casella sopra in verticale
• INSERISCI: vai alla casella a sinistra in orizzontale
• NO OP: vai alla casella indietro in diagonale
18/12/2015 19:24
E. Giovannetti - AlgELab-09-10 - Lez.51
18
trasf("RISO", "PRES") = trasf("RIS", "PRES") + del O
stringa di arrivo
P
stringa di partenza
no 0 ins
R
1 ins
E
2
S
ins 3
T
ins 4 ins
R
del
1
c
I
del
2
c 2
c 2
S
del
3
c
3
c
3
c
3
O
del
4
c
4
c
4
c
4 del 3
T
del
5
T
del
6
O
del
7
18/12/2015 19:24
1
no 1 ins
2 ins
c 2
3 ins
c 3
...
no 2 ...
E. Giovannetti - AlgELab-09-10 - Lez.51
O
5 ins
6
4 ins
5
...
...
19
Esempio di esecuzione
Per semplicità, disegniamo le due matrici in sovrapposizione,
come se fossero un’unica matrice in cui ogni casella contiene
sia la distanza che l’operazione.
18/12/2015 19:24
E. Giovannetti - AlgELab-09-10 - Lez.51
20
trasf("R", "P") = [Cambia R in P], lungh = 1
stringa di arrivo
P
stringa di partenza
no 0 ins
R
del
1
I
del
2
S
del
3
O
del
4
T
del
5
T
del
6
O
del
7
18/12/2015 19:24
c
R
1 ins
E
2
ins 3
S
T
ins 4 ins
O
5 ins
6
1
E. Giovannetti - AlgELab-09-10 - Lez.51
21
trasf("R", "PR") = trasf("", "P")
stringa di arrivo
stringa di partenza
P
R
E
no
0 ins
1 ins
2
R
del
1 c
1
1
I
del
2
S
del
3
O
del
4
T
del
5
T
del
6
O
del
7
18/12/2015 19:24
no
ins 3
S
T
ins 4 ins
E. Giovannetti - AlgELab-09-10 - Lez.51
O
5 ins
6
22
trasf("R", "PRE") = trasf("R", "PR") + ins E
stringa di arrivo
stringa di partenza
P
R
no
0 ins
1 ins
R
del
1 c
1
I
del
2
S
del
3
O
del
4
T
del
5
T
del
6
O
del
7
18/12/2015 19:24
E
2
ins 3
no 1
ins 2
S
T
ins 4 ins
E. Giovannetti - AlgELab-09-10 - Lez.51
O
5 ins
6
23
trasf("R", "PRESTO") = trasf("R", "PREST") + ins O
stringa di arrivo
P
stringa di partenza
no 0 ins
R
del
1 c
I
del
2
S
del
3
O
del
4
T
del
5
T
del
6
O
del
7
18/12/2015 19:24
R
E
1 ins
2
1
1 ins
no
S
ins 3
T
ins 4 ins
2 ins
3 ins
E. Giovannetti - AlgELab-09-10 - Lez.51
O
5 ins
6
4 ins
5
24
trasf("RI", "P") = trasf("R", "") + cambia I in P
stringa di arrivo
P
stringa di partenza
no 0 ins
R
1 ins
R
del
1
c
I
del
2
c 2
S
del
3
O
del
4
T
del
5
T
del
6
O
del
7
18/12/2015 19:24
1
E
2
S
ins 3
no 1 ins
T
ins 4 ins
2 ins
3 ins
E. Giovannetti - AlgELab-09-10 - Lez.51
O
5 ins
6
4 ins
5
25
trasf("RI", "PR") = trasf("R", "P") + cambia I in R
stringa di arrivo
P
stringa di partenza
no 0 ins
R
1 ins
R
del
1
c
I
del
2
c 2
S
del
3
O
del
4
T
del
5
T
del
6
O
del
7
18/12/2015 19:24
1
E
2
S
ins 3
no 1 ins
T
ins 4 ins
2 ins
3 ins
O
5 ins
6
4 ins
5
c 2
E. Giovannetti - AlgELab-09-10 - Lez.51
26
trasf("RISO", "PRES") = trasf("RIS", "PRES") + del O
stringa di arrivo
P
stringa di partenza
no 0 ins
R
1 ins
E
2
S
ins 3
T
ins 4 ins
R
del
1
c
I
del
2
c 2
c 2
S
del
3
c
3
c
3
c
3
O
del
4
c
4
c
4
c
4 del 3
T
del
5
T
del
6
O
del
7
18/12/2015 19:24
1
no 1 ins
2 ins
c 2
3 ins
c 3
...
no 2 ...
E. Giovannetti - AlgELab-09-10 - Lez.51
O
5 ins
6
4 ins
5
...
...
27
eccetera
Esercizio: completare a mano la tabella.
18/12/2015 19:24
E. Giovannetti - AlgELab-09-10 - Lez.51
28
Ricostruzione della sequenza di operazioni
• La sequenza si ricostruisce seguendo all'indietro le frecce.
18/12/2015 19:24
E. Giovannetti - AlgELab-09-10 - Lez.51
29