Nome:                             Cognome:                                EMAIL:

AIW: Compressione Testi

Appello 7/7/2003

Esercizi:   

1. Comprimere il testo T="aabaaba" mediante l'algoritmo LZW, assumendo un trie per il dizionario inizializzato con le due stringhe "a" (codice 1) e "b" (codice 2). Codificare infine ogni numero prodotto da LZW con il codice GAMMA. [10 punti]
2. Sia dato il testo T="aabaaabab" e si consideri l'algoritmo PPM con lunghezza massima di contesto pari a 3.
   1. Indicare le tabelle dei contesti disponibili al PPM immediatamente prima di comprimere l'ultimo carattere di T, ossia l'ultima 'b'.  [8 punti] 
   2. Utilizzando le tabelle del punto precedente, indicare la sequenza di simboli e le loro frequenze inviati dal PPM al successivo coder statistico per la compressione dell'ultimo 'b' di T. [4 punti]  
3. Comprimere il testo T=“ababacaababb” mediante gli algoritmi LZ77 e LZ78. [9 punti]