Nome:                             Cognome:                                   Matr.

AIW: Compressione Testi

Appello 29/5/2003

Esercizi:   

1. È data la sorgente: p(a)=1/4, p(b)=1/2, p(c)=1/8,p(d)=1/8. Decomprimere la stringa C=10000011 con l'algoritmo Aritmetico limitandosi soltanto alle prime quattro lettere del testo originale. (Ordinare alfabeticamente le lettere e assegnarle agli intervalli dal basso verso l'alto.) [10 punti]
2. È data la stringa T="abaabaab", si assuma che coder e decoder sappiano che l'alfabeto di riferimento è binario e consiste delle lettere {a,b}.
   1. Eseguire i primi due passi dell'algoritmo bzip: BWT, MTF; e poi comprimere ciascun numero della lista così ottenuta attraverso il codice GAMMA. Calcolare la  compression ratio. [10 punti] 
   2. Come cambiereste la sequenza BWT+MTF+GAMMA per ottenere una compressione migliore ? E quanto guadagnereste in termini di compression ratio. [6 punti] 
3.   Dimostrare che un codice univocamente decodificabile per essere ottimo deve assegnare codeword lunghe a simboli poco frequenti. [6 punti]