AIW: Compressione Testi
Compitino 19/12/01
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.
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.