Compressione Dati
La compressione dati lossless (compressione dati senza perdita), è una classe di algoritmi di compressione dati che non porta alla perdita di alcuna parte dell'informazione originale durante la fase di compressione/decompressione dei dati stessi.
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 contengano ampie aree con colori puri spesso la compressione lossless non solo è applicabile, ma anche conveniente (GIF, PNG, MNG, TIFF con compressione LZW, ZIP o RLE).
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 file 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 + ... + 2N = 2N+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 + ... + 2N-1 = 2N-1 file che vi appartengono, sempre considerando anche il file di lunghezza zero.
* Tale numero di elementi è più piccolo di 2N+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 (2N) dell'insieme dei file 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 contengano ampie aree con colori puri spesso la compressione lossless non solo è applicabile, ma anche conveniente (GIF, PNG, MNG, TIFF con compressione LZW, ZIP o RLE).
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 file 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 + ... + 2N = 2N+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 + ... + 2N-1 = 2N-1 file che vi appartengono, sempre considerando anche il file di lunghezza zero.
* Tale numero di elementi è più piccolo di 2N+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 (2N) dell'insieme dei file compressi.
Una dimostrazione anche più semplice (ma equivalente) è come segue:
1. Si assuma che ogni file sia rappresentato da una stringa di bit di lunghezza arbitraria.
2. Si supponga (per assurdo), che esista un algoritmo di compressione C che trasformi ogni file di lunghezza maggiore di 1 in un file più corto distinto. (se i file risultanti non sono distinti, l'algoritmo non può essere reversibile senza perdita di dati.)
3. Dato un qualunque file F di lunghezza L(F)=N, si applichi C a questo file, ottenendo il file C(F)
4. Si ripeta il passo precedente applicando C a C(F) e si continui in questo modo: per l'ipotesi al punto (2), si ha:
L(F)=N>L(C(F)) > L(C2(F)) > ...
e quindi:
L(C(F))<= N-1
L(C2(F))<= N-2
L(Ck(F))<= N-k
Dopo al massimo N iterazioni, si deve avere L(CN-1(F))=1, perché ogni iterazione deve diminuire la lunghezza di almeno un bit: questo procedimento non dipende dal valore di N. Dalle nostre ipotesi consegue quindi che esisterebbero due soli file distinti (quello contente il bit 0 e quello contenente il bit 1). Questo è evidentemente falso, quindi l'ipotesi è falsa.
Quindi, ogni algoritmo di compressione che rende alcuni file più piccoli, deve necessariamente rendere altri file più grandi o lasciarli di lunghezza invariata.
Nell'uso pratico, si considerano buoni gli algoritmi di compressione che comprimono effettivamente la maggior parte dei formati più comuni: questo non corrisponde necessariamente ad una misura di bontá in senso teorico (che misura la distanza media, misurata su tutti i file possibili, tra la lunghezza ottenuta e il numero di bit di entropia contenuti nel file, che, per un teorema di Claude_Shannon, è il limite di comprimibilitá teorico). Inversamente, un algoritmo teoricamente buono potrebbe non avere applicabilitá pratica (ad esempio perché non riduce formati di uso comune).
In realtà, molti applicativi che utilizzano la compressione lossless prevedono di lasciare invariati gli insiemi di dati la cui dimensione sia aumentata dopo la compressione. 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.
Programmi generici per la compressione.
Tra i tanti programmi di compressione molti usano un algoritmo tra quelli elencati sopra, mentre alcuni ne hanno uno proprio:
* Arj - algoritmo proprio
* Gzip - usa DEFLATE
* PKZIP - usa DEFLATE
* WinZip - usa DEFLATE
* WinRar - algoritmo proprio
* Bzip2 - usa la trasformata di Burrows-Wheeler
* 7-Zip - usa LZMA
Formati ed algoritmi.
Audio.
* Apple Lossless - ALAC (Apple Lossless Audio Codec)
* Direct Stream Transfer - DST
* FLAC - Free Lossless Audio Codec
* LA - Lossless Audio (il miglior rapporto di compressione)
* Meridian Lossless Packing - MLP
* APE Monkey's Audio
* RealPlayer - RealAudio Lossless
* Shorten - SHN
* TTA - True Audio Lossless
* WavPack - WavPack lossless
* WMA - comprende anche una variante lossless
Immagini.
* ABO - Adaptive Binary Optimization
* GIF - Lempel-Ziv-Welch (LZW) per immagini da 2 a 256 colori
* Portable_Network_Graphics Portable Network Graphics - usa una variante di DEFLATE
* HD Photo - Contempla un metodo di compressione lossless
* OptiPNG - Metodo di compressione lossless in formato PNG
* JPEG - comprende una variante lossless JPEG-LS en:Lossless JPEG (poco utilizzata)
* JPEG 2000 - comprende un metodo di compressione lossless
* JBIG2 - comprende una compressione lossless di immagini in bianco e nero
* TIFF (Tagged Image File Format) - permette di scegliere tra diversi algoritmi sia lossless (tra cui LZW e RLE) o lossy (JPEG)
* WMPhoto - Contempla un meodo di compressione lossless
* Qbit Lossless Codec - Dedicato alla compressione intra-frame
* RLE Run-length encoding algoritmo usato nei formati TGA, BMP, TIFF
* FAX Gruppo 3 (1D) e Gruppo 4 (2D) - algoritmo per immagini bianco e nero usato dai FAX e dal formato TIFF
Video.
* Huffyuv
* CorePNG
* MSU Lossless Video Codec
* Sheervideo
* LCL
* Qbit Lossless Codec
* Animation codec en:Animation codec
* Lagarith
* H.264/MPEG-4 AVC
* Motion JPEG2000 comprende anche una variante lossless.
Tipi di compressione dati.
Le tecniche di compressione dati si dividono in due grandi categorie:
compressione dati con perdita: comprime i dati attraverso un processo con perdita d'informazione che sfrutta le ridondanze nell'utilizzo dei dati;
compressione dati senza perdita: comprime i dati attraverso un processo senza perdita d'informazione che sfrutta le ridondanze nella codifica del dato.
Tipicamente la scelta sul tipo di compressione da operare e le particolarità tecniche su cui esse si basano dipendono dalla particolare applicazione o destinazione d'uso dando vita alle seguenti forme di compressione:
la compressione audio;
la compressione video;
la compressione dell'immagine;
la compressione multimediale.
Di norma file e programmi non tollerano alcuna perdita di informazione, come invece possono le immagini relative a foto, il segnale video o il segnale audio.
Le tecniche senza perdita (lossless) consentono di preservare l'informazione originale in ogni sua parte. È l'unica via possibile quando si devono comprimere file di testo, programmi, documenti, database, schemi elettrici ecc.
Due esempi sono il formato ZIP o il formato 7z, i quali consentono di archiviare o trasmettere uno o più file risparmiando sulle risorse necessarie (spazio su disco o tempo di trasmissione). Al momento in cui vengono recuperati i file dallo ZIP o 7z (decompressione) questi risultano indistinguibili dagli originali.
Un altro esempio di caso in cui viene usata la compressione senza perdita è quello delle immagini non fotografiche, come gli schemi, i disegni o le icone. Per questo scopo esistono formati come il GIF o il più recente PNG.
L'immagine compressa con uno di questi formati mantiene esattamente l'aspetto originale fino al dettaglio più insignificante. Le prestazioni di questo tipo di compressione dati sono tipicamente più contenute e limitate.
D'altro canto, le tecniche con perdita di informazione (lossy) permettono anche delle compressioni molto spinte, quindi un grande risparmio di risorse, a discapito però della qualità dell'immagine o dell'audio che si è voluto comprimere.
Generalmente queste tecniche si usano per comprimere i file multimediali. Pur mantenendo minima la perdita di qualità, il risparmio rispetto ad una compressione lossless sulla stessa informazione è sempre decisamente apprezzabile.
Le informazioni multimediali come audio o video, in origine sono infatti troppo grandi per essere agevolmente trasmesse o memorizzate, quindi si preferisce avere una piccola riduzione della qualità (o distorsione del contenuto), ma nel contempo file molto più leggeri.
Alcuni esempi sono: la compressione di immagini in formato JPEG, largamente usata in fotografia digitale e sul Web, la compressione video in formato XviD oppure la compressione audio in formato MP3.
Infine, è importante puntualizzare che nel caso di compressione lossy di contenuti multimediali (es. MPEG), gli algoritmi di compressione di uso comune sono stati concepiti per minimizzare la distorsione percepita dall'utente in modo da rendere accettabile la degradazione del contenuto multimediale risultante.
1. Si assuma che ogni file sia rappresentato da una stringa di bit di lunghezza arbitraria.
2. Si supponga (per assurdo), che esista un algoritmo di compressione C che trasformi ogni file di lunghezza maggiore di 1 in un file più corto distinto. (se i file risultanti non sono distinti, l'algoritmo non può essere reversibile senza perdita di dati.)
3. Dato un qualunque file F di lunghezza L(F)=N, si applichi C a questo file, ottenendo il file C(F)
4. Si ripeta il passo precedente applicando C a C(F) e si continui in questo modo: per l'ipotesi al punto (2), si ha:
L(F)=N>L(C(F)) > L(C2(F)) > ...
e quindi:
L(C(F))<= N-1
L(C2(F))<= N-2
L(Ck(F))<= N-k
Dopo al massimo N iterazioni, si deve avere L(CN-1(F))=1, perché ogni iterazione deve diminuire la lunghezza di almeno un bit: questo procedimento non dipende dal valore di N. Dalle nostre ipotesi consegue quindi che esisterebbero due soli file distinti (quello contente il bit 0 e quello contenente il bit 1). Questo è evidentemente falso, quindi l'ipotesi è falsa.
Quindi, ogni algoritmo di compressione che rende alcuni file più piccoli, deve necessariamente rendere altri file più grandi o lasciarli di lunghezza invariata.
Nell'uso pratico, si considerano buoni gli algoritmi di compressione che comprimono effettivamente la maggior parte dei formati più comuni: questo non corrisponde necessariamente ad una misura di bontá in senso teorico (che misura la distanza media, misurata su tutti i file possibili, tra la lunghezza ottenuta e il numero di bit di entropia contenuti nel file, che, per un teorema di Claude_Shannon, è il limite di comprimibilitá teorico). Inversamente, un algoritmo teoricamente buono potrebbe non avere applicabilitá pratica (ad esempio perché non riduce formati di uso comune).
In realtà, molti applicativi che utilizzano la compressione lossless prevedono di lasciare invariati gli insiemi di dati la cui dimensione sia aumentata dopo la compressione. 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.
Programmi generici per la compressione.
Tra i tanti programmi di compressione molti usano un algoritmo tra quelli elencati sopra, mentre alcuni ne hanno uno proprio:
* Arj - algoritmo proprio
* Gzip - usa DEFLATE
* PKZIP - usa DEFLATE
* WinZip - usa DEFLATE
* WinRar - algoritmo proprio
* Bzip2 - usa la trasformata di Burrows-Wheeler
* 7-Zip - usa LZMA
Formati ed algoritmi.
Audio.
* Apple Lossless - ALAC (Apple Lossless Audio Codec)
* Direct Stream Transfer - DST
* FLAC - Free Lossless Audio Codec
* LA - Lossless Audio (il miglior rapporto di compressione)
* Meridian Lossless Packing - MLP
* APE Monkey's Audio
* RealPlayer - RealAudio Lossless
* Shorten - SHN
* TTA - True Audio Lossless
* WavPack - WavPack lossless
* WMA - comprende anche una variante lossless
Immagini.
* ABO - Adaptive Binary Optimization
* GIF - Lempel-Ziv-Welch (LZW) per immagini da 2 a 256 colori
* Portable_Network_Graphics Portable Network Graphics - usa una variante di DEFLATE
* HD Photo - Contempla un metodo di compressione lossless
* OptiPNG - Metodo di compressione lossless in formato PNG
* JPEG - comprende una variante lossless JPEG-LS en:Lossless JPEG (poco utilizzata)
* JPEG 2000 - comprende un metodo di compressione lossless
* JBIG2 - comprende una compressione lossless di immagini in bianco e nero
* TIFF (Tagged Image File Format) - permette di scegliere tra diversi algoritmi sia lossless (tra cui LZW e RLE) o lossy (JPEG)
* WMPhoto - Contempla un meodo di compressione lossless
* Qbit Lossless Codec - Dedicato alla compressione intra-frame
* RLE Run-length encoding algoritmo usato nei formati TGA, BMP, TIFF
* FAX Gruppo 3 (1D) e Gruppo 4 (2D) - algoritmo per immagini bianco e nero usato dai FAX e dal formato TIFF
Video.
* Huffyuv
* CorePNG
* MSU Lossless Video Codec
* Sheervideo
* LCL
* Qbit Lossless Codec
* Animation codec en:Animation codec
* Lagarith
* H.264/MPEG-4 AVC
* Motion JPEG2000 comprende anche una variante lossless.
Tipi di compressione dati.
Le tecniche di compressione dati si dividono in due grandi categorie:
compressione dati con perdita: comprime i dati attraverso un processo con perdita d'informazione che sfrutta le ridondanze nell'utilizzo dei dati;
compressione dati senza perdita: comprime i dati attraverso un processo senza perdita d'informazione che sfrutta le ridondanze nella codifica del dato.
Tipicamente la scelta sul tipo di compressione da operare e le particolarità tecniche su cui esse si basano dipendono dalla particolare applicazione o destinazione d'uso dando vita alle seguenti forme di compressione:
la compressione audio;
la compressione video;
la compressione dell'immagine;
la compressione multimediale.
Di norma file e programmi non tollerano alcuna perdita di informazione, come invece possono le immagini relative a foto, il segnale video o il segnale audio.
Le tecniche senza perdita (lossless) consentono di preservare l'informazione originale in ogni sua parte. È l'unica via possibile quando si devono comprimere file di testo, programmi, documenti, database, schemi elettrici ecc.
Due esempi sono il formato ZIP o il formato 7z, i quali consentono di archiviare o trasmettere uno o più file risparmiando sulle risorse necessarie (spazio su disco o tempo di trasmissione). Al momento in cui vengono recuperati i file dallo ZIP o 7z (decompressione) questi risultano indistinguibili dagli originali.
Un altro esempio di caso in cui viene usata la compressione senza perdita è quello delle immagini non fotografiche, come gli schemi, i disegni o le icone. Per questo scopo esistono formati come il GIF o il più recente PNG.
L'immagine compressa con uno di questi formati mantiene esattamente l'aspetto originale fino al dettaglio più insignificante. Le prestazioni di questo tipo di compressione dati sono tipicamente più contenute e limitate.
D'altro canto, le tecniche con perdita di informazione (lossy) permettono anche delle compressioni molto spinte, quindi un grande risparmio di risorse, a discapito però della qualità dell'immagine o dell'audio che si è voluto comprimere.
Generalmente queste tecniche si usano per comprimere i file multimediali. Pur mantenendo minima la perdita di qualità, il risparmio rispetto ad una compressione lossless sulla stessa informazione è sempre decisamente apprezzabile.
Le informazioni multimediali come audio o video, in origine sono infatti troppo grandi per essere agevolmente trasmesse o memorizzate, quindi si preferisce avere una piccola riduzione della qualità (o distorsione del contenuto), ma nel contempo file molto più leggeri.
Alcuni esempi sono: la compressione di immagini in formato JPEG, largamente usata in fotografia digitale e sul Web, la compressione video in formato XviD oppure la compressione audio in formato MP3.
Infine, è importante puntualizzare che nel caso di compressione lossy di contenuti multimediali (es. MPEG), gli algoritmi di compressione di uso comune sono stati concepiti per minimizzare la distorsione percepita dall'utente in modo da rendere accettabile la degradazione del contenuto multimediale risultante.
