Compressione senza perdite

Gli algoritmi di compressione dati senza perdite non possono garantire la compressione per tutti i set di dati in ingresso. In altre parole, per qualsiasi algoritmo di compressione dati senza perdita, ci sarà un insieme di dati in ingresso che non diventa più piccolo quando viene processato dall’algoritmo, e per qualsiasi algoritmo di compressione dati senza perdita che rende almeno un file più piccolo, ci sarà almeno un file che rende più grande. Questo è facilmente dimostrabile con la matematica elementare usando un argomento di conteggio, come segue:

• assumiamo che ogni file sia rappresentato come una stringa di bit di qualche lunghezza arbitraria.
• Supponiamo che esista un algoritmo di compressione che trasformi ogni file in un file di output che non sia più lungo del file originale, e che almeno un file venga compresso in un file di output più corto del file originale.
• Lasciamo che M sia il numero minimo tale che esista un file F di lunghezza M bit che si comprima in qualcosa di più corto. Sia N la lunghezza (in bit) della versione compressa di F.
• Perché N<M, ogni file di lunghezza N mantiene la sua dimensione durante la compressione. Ci sono 2N file di questo tipo possibili. Insieme a F, questo rende 2N+1 file che si comprimono tutti in uno dei 2N file di lunghezza N.
• Ma 2N è più piccolo di 2N+1, quindi per il principio del pigeonhole ci deve essere qualche file di lunghezza N che è contemporaneamente l’output della funzione di compressione su due input diversi. Quel file non può essere decompresso in modo affidabile (quale dei due originali dovrebbe produrre?), il che contraddice l’assunzione che l’algoritmo fosse senza perdite.
• Dobbiamo quindi concludere che la nostra ipotesi originale (che la funzione di compressione non allunga nessun file) è necessariamente falsa.

Qualunque algoritmo di compressione senza perdite che accorcia alcuni file deve necessariamente allungarne alcuni, ma non è necessario che questi file diventino molto più lunghi. La maggior parte degli algoritmi di compressione pratici forniscono una funzione di “escape” che può spegnere la normale codifica per i file che diventerebbero più lunghi essendo codificati. In teoria, solo un singolo bit aggiuntivo è richiesto per dire al decoder che la codifica normale è stata disattivata per l’intero input; tuttavia, la maggior parte degli algoritmi di codifica usa almeno un intero byte (e tipicamente più di uno) per questo scopo. Per esempio, i file compressi in deflate non hanno mai bisogno di crescere di più di 5 byte per 65.535 byte di input.

In effetti, se consideriamo file di lunghezza N, se tutti i file fossero ugualmente probabili, allora per qualsiasi compressione senza perdita che riduce la dimensione di qualche file, la lunghezza attesa di un file compresso (media su tutti i possibili file di lunghezza N) deve necessariamente essere maggiore di N. Quindi se non sappiamo nulla delle proprietà dei dati che stiamo comprimendo, tanto vale non comprimerli affatto. Un algoritmo di compressione senza perdita è utile solo quando abbiamo più probabilità di comprimere certi tipi di file piuttosto che altri; allora l’algoritmo potrebbe essere progettato per comprimere meglio quei tipi di dati.

Quindi, la lezione principale dell’argomento non è che si rischiano grandi perdite, ma semplicemente che non si può sempre vincere. Scegliere un algoritmo significa sempre implicitamente selezionare un sottoinsieme di tutti i file che diventeranno utilmente più corti. Questa è la ragione teorica per cui abbiamo bisogno di avere diversi algoritmi di compressione per diversi tipi di file: non può esistere un algoritmo che sia buono per tutti i tipi di dati.

Il “trucco” che permette agli algoritmi di compressione senza perdita di dati, usati sul tipo di dati per cui sono stati progettati, di comprimere costantemente tali file in una forma più corta è che i file su cui gli algoritmi sono progettati per agire hanno tutti una qualche forma di ridondanza facilmente modellabile che l’algoritmo è progettato per rimuovere, e quindi appartengono al sottoinsieme di file che l’algoritmo può rendere più corti, mentre altri file non verrebbero compressi o addirittura diventerebbero più grandi. Gli algoritmi sono generalmente abbastanza specificamente sintonizzati su un particolare tipo di file: per esempio, i programmi di compressione audio senza perdita non funzionano bene sui file di testo, e viceversa.

In particolare, i file di dati casuali non possono essere coerentemente compressi da nessun concepibile algoritmo di compressione dati senza perdita: infatti, questo risultato è usato per definire il concetto di casualità nella teoria della complessità algoritmica.

È provatamente impossibile creare un algoritmo che possa comprimere senza perdita qualsiasi dato. Mentre ci sono state molte affermazioni nel corso degli anni di aziende che hanno raggiunto una “compressione perfetta” dove un numero arbitrario N di bit casuali può sempre essere compresso in N – 1 bit, questo tipo di affermazioni può essere tranquillamente scartato senza nemmeno guardare ulteriori dettagli riguardanti il presunto schema di compressione. Un tale algoritmo contraddice le leggi fondamentali della matematica perché, se esistesse, potrebbe essere applicato ripetutamente per ridurre senza perdite qualsiasi file alla lunghezza 0. I presunti algoritmi di compressione “perfetti” sono spesso derisivamente chiamati algoritmi di compressione “magici” per questa ragione.

D’altra parte, è stato anche dimostrato che non esiste un algoritmo per determinare se un file è incomprimibile nel senso della complessità di Kolmogorov. Quindi è possibile che qualsiasi file particolare, anche se sembra casuale, possa essere significativamente compresso, includendo anche la dimensione del decompressore. Un esempio sono le cifre della costante matematica pi greco, che sembrano casuali ma possono essere generate da un programma molto piccolo. Tuttavia, anche se non è possibile determinare se un particolare file è incomprimibile, un semplice teorema sulle stringhe incomprimibili mostra che oltre il 99% dei file di qualsiasi lunghezza data non può essere compresso da più di un byte (inclusa la dimensione del decompressore).

Sfondo matematicoModifica

Astrattamente, un algoritmo di compressione può essere visto come una funzione su sequenze (normalmente di ottetti). La compressione ha successo se la sequenza risultante è più corta della sequenza originale (e delle istruzioni per la mappa di decompressione). Affinché un algoritmo di compressione sia senza perdite, la mappa di compressione deve formare un’iniezione da sequenze di bit “semplici” a sequenze di bit “compresse”.

Il principio del pigeonhole vieta una biiezione tra la collezione di sequenze di lunghezza N e qualsiasi sottoinsieme della collezione di sequenze di lunghezza N-1. Pertanto, non è possibile produrre un algoritmo senza perdite che riduca la dimensione di ogni possibile sequenza in ingresso.

Punti di applicazione nella teoria della compressione realeModifica

I progettisti di algoritmi di compressione reale accettano che i flussi di alta entropia informativa non possono essere compressi, e di conseguenza, includono strutture per rilevare e gestire questa condizione. Un modo ovvio di rilevazione è applicare un algoritmo di compressione grezzo e verificare se il suo output è più piccolo del suo input. A volte, il rilevamento è fatto da euristiche; per esempio, un’applicazione di compressione può considerare i file i cui nomi finiscono in “.zip”, “.arj” o “.lha” non comprimibili senza alcun rilevamento più sofisticato. Un modo comune di gestire questa situazione è citare l’input, o parti non comprimibili dell’input nell’output, minimizzando il sovraccarico di compressione. Per esempio, il formato dati zip specifica il ‘metodo di compressione’ di ‘Stored’ per i file di input che sono stati copiati nell’archivio verbatim.

The Million Random Digit ChallengeEdit

Mark Nelson, in risposta alle dichiarazioni di algoritmi di compressione magici che appaiono in comp.compression, ha costruito un file binario di 415.241 byte dal contenuto altamente entropico, e ha lanciato una sfida pubblica di 100 dollari a chiunque scriva un programma che, insieme al suo input, sia più piccolo dei dati binari da lui forniti e sia in grado di ricostituirli senza errori.

Le FAQ del newsgroup comp.compression contengono una sfida di Mike Goldman che offre 5.000 dollari per un programma che possa comprimere dati casuali. Patrick Craig raccolse la sfida, ma invece di comprimere i dati, li divise in file separati che finivano tutti con il numero 5, che non era memorizzato come parte del file. Omettendo questo carattere, i file risultanti (più, secondo le regole, la dimensione del programma che li ha riassemblati) erano più piccoli del file originale. Tuttavia, nessuna compressione effettiva ha avuto luogo, e le informazioni memorizzate nei nomi dei file erano necessarie per riassemblarli nell’ordine corretto nel file originale, e queste informazioni non sono state prese in considerazione nel confronto delle dimensioni dei file. I file stessi non sono quindi sufficienti a ricostituire il file originale; anche i nomi dei file sono necessari. Patrick Craig è d’accordo sul fatto che non c’è stata alcuna compressione significativa, ma ha sostenuto che la formulazione della sfida in realtà non lo richiede. Una storia completa dell’evento, compresa la discussione sul fatto che la sfida sia stata tecnicamente soddisfatta o meno, è sul sito web di Patrick Craig.