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 H0. [punti 2]