Esperimenti sulla stima entropica

Di leonardo maffi

Versione 0.5 del 18 Gennaio 2003.

[Scarica il software in Delphi 5 e i dati risultanti (zippati).]

Contenuti:
Qui mostro e discuto delle misurazioni su come muta localmente l'entropia di alcuni file, e al contempo come si comportano alcuni compressori dati man mano che accumulano informazioni (statistiche) sul file che vanno comprimendo. Ho eseguito queste misurazioni perché non sono riuscito a trovare niente di simile altrove, e l'argomento mi pareva interessante.

Nota per la stampa: questo documento contiene grafici nei quali i colori sono usati per denotare dati diversi. Stampandolo in B/N è possibile che parte di tali informazioni vengano perse. Scusate.

Dati su cui sono state fatte le misurazioni:
Ho scelto due file ben noti e facilmente reperibili, in modo da rendere queste misurazioni più ripetibili, per cui ho usato due file tratti dalla suite di test ACT:
http://compression.ca/act-files.html
- Il file testuale è la traduzione inglese dei Tre Moschettieri, di Alexandre Dumas, (490 KB zippati, 1'344'379 byte non zippati):
ftp://sunsite.unc.edu/pub/docs/books/gutenberg/etext98/1musk10.zip
- Un file eseguibile su Windows, Netscape Navigator v4.06 (1352 KB zippato, 2'934'336 byte non zippati):
http://compression.ca/files/act2-netscape406.zip

Compressori utilizzati:
Per fare i test di compressione e stima entropica ho utilizzato alcuni dei migliori programmi disponibili, dato che i compressori migliori si avvicinano di più alla "vera entropia", anche se per alcuni motivi non sempre i migliori in assoluto (nota: in questo documento non mi riferisco all'entropia di Shannon di ennesimo ordine, ma a quella calcolata sul contesto, cioè ai valori di entropia che si ottengono comprimendo un file con software che lavorano su contesti a lunghezza più o meno variabile. Di solito su file normali i valori dell'entropia contestuale sono significativamente minori dell'entropia di Shannon di ordine 0, 1, 2 o anche più.).
Per fare queste misurazioni ho dovuto fare moltissime prove di compressione, automatizzate attraverso dei programmini Delphi, per cui ho utilizzato compressori a linea di comando (per questo ho utilizzato Compressia V. 0.98 e non 0.99b, dato che quest'ultimo non funziona a linea di comando. Vista la quantità di misurazioni che dovevo fare (cioè di compressioni dati) ho dovuto scegliere dei compressori molto veloci. Fortunatamente alcuni dei compressori migliori sono anche molto veloci (ad esempio PPMnostr).
Molti di questi compressori possono essere trovati qui:
http://ftp.unicamp.br/pub/pc/archivers/
http://ftp.vse.cz/msdos/SAC/pc/pack/
Compressori utilizzati:
- PKZIP V. shareware 2.04g del 02-01-93.
- Compressia 0.98 beta, è basato sull'algoritmo BWT (trasformazione a blocchi con ordinamento), e sfrutta una serie di filtri testuali (la versione 0.99b con interfaccia grafica ha anche un filtro specifico per testi in Inglese).
http://www.compressia.com/
- PPMonstr V. i1, di Dmitry Shkarin, compressore PPMII ottimizzato per la velocità. Una variante è utilizzata anche nel 7-Zip, nel WinRar3+, e in Entropy (attualmente il miglior compressore testuale)
http://ftp.unicamp.br/pub/pc/archivers/ppmdi1.rar
- Rar 3 a linea di comando, basato su una variante di PPMmonstr, ma grazie all'applicazione automatica di vari filtri e vari algoritmi, è più stabile al variare del tipo di file.