Comprimere file. Algoritmi e software a confronto.
Pagina 1 di 2
Tra le operazioni più comuni che possono risultare utili anche per utenti non specializzati individuiamo senz'altro la compressione. Tramite tale operazione infatti, un qualunque file presente sul nostro computer può essere ristrutturato, in modo da occupare una porzione di memoria inferiore su disco fisso. Osserviamo però che, attualmente, si hanno a disposizione hard disk molto capienti a prezzi piuttosto contenuti, dunque l'utilità dei programmi di compressione parrebbe ridursi. Si tratta però di una conclusione affrettata.
Infatti, ad esempio, può essere interessante comprimere uno o più file prima di inviarli via mail, per ridurre i tempi di ricezione e di invio. Interessante e pratica inoltre anche la possibilità di archiviare diversi documenti in un unico file compresso, più pratico da trasmettere e manipolare.
Ma quali sono le principali possibilità a disposizione degli utenti per comprimere uno o più file? E cosa distingue i vari software a disposizione? Esaminiamo innanzitutto il fondamento teorico dei software di compressione, illustrando dunque le principali caratteristiche degli algoritmi di compressione.
Algoritmi di compressione
Una prima distinzione tra gli algoritmi di compressione si individua tra algoritmi lossless, ovvero senza alcun tipo di perdita di qualità e algoritmi lossy, in cui la riduzione di spazio occupato su disco si accompagna a una perdita di qualità. Si tratta, spesso, di un peggioramento qualitativo difficilmente percepibile: ad esempio nel caso della codifica mp3 per i file audio.
Tra gli algoritmi più utilizzati individuiamo senz'altro l'algoritmo di Huffman, l'algoritmo di Shannon-Fano e l'algoritmo di Lempel, Ziv e Welch. Pur non dilungandoci in spiegazioni teoriche, esaminiamo le principali caratteristiche dell'algoritmo di Huffman, che ha segnato la storia delle tecniche di compressione.
Rimandiamo i lettori interessati a ulteriori approfondimenti sulle tecniche di Shannon-Fano e Lempel-Ziv-Welch a link più specifici su questo argomento:
- Algoritmo di Shannon-Fano: http://www.binaryessence.com/dct/en000041.htm
- Algoritmo di Lempel, Ziv e Welch: http://www.dsi.unifi.it/~resp/LZW.pdf
L'algoritmo di Huffman
L'algoritmo di Huffman appartiene alla categoria lossless, non introduce cioè nessuna perdita di qualità. Possiamo scomporne il funzionamento in cinque passi elementari:
- Viene analizzato e conteggiato il numero di ricorrenze degli elementi di base del file da comprimere: i singoli caratteri in un file di testo, i pixel in un file grafico.
- I due elementi meno frequenti sono accomunati in una categoria che li rappresenta entrambi. Così ad esempio se X ricorre 8 volte e Y 7 volte, viene creata la categoria XY, dotata di 15 ricorrenze. Intanto i componenti X e Y ricevono ciascuno un differente marcatore che li identifica come elementi entrati in un'associazione.
- Vengono identificati i due successivi elementi meno frequenti nel file e li si riunisce in una nuova categoria, usando lo stesso procedimento descritto al punto 2. Il gruppo XY può a sua volta entrare in nuove associazioni e costituire, ad esempio, la categoria XYZ. Quando ciò accade, la X e la Y ricevono un nuovo identificatore di associazione che finisce con l'allungare il codice che identificherà univocamente ciascuna delle due lettere nel file compresso che verrà generato.
- Viene creato quindi, per passaggi successivi, un albero costituito da una serie di ramificazioni binarie, all'interno del quale appaiono con maggiore frequenza e in combinazioni successive gli elementi più rari all'interno del file, mentre appaiono più raramente gli elementi più frequenti. In base al meccanismo descritto, ciò fa sì che gli elementi rari all'interno del file non compresso siano associati ad un codice identificativo lungo, che si accresce di un elemento ad ogni nuova associazione. Gli elementi invece che si ripetono più spesso nel file originale sono anche i meno presenti nell'albero delle associazioni, sicché il loro codice identificativo sarà il più breve possibile.
- Viene generato il file compresso, sostituendo a ciascun elemento del file originale il relativo codice prodotto al termine della catena di associazioni basata sulla frequenza di quell'elemento nel documento di partenza.
Dalla somma algebrica dello spazio guadagnato con la codifica breve degli elementi più frequenti e dello spazio perduto con la codifica lunga degli elementi più rari si ottiene il coefficiente di compressione prodotto dall'algoritmo di Huffman. Da quanto detto si deduce che questo tipo di compressione è tanto più efficace quanto più ampie sono le differenze di frequenza degli elementi che costituiscono il file originale, mentre scarsi sono i risultati che si ottengono quando la distribuzione degli elementi è uniforme.
