Nome: Cognome: Matr.

AIW: Compressione Testi

Appello 27/5/2002

Sia dato il testo T = “wewereherewewerethere”.

1. Costruire l’albero di Huffman sulle lettere di T, con modello semi-statico. Si indichino inoltre le codeword per la variante Huffman canonico specificando il metodo adottato per calcolarle. [punti 10]

2. Si fornisca la codifica LZW di T, assumendo il dizionario {e,h,r,t,w} con codifica delle lettere {1,2,3,4,5} rispettivamente. [punti 13]

3. Si consideri il seguente codice Byte-aligned: dato un intero x, esso suddivide la sua rappresentazione binaria in gruppi di 7 bit, e li memorizza poi in una sequenza di byte nei quali il primo bit del primo byte è posto a 1, mentre il primo bit degli altri byte è posto a 0. Si indichi la compressione degli interi 35 e 150. Si calcoli la lunghezza della codeword da lui prodotta, in funzione del numero intero x da comprimere. Si confronti questa lunghezza con quella del Gamma-coding(x) indicando così un intervallo di interi per i quali Byte-aligned è migliore del Gamma-coding. [punti 7]