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 ?