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]