Nome: Cognome: Matr.

AIW: Compressione Testi

Appello 12/2/2002

Sia dato il testo T = “aaabcbbaaa”.

1. Illustrare il funzionamento dell’algoritmo Aritmetico sul testo T, con modello semi-statico, indicando inoltre il testo compresso da lui prodotto. [punti 15]

2. Con riferimento all’esercizio 1, indicare per ogni passo dell’algoritmo Aritmetico i bit del file compresso che potrebbero essere emessi in output immediatamente, senza attendere l’intera scansione di T. (motivare la risposta) [punti 6]

3. Sia T’ la stringa ottenuta permutando arbitrariamente le lettere di T. Servendosi della formula adottata dall’algoritmo Aritmetico per calcolare la lunghezza del file compresso, dimostrare che il compresso di T’ ha la stessa lunghezza del compresso di T (qualunque sia la permutazione). [punti 4]

4. Sia data una sorgente che emette numeri interi positivi x con probabilità 2^-x. Indicare, per ogni intero x, la lunghezza della codeword nel codice ottimo ideale. Indicare due codici ottimi, selezionati tra quelli visti in classe. [punti 5]