AIW: Compressione Testi

Compitino 19/12/01

 

 

 

Esercizio n. 1 (punti 15)

 

Sia data la stringa S=`abcdmaataa`. Si costruisca la stringa T appendendo a S le prime 3 lettere del proprio nome e le prime 3 lettere del proprio cognome.

 

  1. Si esegua l’algoritmo di Huffman Canonico su T mostrando l’albero ottenuto e calcolando le firstcw, le numcw, e la tabella symb.   [punti 11]
  2. Sia y il numero ottenuto sommando la frequenza della lettera `a’ in T con la cifra più a destra del proprio numero di matricola.  Si codifichi y utilizzando i codici Gamma e Delta.  [punti 4]

 

 

Esercizio n. 2 (punti 15)

 

Si costruisca la stringa S1 come concatenazione delle prime 4 lettere del proprio nome e delle prime 4 lettere del proprio cognome, e si consideri inoltre la stringa S2 = `aaeeaaee`. Si costruisca da S1 e S2 la stringa T tale che

 

T[2i-1] = S1[i] e T[2i] = S2[i], con 1 £ i £ 8

 

ossia T consta di 16 caratteri, i caratteri in posizione dispari di T danno la stringa S1 mentre quelli in posizione pari danno la stringa S2.

1.     Si calcoli la trasformazione di Burrows-Wheeler della stringa T, e si indichi il risultato con la coppia (n,L).

2.     Sia L la lista formata da tutti i caratteri distinti di T e ordinata alfabeticamente. Si mostri il funzionamento dell’algoritmo Move-To-Front applicato alla stringa L con lista iniziale L.