Nome: Cognome:

AIW: Compressione Testi

Appello 17/9/2004

1. Siano F e L la prima e l’ultima colonna, rispettivamente, della matrice costruita dalla trasformata di Burrows-Wheeler applicata a un testo T[1,n].

a. Dimostrare che F e L sono permutazioni di T. [punti 2]

b. Dimostrare che la i-esima lettera x su F corrisponde alla i-esima lettera x su L, qualunque sia la lettera x. [punti 6]

c. Descrivere la struttura dell’algoritmo Bzip [punti 2]

d. Motivare la scelta dei vari moduli di Bzip. [punti 3]

2. Sia T=“bcbcbcbbcbbcbc” e si consideri l’algoritmo aritmetico con modello semi-statico.

a. Si mostri il calcolo degli intervalli per le prime 5 lettere di T. [punti 7]

b. Si calcoli la lunghezza in bit del compresso di T, senza comprimere tutto T. [punti 5]

3. Formare tre interi x, y, z dividendo il proprio numero di matricola in coppie di cifre adiacenti. Codificare x con il codice Gamma, y con il codice Delta e z con il codice Golomb di parametro k=3. [punti 1+2+2]