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]