4/19/2015E. Giovannetti -- OI09.1 Olimpiadi di Informatica 2010 Giornate preparatorie Dipartimento...

04/11/23 E. Giovannetti -- OI09. 1

Olimpiadi di Informatica 2010Giornate preparatorie

Dipartimento di InformaticaUniversità di Torino

marzo 2010

14 – Programmazione dinamica: distanza minima fra due sequenze di caratteri.

(versione 11/04/23)

11/04/23 19:53 E. Giovannetti - AlgELab-09-10 - Lez.51 2

Distanza fra due sequenze di caratteriSi 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 compatta-mento 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.


Esempio

trasformazione (non minimale) di RISOTTO in PRESTO:

RISOTTO1 cancella R ISOTTO2 cancella I SOTTO3 cancella S OTTO 4 cancella O TTO 5 cambia T in S STO6 inserisci P PSTO7 inserisci R PRSTO8 inserisci E PRESTO

distanza (non minima) = 8


Esempi

trasformazione minimale di RISOTTO in PRESTO:RISOTTO

inserisci P PRISOTTOcambia I in E PRESOTTOcancella O PRESTTO (da PRESOTTO)cancella T PRESTO (da PRESTTO)

distanza (minima) = 4

trasformazione di STUDENTE in LAUREATO:STUDENTE

cambia S in L LTUDENTEcambia T in A LAUDENTEcambia D in R LAURENTEcambia N in A LAUREATEcambia E in O LAUREATO



Esempi

trasformazione di ACQUA in VINO:ACQUA

cancella A CQUAcambia C in V VQUAcambia Q in I VIUAcambia U in N VINAcambia A in O VINO



Esercizio

Si specifichi, usando la tecnica della programmazione dinami-ca, l'algoritmo che, date due stringhe, trova la più corta tra-sformazione da una all'altra.

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;



Esempio: trasf(“RIS", “PRES") = trasf (“RI", “PRE")

distanze: d(“RIS", “PRES") = d(“RI", “PRE")

P R E S T O

R

I d

S d

O

T

T

O

stri

ng

a d

i p

art

en

za

stringa di arrivo


Esempio: trasf(“RISO", “PREST") d(“RISO", “PREST") = min(d1, d2, d3) + 1

P R E S T O

R

I

S d1d2

O d3

T

T

O

stri

ng

a d

i p

art

en

za

stringa di arrivo

Base della ricorsione

b1b2...bi stringa vuotaCANCELLA 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;


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);


… 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.


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.


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];}


Versione iterativaCome 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.



Esempio: distanza("RISOTTO", "PRESTO")

P R E S T O

no 0

ins 1

ins 2

ins 3 ins 4 ins 5

ins 6

R del 1

I del 2

S del 3

O del 4

T del 5

T del 6

O del 7

stri

ng

a d

i p

art

en

za

stringa di arrivo

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] ); } }}


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



P R E S T O

no 0 ins 1

ins 2

ins 3 ins 4 ins 5

ins 6

R del 1

c 1 no 1 ins 2

ins 3

ins 4

ins 5

I del 2

c 2 c 2

c 2

c 3

... ...

S del 3

c 3

c 3

c 3

no 2... ...

O del 4

c 4

c 4

c 4

del 3

T del 5

T del 6

O del 7

stri

ng

a d

i p

art

en

za

stringa di arrivo

trasf("RISO", "PRES") = trasf("RIS", "PRES") + del O

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.



P R E S T O

no 0 ins 1

ins 2

ins 3 ins 4 ins 5

ins 6

R del 1

c 1

I del 2

S del 3

O del 4

T del 5

T del 6

O del 7

stri

ng

a d

i p

art

en

za

stringa di arrivo

trasf("R", "P") = [Cambia R in P], lungh = 1


P R E S T O

no 0

ins 1

ins 2

ins 3 ins 4 ins 5

ins 6

R del 1

c 1

no 1

I del 2

S del 3

O del 4

T del 5

T del 6

O del 7

stri

ng

a d

i p

art

en

za

stringa di arrivo

trasf("R", "PR") = trasf("", "P")


P R E S T O

no 0

ins 1

ins 2

ins 3 ins 4 ins 5

ins 6

R del 1

c 1

no 1

ins 2

I del 2

S del 3

O del 4

T del 5

T del 6

O del 7

stri

ng

a d

i p

art

en

za

stringa di arrivo

trasf("R", "PRE") = trasf("R", "PR") + ins E


P R E S T O

no 0 ins 1

ins 2

ins 3 ins 4 ins 5

ins 6

R del 1

c 1

no 1

ins 2

ins 3

ins 4

ins 5

I del 2

S del 3

O del 4

T del 5

T del 6

O del 7

stri

ng

a d

i p

art

en

za

stringa di arrivo

trasf("R", "PRESTO") = trasf("R", "PREST") + ins O


P R E S T O

no 0 ins 1

ins 2

ins 3 ins 4 ins 5

ins 6

R del 1

c 1 no 1 ins 2

ins 3

ins 4

ins 5

I del 2

c 2

S del 3

O del 4

T del 5

T del 6

O del 7

stri

ng

a d

i p

art

en

za

stringa di arrivo

trasf("RI", "P") = trasf("R", "") + cambia I in P


P R E S T O

no 0 ins 1

ins 2

ins 3 ins 4 ins 5

ins 6

R del 1

c 1 no 1 ins 2

ins 3

ins 4

ins 5

I del 2

c 2 c 2

S del 3

O del 4

T del 5

T del 6

O del 7

stri

ng

a d

i p

art

en

za

stringa di arrivo

trasf("RI", "PR") = trasf("R", "P") + cambia I in R


P R E S T O

no 0 ins 1

ins 2

ins 3 ins 4 ins 5

ins 6

R del 1

c 1 no 1 ins 2

ins 3

ins 4

ins 5

I del 2

c 2 c 2

c 2

c 3

... ...

S del 3

c 3

c 3

c 3

no 2... ...

O del 4

c 4

c 4

c 4

del 3

T del 5

T del 6

O del 7

stri

ng

a d

i p

art

en

za

stringa di arrivo

trasf("RISO", "PRES") = trasf("RIS", "PRES") + del O

eccetera

Esercizio: completare a mano la tabella.



Ricostruzione della sequenza di operazioni

•La sequenza si ricostruisce seguendo all'indietro le frecce.

4/19/2015E. Giovannetti -- OI09.1 Olimpiadi di Informatica 2010 Giornate preparatorie Dipartimento...

Documents

Transcript of 4/19/2015E. Giovannetti -- OI09.1 Olimpiadi di Informatica 2010 Giornate preparatorie Dipartimento...