Nome:                             Cognome:                                   Matr.

AIW: Compressione Testi

Appello 5/2/2003

Esercizi:   

1. Sia dato il testo T="cabab".
   1. Calcolare la sequenza di bit del compresso di T secondo l'algoritmo Aritmetico. [8 punti] 
   2. Se ogni carattere di T occupa 8 bit, qual'e' la percentuale di compressione? [2 punti]
2. Sia dato il testo T= "abababb". 
   1. Indicare il risultato < L,r > della trasformata di Burrows-Wheeler applicata a T. [4 punti]
   2. Indicare il risultato della compressione di T mediante LZ77 e LZ78. [6 punti]
3. Sia dato l'alfabeto S={a,b,c} e la sequenza di interi C=<1,1,2,3,5,8,3,10> ottenuta comprimendo un testo T mediante l'algoritmo LZW. 
   1. Decomprimere C assumendo che i caratteri di S formino le prime 3 frasi del dizionario di LZW con numerazione 1,2,3, rispettivamente. [6 punti] 
   2. Quali codici di C richiedono l'esecuzione del "passo speciale" di decodifica in LZW ? [2 punti] 
4. Dimostrare che il codice a=1, b=00, c=01 e' ottimo per la sorgente p(a)=1/2, p(b)=p(c)=1/4. [4 punti]