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]