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]