Nome: Cognome: Matr.
AIW: Compressione Testi
Appello 29/5/2003
Esercizi:
- È data la sorgente: p(a)=1/4, p(b)=1/2, p(c)=1/8,p(d)=1/8. Decomprimere la stringa C=10000011 con l'algoritmo Aritmetico limitandosi soltanto alle prime quattro lettere del testo originale. (Ordinare alfabeticamente le lettere e assegnarle agli intervalli dal basso verso l'alto.) [10 punti]
- È data la stringa T="abaabaab", si assuma che coder e decoder sappiano che l'alfabeto di riferimento è binario e consiste delle lettere {a,b}.
- Eseguire i primi due passi dell'algoritmo bzip: BWT, MTF; e poi comprimere ciascun numero della lista così ottenuta attraverso il codice GAMMA. Calcolare la compression ratio. [10 punti]
- Come cambiereste la sequenza BWT+MTF+GAMMA per ottenere una compressione migliore ? E quanto guadagnereste in termini di compression ratio. [6 punti]
- Dimostrare che un codice univocamente decodificabile per essere ottimo deve assegnare codeword lunghe a simboli poco frequenti. [6 punti]