Come funziona la compressione dei file

Si parla parecchio, ormai, di compressione dei dati. La troviamo nei formati rivoluzionari come MP3, è presente nel MiniDisc della Sony; è ormai un concetto comune per chi usa utility come WinZip ed emerge continuamente ogni volta che si parla di trasmissione dei dati. Ci hanno detto un sacco di volte che la compressione di un file porta a ridurne la dimensione ma, alla fine, i byte mancanti dove vanno a finire? Siamo sicuri di non aver perso nulla?
Niente paura, la compressione non ha nulla di magico: si tratta di algoritmi abbastanza semplici e consolidati che fanno parte del bagaglio culturale dei programmatori ormai da parecchi anni.

Il primo che iniziò a parlare di compressione dei dati fu Claude Shannon dei Bell Laboratories negli anni Quaranta. Compressione dei dati vuol dire ridurre lo spazio che le informazioni occupano, senza per questo rinunciare al contenuto che trasmettono. La possibilità di comprimere le informazioni si basa essenzialmente sul fatto che spesso queste sono ridondanti, contengono informazioni ripetute, spazi inutilizzati oppure elementi non significativi. Qualcosa di analogo ai prodotti sottovuoto, dove viene eliminato lo spazio occupato dall’aria, senza per questo alterare in alcun modo il contenuto. Possiamo, inizialmente, distinguere tra due tipi di compressione: senza perdita di dati e con perdita di dati.

Compressione senza perdita di dati

Quando trasferiamo attraverso Internet documenti, programmi, dati di una certa importanza, e utilizziamo una compressione per ridurre i tempi di connessione, desideriamo sempre trasmettere tutte le informazioni senza perderne neanche un pezzetto, in modo che, mediante una opportuna decompressione, si possa ottenere esattamente il contenuto originario (sia esso un file, una immagine, un suono ecc.). È la compressione che tutti conosciamo attraverso i famosi formati ZIP, ARJ e così via. È di estremo interesse in quanto non intacca il contenuto, quindi può diventare totalmente trasparente per l’utente. L’idea che sia possibile comprimere i dati si basa sulla nozione di entropia, mutuata dalla termodinamica e applicata all’informatica. Diciamo che un insieme di dati (cioè, ai fini pratici, un file) possiede una maggiore o minore entropia a seconda della quantità di informazioni che contiene. Certo, detto così non è di grande aiuto. È più facile comprendere con un esempio. Date le due sequenze di caratteri

AAAAAAAAAAABBBBBBBBBBBBBBB
ABCDEFGHIJKLMNOPQRSTUVWXYZ

è abbastanza intuitivo vedere che la seconda sequenza contiene maggiore Informazionerispetto alla prima (e quindi, secondo il discorso precedente, possiede una entropia maggiore). Nello stesso spazio, infatti, sono contenuti molti più simboli, con una variabilità maggiore. Mentre la prima sequenza è estremamente ridondante (solo due simboli ripetuti molte volte) è difficile trovare un modo per “riassumere”la seconda sequenza. L’idea alla base della compressione senza perdita di dati è che, minore è l’entropia e minore può risultare lo spazio occupato (ottenendo, quindi, una maggiore compressione). La prima sequenza di caratteri potrebbe, infatti, essere scritta anche come

11A+15B

occupando uno spazio più ridotto, ma senza per questo perdere informazione. La compressione che sfrutta questa tecnica prende il nome di Run-Length Encoding.
Analogamente alla precedente, potremmo compiere un’analisi più approfondita sulla sequenza di caratteri per trovare dei “pattern”o delle forme comuni che si ripetono. Se, per esempio, abbiamo la sequenza ABBABBABBABB è facile vedere che potrebbe essere riscritta come 4ABB. Questo tipo di compressione si chiama LZW, dalle iniziali dei ricercatori che hanno avuto l’idea. Brevettato nel 1985 dalla Sperry Corp., (diventata in seguito Unisys Corp.) il metodo LZW viene utilizzato dal formato di immagine GIF e dallo standard V.42bis per i modem.

Compressione con perdita di dati

In molti casi, specialmente quando si ha a che fare con informazioni digitalizzate (per esempio fotografie o file audio) potrebbe essere conveniente rinunciare a qualche piccolo dettaglio insignificante per guadagnare in comprimibilità. Se, infatti, in una fotografia possiamo eliminare piccole sfumature (che comunque rappresentano informazione) riusciamo in questo modo a ridurre l’entropia dell’immagine. A questo punto i metodi di compressione senza perdita di dati visti in precedenza possono essere applicati con maggiore efficacia.

Quindi in realtà la compressione con perdita di dati usa gli stessi algoritmi di quella senza perdita di dati; la differenza sta nel fatto che li fa precedere da un procedimento di “semplificazione”dell’informazione. Ritroviamo questo tipo di compressione nel formato di immagine JPEG che, come è noto, viene consigliato soprattutto per immagini fotografiche.

Tutti i formati MPEG funzionano secondo questo procedimento. Consentono di ridurre l’entropia eliminando informazioni non importanti. Facciamo un esempio. Quando ascoltiamo un brano audio, il nostro cervello opera da filtro su alcune informazioni che non ritiene rilevanti. In presenza di un segnale forte, per esempio, i segnali molto più deboli tendono a non essere percepiti. L’idea è allora di eliminare all’origine questi segnali, riducendo in tal modo le informazioni contenute nel file. Possono essere filtrate analogamente le frequenze non udibili o comunque poco significative.
Elemento importante in questo caso è che si può accedere a livelli diversi di compressione. Se si accetta di rinunciare alla qualità, si può guadagnare sulla dimensione. Più sono i dettagli sacrificati, minore sarà la qualità dell’Informazionefinale e più piccolo sarà il file corrispondente.

Compressione frattale

Uno dei campi più promettenti per la ricerca di nuovi standard di compressione è dato dagli algoritmi frattali. Senza entrare nei dettagli tecnici, si tratta di procedure che ricercano all’interno del file (per esempio una immagine) delle ricorrenze in modo analogo al metodo LZW. Solo che in questo caso gli elementi ripetuti non devono essere necessariamente identici, ma è sufficiente che siano “affini”. Siano cioè ottenibili attraverso trasformazioni elementari della forma originaria come, per esempio, la rotazione. In modo analogo a quello che avviene nelle immagini frattali – in cui si nota una “somiglianza”delle varie parti – questo metodo di compressione cerca di ricondurre l’Informazionea pochi “mattoni”di base e alla combinazione delle loro trasformazioni.

Pro e contro

Ma se la compressione è così efficace, perché non usarla dappertutto? Perché non avere come standard una base compressa, come si usava sugli hard disk di qualche anno fa per aumentarne la capacità? La verità è che bisogna evitare di abusarne, perché genera assuefazione. Il fatto è che una Informazionepuò essere compressa senza perdita di dati solamente quando contiene ridondanze eliminabili. Una volta eliminate, non si può eliminarle una seconda volta. Il che vuol dire che un file compresso non può essere compresso di nuovo, o almeno non si avrà un grande beneficio in termini di dimensione. È un problema analogo alle offerte speciali sugli acquisti: non sono mai cumulabili!
Se si fa largo uso di compressione, in modo trasparente, si tende a dimenticarsene incappando a spiacevoli sorprese. Chi infatti usa dischi compressi o, come a volte si diceva, “stackerizzati”, e vuole salvare sul proprio disco file di WinZip, faccia bene attenzione alle dimensioni perché i file “zippati”non verranno ridotti granché. Quindi i valori medi dichiarati di guadagno di spazio su disco non verranno rispettati. Per fare un esempio, un disco da 100 MByte che, stackerizzato, viene dichiarato da 200 MByte, in realtà non guadagnerà molto rispetto alla capacità originaria se viene riempito di file ZIP.

Inoltre la ridondanza delle informazioni non sempre è un nemico da combattere. Nelle trasmissioni di dati è un valido aiuto contro i disturbi: per sapere se sono avvenuti errori di trasmissione occorre inserire informazioni supplementari di controllo (che non aggiungono contenuto e quindi riducono l’entropia). È più facile che si rovini un file ZIP piuttosto che uno non compresso.