Nome: Cognome:

AIW: Compressione Testi

Appello 22/6/2004

1. Sia data la stringa T=“abcabcabcab”. Illustrare il funzionamento di LZW nel comprimere T, assumendo il dizionario iniziale {a,b,c} con codifica {1,2,3} rispettivamente. [punti 8]

2. Sia data la stringa T=“banana”. Si esegua l’algoritmo Huffman dinamico su T. [punti 10]

3. Scrivere lo pseudo-codice dell’algoritmo Aritmetico per comprimere un testo T[1,n], nell’ipotesi di precisione infinita. [punti 12]