Nome:                             Cognome:                                   Matr.

AIW: Compressione Testi

Appello 7/1/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=0110101 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.  Si prendano le ultime 2 cifre del proprio numero di matricola, si sommi ad esse il valore 51, e si calcoli il codice DELTA del numero cosi' ottenuto. [5 punti]
3.  Sia dato un testo T e sia [l,r] l'intervallo identificato con la compressione di T mediante l'algoritmo Aritmetico. Si indichi, in funzione di l e r, il numero reale scelto per identificare l'intervallo suddetto e il numero di bit utilizzati per la sua rappresentazione approssimata. Si dimostri che tale numero reale e' interno all'intervallo [l,r]. [9 punti]
4. Sia B[1,n] un vettore binario, B[i] Î{0,1}, contenente il compresso di un testo T secondo l'Huffman Canonico. Progettare un algoritmo che decomprime le codeword contenute in B e stampa in output i simboli corrispondenti. Indicare anche le strutture dati utilizzate e la loro inizializzazione.     [8 punti]