AIW: Compressione Testi
Appello 23/1/2002
Esercizio 1
1.
Calcolare il
codice di Fano per la sorgente {p(a)=1/4, p(b)=1/16, p(c)=1/8, p(d)=1/16,
p(e)=1/2}. Discutere inoltre la sua ottimalità. [punti
5]
2.
Sia data la
sorgente: p(a)=1/4, p(b)=1/2, p(c)=1/4. Decomprimere la stringa C=010111 con
l’algoritmo Aritmetico eseguendo solo i primi 3 passi (ossia, decomprimiamo
solo le prime tre lettere). [punti 10]
Esercizio 2
Sia data la stringa T=“abababaabaabab”.
1.
Illustrare
il funzionamento di LZ77 nel comprimere T. [punti
5]
2.
Illustrare
il funzionamento di LZW nel comprimere T. [punti
7]
3.
Eseguire la
decompressione della stringa prodotta nell’esercizio precedente indicando i
passi in cui si verifica il “caso speciale” di LZW. [punti
3]