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.