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]