Un piccolo esperimento di compressione dati

Di leonardo maffi
Versione 0.1 del 2002 10 5.

Introduzione per chi non è esperta/o

Ipotizziamo di dover trasmettere pochi dati lungo un canale di trasmissione lentissimo (ad esempio con una sonda spaziale molto lontana, o un sottomarino in immersione col quale si comunica con onde radio a frequenze bassissime) o tramite un supporto di memorizzazione dalla capienza minimale (ad esempio una piastra metallica incisa). Ipotizziamo anche che si sistemi posti ai due estremi del canale di comunicazione dispongano di elevate capacità di calcolo e anche di una certa quantità di informazioni che si erano scambiati in precedenza.

In questa situazione (i dati in queste prove sono di tipo testuale) si può pensare di usare un programma di compressione dati (come lo Zip), che sia a disposizione di mittente e destinatario. Questo migliora la situazione, ma non molto, in quanto se i dati sono pochi (ad esempio meno di 20 kB) il tasso di compressione di risulterà basso, perché il programma di compressione non dispone materiale a sufficienza per costruire un dizionario statistico accurato.

Per migliorare la situazione si può fornire a priori sia al mittente che destinatario un pacco di dati che siano statisticamente simili a quelli del messaggio da comprimere, in modo da dargli modo di formare delle statistiche migliori.

Per farlo si può usare direttamente un programma di compressione chiamato ACB (Associative Coder). Oppure si può usare metodi più rustici. Qui mostro un esperimento realizzabile in pochi minuti con un sistema Windows (per ripetere questo esperimento servono almeno 256 MB di RAM) e software gratuito, e senza scrivere programmi.

Il materiale usato è:

a, b: due file di testo Txt in italiano, usati per fare il test. Il primo (a) è di oltre tre megabyte e mezzo (3'642'484 byte) e viene usato come database statistico condiviso, il secondo (b) è di meno di venti kilobyte (19'265 byte).

Xdelta per windows, versione 1.1.3:
http://www.eng.uwaterloo.ca/~ejones/software/xdelta-win32.html

PPmonstr versione I1 (e PPMD var.I 1):
ftp://ftp.elf.stuba.sk/pub/pc/pack/ppmdi1.rar

Il tasso di compressione ottenuto zippando b (regolato a massima compressione) è molto basso (3.51 bpc, cioè bit necessari per codificare un carattere del testo). Per il primo (a) è migliore (ma comunque alto, 2.7 bpc).

Se ipotizziamo che mittente e destinatario dispongano di molta potenza di calcolo e RAM, allora si può usare PPMD-PPmonstr che forse è il miglior compressore testuale del momento, che infatti è stato integrato nel WinRar3 (ne esiste uno leggermente migliore, ma non è facilmente reperibile, si chiama Entropy. Qui si può vedere all'opera: http://www.geocities.com/SiliconValley/Bay/1995/texts24.html).

Nella tabella sotto si può vedere la differenza rispetto allo zip è piuttosto elevata, soprattutto per il file a. Si noti che per comprimere tale file PPmonstr con questi parametri (Ordine 32) utilizza circa ben 180 MB di RAM, ma ottiene meno di 1.6 bit per carattere, che considerando che il file non era del tutto pulito, includeva maiuscole e punteggiatura, eccetera, è un risultato eccellente (Shannon stimava che un testo senza punteggiature e lettere maiuscole potesse avere un'entropia intrinseca di circa 1 bpc). Il file b viene compresso solo a 2.8 bpc, dato che PPmonstr non ha dati a sufficienza per poter creare delle statistiche affidabili (PPmonstr internamente sfrutta giù alcune caratteristiche del testo).

Per fare l'esperimento ho costruito il file a+b unendo il file b in coda al file a. Poi ho compresso sia a che ab usando PPmonstr, ottenendo i file a.p e a+b.p.

I file a.p e a+b.p sono simili perché i compressori dati come PPmonstr sono incrementali, cioè man mano incontrano dati da comprimere, accumulano in un file il risultato compresso. Per cui sia i file a+bche a+b.p hanno tutta la loro prima parte in comune rispettivamente coi file a e a.p.

Per cui adesso basta creare un file differenza. Questo può essere fatto con un programma apposito, Xdelta col seguente comando:

Xdelta delta -- noverify a+b.p a.p a+b.px
(--noverify riduce leggermente la lunghezza del file differenza).

Il file risultante a+b.px è di soli 4'392 bytes, il che corrisponde a 1.8 bpc. Quindi siamo passati da 2.8 e 1.8 bpc.
a+b.px insieme a b.p sono sufficienti per ricostruire (usando Xdelta al contrario) b.p e quindi b (usando PPmonstr).
Si noti che ci sono circa 200 byte di overhead nel file differenza a+b.px, ma parte di tale overhead è dovuto anche agli header diversi di a.p e a+b.p (che contengono ad esempio il nome del file e la lunghezza e forse dei codici CRC di controllo, eccetera).

  Byte            bpc
3'642'484  a       8
1'236'808  a.zip   2.716 (massima compressione)

  720'712  a.p     1.582 (PPmonstr I1 -o32 -m200)

   19'265  b       8
    8'458  b.zip   3.512 (massima compressione)
    6'840  b.p     2.84  (PPmonstr I1 -o32 -m200)

3'661'749  a+b 8
  724'918  a+b.p         (Ppmonstr I1 -o32 -m200)
    4'392  a+b.px  1.823 (--noverify)

4'206 a+b.p-a.p 1.74

Bpc = bit per carattere del testo.
a, b = file di testo.
p = file prodotti da PPmonstr (versione I 1) -o32 -m200
x = file prodotti da Xdelta per Windows (versione 1.1.3).

Tutto questo processo può ovviamente essere automatizzato, anche se è molto lento (la compressione e decompressione con PPmonstr usato a questi livelli è abbastanza lenta). Integrando Xdelta e PPmonstr in un unico programma (i loro sorgenti sono disponibili gratuitamente) si può risparmiare qualche altro byte di overhead.

Rimane la discrepanza tra 1.74 bpc del file differenza (ignorando l'overhead) e la compressione di solo a (1.582 bpc). Non so da cosa possa sia causata, forse dal fatto che b non è proprio simile alla media dei testi contenuti in a (cioè b ha una entropia maggiore della media di a).

[Indice]