Nome: Cognome: Matr.
AIW: Compressione Testi
Appello 5/2/2003
Esercizi:
- Sia dato il testo T="cabab".
- Calcolare la sequenza di bit del compresso di T secondo l'algoritmo Aritmetico. [8 punti]
- Se ogni carattere di T occupa 8 bit, qual'e' la percentuale di compressione? [2 punti]
- Sia dato il testo T= "abababb".
- Indicare il risultato < L,r > della trasformata di Burrows-Wheeler applicata a T. [4 punti]
- Indicare il risultato della compressione di T mediante LZ77 e LZ78. [6 punti]
- Sia dato l'alfabeto S={a,b,c} e la sequenza di interi C=<1,1,2,3,5,8,3,10> ottenuta comprimendo un testo T mediante l'algoritmo LZW.
- Decomprimere C assumendo che i caratteri di S formino le prime 3 frasi del dizionario di LZW con numerazione 1,2,3, rispettivamente. [6 punti]
- Quali codici di C richiedono l'esecuzione del "passo speciale" di decodifica in LZW ? [2 punti]
- Dimostrare che il codice a=1, b=00, c=01 e' ottimo per la sorgente p(a)=1/2, p(b)=p(c)=1/4. [4 punti]