Nome: Cognome: Corso:

Compressione

Appello 12/7/2002

Esercizi

1. È data la sorgente: p(a)=1/4, p(b)=1/2, p(c)=1/4. Decomprimere la stringa C=0110001 con l’algoritmo Aritmetico eseguendo solo i primi 4 passi (ossia, decomprimiamo solo le prime quattro lettere). [punti 5]

2. È data la stringa L = “errhwhrwteeeeee#” e l’intero I=16. La coppia <L,I> indica l’output della trasformata BWT applicata a una stringa di 16 caratteri (il carattere # si assume più piccolo di ogni altro). Eseguire la trasformata inversa di BWT a partire dalla coppia <L,I>. [punti 10]

3. È dato il testo T=“xxyxyx” e un compressore PPM con lunghezza massima di contesto uguale a 2. Eseguire PPM su T indicando per ogni suo carattere l’insieme dei contesti e le probabilità di predizione di ogni simbolo {x,y,ESC} in ciascuno di essi. [punti 9]

4. Utilizzando i contesti al punto 3, indicare la sequenza di simboli e le probabilità che PPM invierebbe a un coder statistico nell’ipotesi di dover codificare dopo T il simbolo x. [punti 6]