Nome:                      Cognome:                     Matr.


AIW: Compressione Testi

Compitino 5/11/2002



Esercizio 1. [punti 6] 

Costruire il codice di Shannon-Fano per la sorgente che emette i simboli {a,b,c,d,e} con probabilità pa=0.36, pb=0.17, pc=0.17, pd=0.16, pe=0.14.












Esercizio 2. [punti 9]

È dato il testo T=“aaabaaabaabbccbbddeee”, indicare l'albero di Huffman; e poi il contenuto dei vettori FCW, NCW e SYMB ottenuti dall'algoritmo canonico (SYMB[j] è la lista dei simboli al livello j dell'albero).



Esercizio 3. [punti 9] 

È dato il testo T=“ababacaaaaabbabb”, indicare il risultato della compressione secondo l'algoritmo LZ77. Inoltre, indicare cosa cambia (se cambia) e come la compressione se si impone una limitazione a una finestra di 4 caratteri.



















Esercizio 4. [punti 5]  È dato il codice d(x)=001111100110, indicare il valore di x.








Esercizio 5. [punti 3]  Nel caso in cui l'esecuzione dell'algoritmo di Huffman porti a costruire tre o più nodi aventi la stessa probabilità, come si scelgono i due nodi da fondere per minimizzare la profondità dell'albero ?



Nome:                      Cognome:                     Matr.


AIW: Compressione Testi

Compitino 5/11/2002



Esercizio 1. [punti 6]

Costruire il codice di Shannon-Fano per la sorgente che emette i simboli {a,b,c,d,e} con probabilità pa=0.38, pb=0.18, pc=0.16, pd=0.14, pe=0.14.













Esercizio 2. [punti 9]

È dato il testo T=“bbbaaabbaaaaccbbddfffeee”, indicare l'albero di Huffman; e poi il contenuto dei vettori FCW, NCW e SYMB ottenuti dall'algoritmo canonico (SYMB[j] è la lista dei simboli al livello j dell'albero).


Esercizio 3. [punti 9] 

È dato il testo T=“ababaabbababbbaaa”, indicare il risultato della compressione secondo l'algoritmo LZ77. Inoltre, indicare cosa cambia (se cambia) e come la compressione se si impone una limitazione a una finestra di 4 caratteri.























Esercizio 4. [punti 5]  È dato il codice d(x)=011110, indicare il valore di x.









Esercizio 5. [punti 3]  Nel caso in cui l'esecuzione dell'algoritmo di Huffman porti a costruire tre o più nodi aventi la stessa probabilità, come si scelgono i due nodi da fondere per minimizzare la profondità dell'albero ?



Nome:                      Cognome:                     Matr.


AIW: Compressione Testi

Compitino 5/11/2002



Esercizio 1. [punti 6]

Costruire il codice di Shannon-Fano per la sorgente che emette i simboli {a,b,c,d,e} con probabilità pa=0.35, pb=0.21, pc=0.16, pd=0.14, pe=0.14.












Esercizio 2. [punti 9]

È dato il testo T=“aaffbbbaaaaccbbddee”, indicare l'albero di Huffman; e poi il contenuto dei vettori FCW, NCW e SYMB ottenuti dall'algoritmo canonico (SYMB[j] è la lista dei simboli al livello j dell'albero).



Esercizio 3. [punti 9] 

È dato il testo T=“ababcdaabbcb”, indicare il risultato della compressione secondo l'algoritmo LZ77. Inoltre, indicare cosa cambia (se cambia) e come la compressione se si impone una limitazione a una finestra di 4 caratteri.























Esercizio 4. [punti 5]  È dato il codice d(x)=0010111001, indicare il valore di x.











Esercizio 5. [punti 3]  Nel caso in cui l'esecuzione dell'algoritmo di Huffman porti a costruire tre o più nodi aventi la stessa probabilità, come si scelgono i due nodi da fondere per minimizzare la profondità dell'albero ?





Nome:                      Cognome:                     Matr.


AIW: Compressione Testi

Compitino 5/11/2002



Esercizio 1. [punti 7]

Costruire il codice di Shannon-Fano per la sorgente che emette i simboli {a,b,c,d,e} con probabilità pa=0.39, pb=0.17, pc=0.16, pd=0.16, pe=0.12.













Esercizio 2. [punti 9]

È dato il testo T=“aabbaaaaccbbbddeee”, indicare l'albero di Huffman; e poi il contenuto dei vettori FCW, NCW e SYMB ottenuti dall'algoritmo canonico (SYMB[j] è la lista dei simboli al livello j dell'albero).


Esercizio 3. [punti 9] 

È dato il testo T=“cabababababbc”, indicare il risultato della compressione secondo l'algoritmo LZ77. Inoltre, indicare cosa cambia (se cambia) e come la compressione se si impone una limitazione a una finestra di 4 caratteri.




















Esercizio 4. [punti 5]  È dato il codice d(x)=001111101110, indicare il valore di x.












Esercizio 5. [punti 3]  Nel caso in cui l'esecuzione dell'algoritmo di Huffman porti a costruire tre o più nodi aventi la stessa probabilità, come si scelgono i due nodi da fondere per minimizzare la profondità dell'albero ?