Loading AI tools
classe di algoritmi di compressione dati Da Wikipedia, l'enciclopedia libera
La compressione dati senza perdita (o compressione dati lossless), in informatica e telecomunicazioni, è 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 "senza perdita" non solo è applicabile, ma anche conveniente (GIF, PNG, MNG, TIFF con compressione LZW, ZIP o RLE).
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 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) è la seguente:
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 contenente 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.
In generale, non vi è un rapporto di proporzionalità indiretta tra qualità della compressione ottenibile da un 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 i dati non sono più direttamente disponibili ma occorre svolgere un passaggio intermedio (decompressione).
Poiché, dato uno stesso archivio dati, la decompressione è solitamente molto più frequente della compressione molti algoritmi sono fortemente asimmetrici: il tempo richiesto per la compressione è sostanzialmente superiore a quello richiesto per la decompressione. Questo accade anche nei riguardi delle richieste di memoria e di capacità di calcolo.
Esistono diversi algoritmi di compressione. Tra i più noti:
Tra i tanti programmi di compressione molti usano un algoritmo tra quelli elencati sopra, mentre alcuni ne hanno uno proprio:
Supportano tutti la cifratura con algoritmo AES-128 o AES-256.
In ogni caso è possibile cifrare e comprimere il file con due programmi diversi, ma ciò rallenta l'apertura e chiusura, rispetto ad un unico programma che faccia entrambe le cose.