Nome: Cognome: Matr.

AIW: Compressione Testi

Appello 16/1/2004

Sia data la stringa T=“abababaabaabab”.

1. Illustrare il funzionamento di LZ77 nel comprimere T. [punti 6]

2. Illustrare il funzionamento di LZ78 nel comprimere T. [punti 6]

3. Illustrare il funzionamento di LZW nel comprimere T, assumendo il dizionario iniziale {a,b} con codifica {1,2} rispettivamente. [punti 7]

4. Si esegua l’algoritmo Aritmetico su T , con modello semi-statico, mostrando soltanto i primi 5 passi. [punti 8]

5. Con riferimento al punto precedente si calcoli la lunghezza del compresso di T (NOTA: senza determinare l’intervallo finale). [punti 3]