Nome:                                     Cognome:                                                     Matr.

AIW: Compressione Testi

Appello 5/11/2003

Esercizio 1. [punti 7] 

Sia data la sequenza binaria 00100101001101101 ottenuta codificando tre interi  mediante la giustapposizione dei loro codici DELTA, GAMMA e GOLOMB con k=6, rispettivamente. Indicare i tre interi, commentando brevemente i passi della decodifica. (Nota: Si assuma che Unary(3)=001 e non 110)

Esercizio 2. [punti 11] 

È dato il testo T=“ababcacaaaaabbab”, indicare le tabelle dei contesti costruite dal PPM dopo aver scandito il testo T, con una lunghezza max di contesto pari a 2. Indicare inoltre come il PPM comprime la lettera c usando queste tabelle.

Esercizio 3. [punti 12] 

Sia dato il testo T= "ababcb" con codifica dei caratteri a=1,b=2,c=3. Si consideri una implementazione di LZ77 con finestra illimitata, tabella hash con liste di catenazione e funzione hash h() applicata su coppie di caratteri. 

1. Si spieghi qual'è il vantaggio nell'usare una tabella hash per la ricerca della più lunga sottostringa già vista.     [punti 4]
2. Discutere cosa accadrebbe se h() operasse su quadruple di caratteri, invece di coppie, confrontando il numero delle posizioni potenzialmente verificate con la compressione ottenuta da LZ77.  [punti 3]
3. Sia h(x'x'') = 2(y'+y'') mod 7, dove y' e y'' è la codifica dei caratteri x' e x'' rispettivamente, e si assuma una tabella hash di 7 posizioni.        [punti 5]
   1. Si indichi il contenuto della tabella hash alla fine di T. 
   2. Si assuma di dover comprimere la stringa X="abb" usando la tabella hash del punto 3.1. Quali sono le posizioni di T indicate dalla tabella hash, e "verificate" da LZ77, per comprimere X.