5 Dic. 1998
Sfida Compressori, percentuali residue:
Compressors Contest, residual percentages:
 

Quella che segue è una sfida fra compressori lossless, cioè senza perdita di qualità. Viene fornito un insieme di file tipici per vedere quale programma per Dos/Win9x produce i file di output più corti. Questa piattaforma è stata scelta perchè, insieme a quella Unix/Linux, è quella che dispone dei migliori compressori. Alcuni di questi file sono tratti da archivi nati per scopi simili a questo, come Book1 tratto dal Calgary Corpus o l'immagine di Lena. Questi file non rappresentno il contenuto medio di una directory di Hd:, sono rappresentanti tipici di quante più categorie di dati possibili.
Questo confronto non è stato svolto in maniera massimamente seria e oggettiva, perchè i files sono stati scelti apposta per ottenere un certo risultato. Comunque sono file reali, non generati allo scopo, eccetto una coppia. Lo scopo che ho voluto ottenere è piuttosto particolare. Mi spiego: non esistono file oggettivi per verificare l'efficienza di un compressore entropico. Per qualunque di essi esiste un file o una classe di file sui quali produce un risultato pessimo. L'unica cosa da fare è fare moltissime prove con file reali differenti e sperare che i risultati medi siano sensati. Io ho usato per molti mesi tutti questi compressori e ho imparato quali sono i punti di forza  e i punti deboli di ciascuno. Questa prova avrebbe potuto essere fatta con migliaia di file, seguita da solida analisi statistiche. Ma sarebbe stato molto difficile poter distribuire i file della sfida ad altri. Per cui ho deciso di seguire un'altra strada, apparentemente meno oggettiva. Ho scelto una serie di file allo scopo di mostrare ciò che avevo imparato sui compressori. Questi file sono stati scelti perchè mostarvano i migliori e i peggiori risultati per ciasun compressore, pur rimanendo file reali. Come si vede dalla tabella sotto, quasi ogni compressore ha vinto per almeno per un file. Sarebbe stato abbastanza facile scegliere file per far vincere sempre uno dei migliori compressori. Ma non era il mio scopo. Ad esempio ho mostrato che 777 è mediamente il migliore per file eseguibili, ma sarebbe stato facile scegliere un sigolo eseguibile per far vincere Boa, Acb, Rkive, e usando file sintetici praticamente qualsiasi compressore della lista. Quindi i risultati sotto rispecchiano i risultati che potremmo ottenere da medie di grandi quantitativi di file, sono risultati tipici. Se ci sono eccezzioni lo dirò. In un certo senso ho fatto in modo da far vincere tutti, almeno una volta. La varianza dei risultati è quindi molto alta (non vincono sempre gli stessi pochi compressori).
Esistono almeno altre tre sfide fra compressori, ma il loro scopo è differente. La più famosa è probabilmente l'Act (A.C.T.: Archive Comparison Test, di Jeff Gilchrist,  jeffg@nbnet.nb.ca , http://personal.nbnet.nb.ca/jeffg/act.html, possiede due mirror). La sua sfida confronta molti più compressori di me, quasi tutti, (io provo solo i migliori) e misura anche i tempi di esecuzione. Però ha pochi file di confronto. Recentemente è in ristrutturazione con un mumero maggiore di file, ma sempre di pochi tipi. Il difetto di questa prova è che si basa su pochi file e non ne giustifica la scelta. Comunque credo che l'autore sia sempre in buona fede.
L'altra sfida nota è The Art of Lossy:http://www.geocities.com/SiliconValley/Bay/1995/artest9.html, essa si occupa solo di compressione lossless di immagini, ma la prova è svolta in maniera migliore perchè i file provati sono moltissimi. (nonostante ciò i risultati non sono totalmente a favore di un vincitore).
Esiste un'altra sfida,Waterloo Bragzone, apparentemente più oggettiva.
L'Act non mi sembra che confronti WavArc e Bmf, e The Art of Lossy non prova l'ultima versione di Bmf. Io cerco di dare spiegazioni utili su come e quali compressori usare in ciascuna situazione, ed ho cercato di spiegare le caratteristiche dell'informazione contenuta nei file della prova, cosa che altre sfide non mi sembrano fare.
Se si è in disaccordo in qualsiasi cosa ho scritto prego di farmelo sapere per email. Io comunque non ho intenzione di offendere nessun autore di compressori, dato che è grazie a questi pochi singoli che oggi disponiamo di software funzionante allo stato dell'arte, talvolta la cui efficienza, ottenuta con esperienza pratica, supera i risultati teorici di vari algoritmi sperimentali. Il futuro Zip è fra questi!

Oltre che sul sito dell'Act, si possono trovare i compressori via Ftp in: ftp://ftp.elf.stuba.sk/pub/pc/pack/
Mirror italiano: ftp://ftp2.itb.it/pub/PC/SAC/pack/
Compression pointers:  http://www.internz.com/compression-pointers.html

Qualche nota sparsa. Questa pagina sarà aggiornata ogni volta che troverò compressori migliori. Io mi baso soprattutto sull'ACT come indice di compressori.
Le immagini da comprimere hanno una struttura entropica molto molto differente fra loro, ma ce ne sono molte di animali e furry. Non ho idea di quante persone vedranno la mia sfida e cercheranno la mie immagini di test, comunque ho fatto in modo che fosse materiale gradevole. (book1 del Calgary lo hanno moltissime persone, ma non ho idea di quante lo abbiano letto. Il Canterbury Corpus fa diffondere anche fra i computer delle informazioni molto diffuse per altre vie: ad esempio l'intero genoma del E. coli, che tutti abbiamo im miliardi di leggere varianti nell'intestino...)
Per il momento, a causa dello spazio limitato, non posso mettervi in linea tutto il materiale usato nella sfida, zippato occupa circa 6.6MB.
Da notare che ci possono essere lievi "imprecisioni" nelle misure: riporto le lunghezze in byte dei files salvati su disco, header inclusi.
Perchè una sfida fra compressori lossless? I compressori lossless sono più oggettivi da confrontare: la dimensione è un numero discreto sempre uguale, e il tempo di calcolo è quasi costante e oggettivo. Non è facile confrontare oggettivamente i differenti difetti dei risultati dei jpg, wavelet, frattale, Ac3, mp3, vqf, ecc. Inoltre spesso le compressioni lossless sono indispensabili: durante il lavoro su una immagine o un file audio si devono usare questi metodi di salvataggio, altrimenti dopo ripetuti caricamenti e salvataggi, il materiale risulta rovinato...

Versione in Excel95 e Exel5 in Italiano, zippata (35KB): SfidaComp_ita.zip
Version in Excel95 and Exel5 in English, zipped (34KB): SfidaComp_eng.zip

File      Orig WinZip Rkive Acb   777  Boa58  Loco  Eri5 Minerva Gif Bmf0.3  Wa  WinRar Szip Uharc %Smallest

Book1     (txt) 40,1  27    28,4  28,8  27                                        35,7  28,9  34,8   27      Book1
Caso150         91,2  92,5  96,5  91,2  92,3                                      91,4  91,3  97,4   91,2    Caso150
Caso50          72,3  71,6  77,2  72,4  71,9                                      73,5  72,2  71,6   71,6    Caso50
Dreams     xm   57,6  56,7  52,1  51,6  53,3                                      53,9  54,6  50,1   50,1    Dreams
Enya S16   wav  83,3  84,5  78    72,4  57                                  43,8  56    56,2  55,6   43,8    Enya S16
Gard       ppm  91,7  81,5  85    75,5  84    75,9  54,9              50,8        86,7  80,7  62,5   50,8    Gard
Istogra    bmp   1,4   1,1   1,1   0,8   1,2         6,4   1,4   9,4   0,8        1,1   3,5   1      0,8     Istogra
Lena       pgm  89,4  68,9  74,4  69,5  68,7  57,6  65,8       106,3  56,2        67,4  70    64,3   56,2    Lena
Midi       mid  41,2  32    35,7  39,8  34,7                                      38,2  43,8  37     32      Midi
Mozart 16  wav  85,6  72,5  72,5  65,2  59,4                                46,2  58,7  58,9  62,7   46,2    Mozart 16
Mozart 8   wav  35,3  21,1  23,3  20,5  21,2                                22,2  23,3  22    21,1   20,5    Mozart 8
Mozart S8  wav  68,6  36    49    41,1  30,9                                28,8  29,6  30,3  33,8   28,8    Mozart S8
NRecipes  (lzh) 26,3  19,9  18,6  19,9  19,2                                      22,6  20,5  21,7   18,6    NRecipes
Oldfield   mp3  96,8  96,9  96,6  95,6  96,4                                      96,9  96,1  98,4   95,6    Oldfield
Ouch       pgm  12,8  11    10,5  10,6  10,2  21,5  13,8   9,8 12,9  10,5         13,2  10,6  10,6    9,8    Ouch
Pagina     pbm  17,7  16,9  16,8  15,3  16,5  27,8  20,5  13,3 24,9  13,9         17,1  17,4  16,1   12,3    Pagina
Paper      ps   18,2  15,6  14,2  12    15,4                                      16,7  11,6  13,6   11,6    Paper
Snowolf    ppm  56,7  45    43,8  40,3  42,4  36,3  19,8             19,1         31,5  29    27,6   19,1    Snowolf
Spring     pbm  64,9  62,5  62,1  62,3  61,2 114,8 100,4  55,3 74,1  57,8         66    64,4  60     55,3    Spring
Tigre      ppm  15,9  13,1  12,1  14    12,3  20,2  12,4             11           15,5  12,3  11,9   11      Tigre
Volpe      bmp  55,8  52,8  43,1  49,2  41,9        52,2  46,3  62,3 38,9         57,1  42,6  41,2   38,9    Volpe
WinZip32   exe  42,3  35,6  36,8  33,6 38,3                                       39,1  40,5  35,5   33,6    WinZip32

% Media:        48,2  40,1  40,1  37,2  36,9                                      38,2  35,5  34,9   29,9    Media
In questa figura si può vedere l'efficienza relativa fra alcuni potenti compressori. 
Dato un file quale compressore usare? Cercherò di trarre le conclusioni. La scelta non è immadiata, e sono richieste alcuni tentativi. A parte questo bisogna per prima cosa chiedersi se conviene. Talvolta il file ha entropia molto alta, come una immagine Jpg, o un file audio Mp3, e una compressione può essere quasi una perdita di tempo. Un'altra cosa da chiedersi è a chi è rivolto il file: questi compressori non sono di uso elementare, e il destinatario può avere difficoltà nel decomprimere. Altri problemi possono essere dati dall'affidabvilità agli errori: un errore localizzato in un file zip può far perdere solo alcuni file su molti, ma lo stesso errore in un archivio solido può far perdee in media metà dei file. Per questo motivo WinRar possiede una opzione per aggiungere al file prodotto della ridondanza (Recovery Record) che permette di recuperare piccoli errori localizzati. Io consiglio di usare sempre tale opzione nel salvare file su floppy, perchè essi sono notoriamente inaffidabili, di circa il 95-98%. Ricordarsi, in tale caso, di lasciare almeno 1KB di spazio libero sul floppy, per permettere a Scandisk di correggre eventuali errori.
Un'altro parametro importante da tener di conto nello scegliere compressori è la disponibilità di decompressori nel destinatario. Ad esempio la maggio parte di questi compressori lavorano solo su Pc. Inoltre non sono massimamente affidabili, e non sono diffusi o supportati da molti. Fra molti anni sarà facile trovare un decompressore Zip su qualsiasi macchina, anche un Risc a 64 bit, ma si dovrebbe trovare il Rkive di una specifica versione e un simulatore di Pc per decomprimere file compressi oggi con Rkive...
Chi decomprime deve avere i programmi necessari pr farlo. Essi possono essergli dati Una Tantum, oppure allegati insieme al materiale compresso. Quindi vanno contate anche le loro dimensioni nel calcolo finale della quantità di materiale dato. (Però ad esempio se si deve distribuire il Calgary Corpus ad un possssore di Pc, conviene darlo compresso col Boa, insieme al Boa stesso zippato, piuttosto che fornire solo il Corpus zippato.)

Detto tutto ciò, ecco un insieme di regole euristiche, cioè di suggerimenti intuitivi, su quale compressore usare in ogni caso, in ordine di importanza delle prove da fare:

File testuali in lingue natuarli ==> Boa, Rkive
File testuali artificiali, script, log, Sorgenti di linguaggi ==> Acb, Boa, Rkive
File Postscript ==> Szip, Boa, Rkive, Acb
Eseguibili ==> 777 -m9, 777 -m2, Acb
Mp3, Jpeg, ecc ==> Nulla, 777 -m1, 777 -mg,
Midi ==> Rkive non solido, Rkive, Boa, Acb
Moduli, file multimediali misti ==> Uharc, 777 -mg
Wav generiche ==> Wa, 777 -m6, 777 -m3
Wav 8 bit mono (a basso volume) ==> 777 -m6, Wa
Immagini truecolor, o fotografiche, sfumate ==> Bmf e volendo Eri5
Immagini binarie o a pochissimi colori  ==> Minerva, Bmf
Immagini minuscole e bianrie ==> Minerva, GifBlaster, Bmf
File ad entropia molto alta, file già compressi ==> 777 -m1, 777 -mg
File generici ==> 777 -mg, Acb

[Queste regole potrebbero essere inserite in un piccolo programma che sceglie e usa automaticamente il compressore ideale per ciasun file. Sarebbe una specie di Macrocompressore Euristico. (complessivamente non occuperebbe più spazio di ZipMagic...).]
Da notare che questi suggerimenti partano dal presupposto che si posseggno molti o tutti i compressori e che si abbia tempo e Ram in quantità. Se il tempo è un fattore importante può convenire non usare 777 e Acb, ma ad esempio il WinRar. Se il tempo è minimo il WinZip o ZipMagic sono scelte obbilgate. (Szip è quasi altrettanto veloce, ma possiede una interfaccia a linea di comando, più lenta da usare).
Praticamente per immagini e audio digitale in formato Wav i migliori codificatori sono Bmf e Wa. Sono programmi piccoli, superefficienti e fatti da una sola persona, ciò dovrebbe far riflettere. Sfido il lettore a trovare compressori più efficienti di questi.
Se si vuol trovare il compressore migliore in media, pare che sia Uharc. Ma il risultato ha poco senso, perchè dipende dal tipo di file. Uharc risulta il vincitore singolo soprattutto a causa dei tanti file multimediali presenti. Un significato maggiore lo ha usare Wa, 777 e Bmf. Da soli questi tre sono in grado di comprimere tutti i tipi di file, producendo medie molto vicine al risultato minimo possibile.
Sarebbe carino fare un programma per relizzare una interfaccia Win per compressori lossless generici.

Esistono programmi, come XDelta, solitamente utilizzati per la distribuzione di Patch. Faccio un esempio. A scrive romanzi, e ne ha dato uno, Rom1, a B. Poi A apporta delle minime modifiche a Rom1 producendo Rom2. A usa XDelta per estrarre e comprimere in un file Diff solo le differenze fra Rom1 e Rom2. Così A può dare a B solo Diff, di pochi Kappa. B usa XDelta e Diff per ricostruire Rom2.
XDelta comprime le differenze, ma non è efficiente come i migliori quì mostrati. Come combinare le due cose? Basta ricordarsi che i compressori di solito lavorano incrementalmente. Ecco quello che deve fare A nella stessa situazione: comprimere con Boa (o Rkive) il vecchio romanzo. Comprimere con lo stesso compressore, il vecchio e nuovo romanzo, con l'opzione Storing. Calcolare la differenza con XDelta fra i due file compressi, e darla a B.
B deve fare operazioni quasi simmetriche: comprimere il vecchio romanzo  con lo stesso compressore,  applicare XDelta a questo file compresso e a quello fornito da A e ricostruire il file compresso con la coppia di file. Infine deve estrarre Rom2 da questo. Ho fatto delle prove e pare che convenga fare questa operazione, se le modifiche non sono troppo minime.