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]