Nome: Cognome:

AIW: Compressione Testi

Appello 13/7/2004

1. Scrivere lo pseudocodice dell’algoritmo di decompressione di Huffman canonico applicato a una sequenza binaria B[1,n] assumendo di disporre dei vettori Firstcw, Numcw, Symb, e del valore MaxCwLen. [punti 8]

2. Dimostrare chiaramente la correttezza del codice al punto 1. [punti 3]

3. Quale è la lunghezza massima di una codeword assegnata da Huffman a un simbolo di probibilità p? [punti 3]

4. Se Huffman è applicato a un testo di lunghezza L contenente 5 simboli distinti (quindi L³5), quale sarà la lunghezza massima delle sue codeword? [punti 4]

5. Sia T=“abaabbaabb”, sareste in grado di indicare la lunghezza del compresso prodotto da Huffman senza eseguirlo? Motivare la risposta. [punti 2]

6. Senza eseguire l’algoritmo Aritmetico con modello semi-statico su T=“ababab”, ma sfruttando soltanto la frequenza delle sue lettere, sareste in grado di indicare la lunghezza del compresso da lui prodotto? Motivare la risposta. [punti 4]

7. Indicare un testo sul quale MTF è migliore di Huffman, e dimostrarlo. [punti 4]

8. Fornire un limite superiore alla percentuale di compressione ottenuta da MTF, in funzione dell’entropia H₀. [punti 2]