Compressione dati lossless

La compressione dati lossless è quella classe di algoritmi di compressione che non comportano perdite di dati, che consentano quindi di recuperare tutta l'informazione e ricostruire esattamente i dati originali partendo dai dati compressi.

Un esempio di questo tipo di compressione è dato dai formati zip, gzip, bzip2, rar, 7z. I file per cui non è accettabile una perdita di informazione, come i testi o i programmi, utilizzano questo metodo. Per le immagini fotografiche generalmente non si usano algoritmi lossless in quanto sarebbero veramente poco efficienti, ma per le immagini che contengono schemi o disegni realizzati al PC spesso la compressione lossless non solo è applicabile, ma anche conveniente (GIF, PNG, MNG, TIFF).

Problemi della compressione lossless

Gli algoritmi di compressione lossless non possono sempre garantire che ogni insieme di dati in input diminuisca di dimensione. In altre parole per ogni algoritmo lossless ci saranno particolari dati in input che non diminuiranno di dimensione quando elaborati dall'algoritmo. Questo è facilmente verificabile con della matematica elementare:

Si assuma che ogni file sia rappresentato da una stringa di bit di lunghezza arbitraria.
Si supponga (per assurdo), che esista un algoritmo di compressione che trasformi ogni file in un file più corto distinto. (se i files risultanti non sono distinti, l'algoritmo non può essere reversibile senza perdita di dati.)
Si considerino l'insieme dei file con lunghezza massima di N bit. Questo set ha 1 + 2 + 4 + ... + 2^N = 2^N+1-1 elementi, se si include il file di lunghezza zero.
Ora considerando l'insieme dei file con N-1 bit, vi sono 1 + 2 + 4 + ... + 2^N-1 = 2^N-1 file che vi appartengono, sempre considerando anche il file di di lunghezza zero.
Tale numero di elementi è più piccolo di 2^N+1-1. Non è possibile collegare in modo univoco gli elementi di un insieme più grande (i file da comprimere) con gli elementi di un insieme più piccolo (i file dopo la compressione).
Questa contraddizione implica che l'ipotesi originale (che un algoritmo di compressione renda tutti i file più piccoli) sia errata.

Si può notare che la differenza di dimensione è così elevata che non fa alcuna differenza se si considerano file di dimensione esattamente N come insieme dei file da comprimere: tale insieme è comunque di dimensioni maggiori (2^N) dell'insieme dei file compressi.

Quindi, ogni algoritmo di compressioni dati che rende alcuni file più piccoli, deve necessariamente rendere altri file più grandi. I buoni algoritmi di compressione rendono la maggiorparte dei file usati comunemente più piccoli, anche quando teoricamente esistono molti più file che aumenterebbero di dimensione. In realtà, in molti formati lossless, è previsto che quando un insieme di dati aumenti di dimensione dopo la compressione esso viene memorizzato non compresso. Ovviamente, il flag che indica che questo gruppo di dati non va processato dall'algoritmo aumenta la dimensione effettiva necessaria a memorizzare il gruppo di dati, ma permette di evitare un ulteriore spreco di spazio e di tempo necessario alla compressione/decompressione.

Qualità della compressione e velocità

In generale, vi è un rapporto di proporzionalità indiretta tra qualità della compressione ottenibile da una algoritmo e la sua velocità di esecuzione.

Prendiamo ad esempio la seguente stringa di dati: 005555550055555500555555005555550055555500555555 La stringa richiede 48 caratteri, ma è immediatamente disponibile all'utilizzo. Un algoritmo di compressione lossless potrebbe essere "cifra-numero di ripetizioni". La stringa, utilizzando questo algoritmo, diviene quindi: 025602560256025602560256 È chiaro che per rendere disponibili i dati occorre svolgere un passaggio intermedio. È possibile migliorare l'algoritmo per ottenere una compressione più spinta. L'algoritmo "cifra-numero di ripetizioni-numero di ripetizioni" permette di ottenere una stringa equivalente di soli 5 caratteri, ma al "prezzo" di un ulteriore passaggio: 02566

Normalmente gli algoritmi di compressione vengono progettati per essere più veloci nella decodifica dell'informazione rispetto alla fase di codifica, in quanto quest'ultima è un'operazione effettuata di gran lunga più frequentemente.

Tecniche di compressione

Esistono diversi algoritmi di compressione. Tra i più famosi:

Huffman
GZip
LZMA
LZ77
LZ78
LZW
Bzip2
PPM
DEFLATE (Usato anche da WinZip e WinRar)