Nome: Cognome:

Compressione

Appello 1/6/2004

Esercizi

1. È data la stringa L = “ard#rcaaaabb” e l’intero I=4. Applicare la trasformata INVERSA di Burrows-Wheeler alla coppia <L,I> assumendo che il carattere # sia più piccolo di ogni altro. Dettagliare la risposta. [punti 10]

2. Si consideri l’algoritmo di Huffman canonico e si decomprima la stringa:

C = 10100111000100110100111, utilizzando la tabella symb[length] e il vettore FirstCW[length] definiti come: symb[3]={c,d,b,r} e FirstCW[3]=000, symb[1]={a} e FirstCW[1]=1. Dettagliare la risposta. [punti 10]

3. Si consideri l’algoritmo Aritmetico e si decomprimano i primi 3 simboli dalla sequenza binaria C=0001100101 assumendo che l’alfabeto sia formato dai simboli {a,b,n} e le loro probabilita’ siano, rispettivamente: 0.5, 0.16, 0.34. Dettagliare la risposta, partizionando gli intervalli secondo la sequenza [b,a,n] dal basso verso l’alto. [punti 10]