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.