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]