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]