Nome:                             Cognome:                                   Matr.

AIW: Compressione Testi

Appello 20/6/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=10000001 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. È data la stringa T="abccbccbddb", indicare il risultato delle trasformazioni BWT e poi MTF, assumendo che coder e decoder siano a conoscenza del fatto che T è costruito sull'alfabeto {a,b,c,d}. Comprimere infine ciascun numero della sequenza MTF così ottenuta attraverso il codice GAMMA. [14 punti] 
3. Date le due colonne F e L prodotte dalla trasformata di Burrows-Wheeler, dimostrare che l'i-esima occorrenza del carattere c su F corrisponde all'i-esima occorrenza del carattere c su L, qualunque sia il carattere c dell'alfabeto. [6 punti]