Come funziona la compressione dei file
Uno zip è più piccolo di quello che ci è entrato, e non è stato buttato via niente. Il trucco è che i dati normali sono molto più prevedibili del modo in cui li scriviamo di solito.
Perché codici corti per le lettere comuni vincono
Livello Base — linguaggio semplice, senza matematica
Normalmente ogni lettera che memorizzi occupa lo stesso spazio: otto bit ciascuna, che sia una e o una q. È comodo ed è anche uno spreco, perché quelle due lettere non sono ugualmente comuni. In italiano la e compare circa cento volte più spesso della q. Dare loro la stessa quantità di spazio è come usare la stessa scatola per spedire un divano e una cartolina.
Quindi fai la cosa ovvia: dai codici corti alle lettere comuni e codici lunghi a quelle rare. Dai tre bit alla e e lascia undici bit alla q. Ci perdi un pochino su ogni q e ci guadagni un pochino su ogni e, e siccome di e ce ne sono infinitamente di più, il totale viene più piccolo. Non è stato buttato via niente: ogni lettera è ancora lì, esattamente com'era.
C'è un problema da risolvere. Se i codici hanno lunghezze diverse, come fai a sapere dove finisce uno e comincia l'altro? La risposta è fare in modo che nessun codice sia l'inizio di un altro codice. Se 10 è una lettera intera, allora nessun altro codice può cominciare per 10. Un metodo chiamato codifica di Huffman costruisce esattamente questo, incollando ripetutamente insieme le due lettere più rare e risalendo, il che mette automaticamente le rare in fondo a un albero e le comuni vicino alla cima.
Gioca col cursore della ripetizione e guarda le barre. Più il tuo messaggio è prevedibile, più c'è da risparmiare. Una pagina della stessa lettera si comprime quasi a niente. Una pagina di pura casualità non si comprime per niente, e questo si rivela essere un fatto profondo più che una scocciatura.
Da sapere
- Nei testi in italiano le sei lettere più comuni - e a i o n r - fanno circa il 45% di tutto lo scritto. Quello squilibrio è l'intera fonte del risparmio.
- Il codice Morse è una versione artigianale della stessa idea: la E è un punto solo, la Q è linea-linea-punto-linea. Samuel Morse contò le lettere nella cassetta dei caratteri di un tipografo per capire quali dovessero essere corte.
- Un file di numeri davvero casuali non si può comprimere affatto. Se un programma sostiene di rimpicciolire qualsiasi file, si sbaglia: non ci sono abbastanza file corti per contenere tutti quelli lunghi.
Entropia, codici a prefisso e il confine fra con e senza perdita
Livello Studente — le equazioni principali
La quantità che viene sfruttata ha un nome e un numero. L'entropia di Shannon misura l'informazione media per simbolo: \(H = -\sum p_i \log_2 p_i\) bit. Per le lettere di un testo con le loro frequenze reali vale circa 4,1 bit per carattere invece degli 8 che spendi memorizzandole ingenuamente, e se tieni conto del fatto che dopo una q c'è quasi sempre una u, scende a circa 1,5 bit per carattere. L'entropia è il pavimento: nessun metodo senza perdita può usare in media meno bit per simbolo dell'entropia della sorgente, e la codifica di Huffman arriva a meno di un bit da lì.
L'algoritmo di Huffman è una costruzione avida dalle foglie. Prendi i due simboli meno frequenti, fondili in un nodo il cui peso è la loro somma, rimettilo nel mucchio, ripeti finché non resta un nodo solo. Leggendo l'albero dalla radice, un ramo a sinistra è uno 0 e uno a destra è un 1, e siccome ogni simbolo è una foglia, nessun codice è il prefisso di un altro: il decodificatore può scendere l'albero bit per bit e sa sempre quando è arrivato.
I formati veri sovrappongono altri trucchi. La codifica run-length sostituisce le ripetizioni con un conteggio. LZ77, il cuore di ZIP, PNG e gzip, sostituisce un pezzo ripetuto con un riferimento all'indietro - torna di 214 byte e copiane 9 - ed è per questo che testo e codice si comprimono così bene, e per cui un file compresso due volte non si restringe quasi più la seconda. DEFLATE è semplicemente LZ77 seguito da Huffman.
Tutto questo è senza perdita: l'originale torna bit per bit. Fotografie e musica usano invece metodi con perdita, che buttano via l'informazione che l'occhio o l'orecchio non notano: JPEG trasforma ogni blocco di 8×8 pixel in frequenze e rende grossolane quelle alte, MP3 scarta i suoni mascherati da vicini più forti. È per questo che un JPEG salvato ripetutamente degrada e uno ZIP mai.
Formule chiave
| Entropia | \(H = -\sum_i p_i \log_2 p_i\) | bit per simbolo, il pavimento duro |
|---|---|---|
| Lunghezza ideale | \(\ell_i = -\log_2 p_i\) | simbolo più raro, codice più lungo |
| Limite di Huffman | \(H \le \bar{\ell} < H + 1\) | |
| Rapporto di compressione | \(R = \dfrac{\text{bit originali}}{\text{bit codificati}}\) | |
Da sapere
- La codifica di Huffman è dimostrabilmente ottima fra i metodi che assegnano a ogni simbolo un numero intero di bit. La codifica aritmetica la batte proprio sfuggendo a quel vincolo e codificando l'intero messaggio come un singolo numero frazionario.
- Comprimere un file già compresso di solito lo fa diventare leggermente più grande, perché il contenitore aggiunge intestazioni a dati che non hanno più ridondanza da togliere.
- PNG è senza perdita e JPEG è con perdita, ed è per questo che gli screenshot vanno in PNG e le fotografie in JPEG. Salvare uno screenshot in JPEG produce aloni visibili attorno al testo per un risparmio che non vale nulla.
Complessità di Kolmogorov, l'argomento di conteggio e i compressori moderni
Livello Esperto — profondità matematica completa
01Perché nessun compressore può rimpicciolire tutto
La dimostrazione è un argomento di conteggio e sta in una riga. Ci sono \(2^n\) stringhe di lunghezza \(n\) ma solo \(2^n - 1\) stringhe più corte di \(n\). Qualsiasi compressore senza perdita è un'iniezione, quindi non può mandare ogni stringa di lunghezza \(n\) in una più corta: qualche ingresso deve crescere. La compressione non è dunque mai una proprietà del solo algoritmo; è una scommessa sulla distribuzione degli ingressi. Un buon compressore è quello il cui modello implicito coincide con i dati che gli vengono effettivamente dati.
02Comprimere è prevedere
I codificatori aritmetici e a intervalli recidono il legame fra simbolo e bit interi, codificando un messaggio come un singolo numero in \([0,1)\) il cui intervallo viene ristretto da ogni simbolo in proporzione alla sua probabilità. La conseguenza è che la modellazione e la codifica diventano problemi separati, e tutto il guadagno residuo sta nel modello. I compressori a mescolamento di contesti come PAQ fanno girare centinaia di modelli predittivi in parallelo e li fondono con una rete neurale; i migliori compressori di testo di oggi sono, funzionalmente, modelli linguistici. L'equivalenza vale nei due sensi: un modello che prevede bene il token successivo è un compressore, e il rapporto di compressione è una misura legittima di quanto un modello capisca i propri dati.
03La complessità di Kolmogorov
Il limite teorico per una particolare stringa è la lunghezza del programma più corto che la produce, \(K(x)\). Una stringa con struttura - un miliardo di cifre di π - ha complessità di Kolmogorov minuscola nonostante un'entropia enorme sotto qualsiasi modello di simboli, perché la genera un programma corto. Il guaio è che \(K\) non è calcolabile: nessun algoritmo può trovare in generale il programma più corto, risultato che discende dal problema della fermata. La compressione pratica è la ricerca di approssimazioni calcolabili a un ideale non calcolabile.
04Che cosa fanno davvero i formati moderni
Zstandard accoppia un ricercatore di corrispondenze in stile LZ77 con la finite state entropy, una implementazione dei sistemi numerici asimmetrici che raggiunge l'efficienza della codifica aritmetica alla velocità di una lettura da tabella - un progresso genuino, dato che per trent'anni la scelta è stata fra veloce e piccolo. Brotli porta con sé un dizionario da 120 kB di stringhe web comuni, così le risposte HTTP brevi si comprimono contro testo che non hanno mai contenuto. Per le immagini, la codifica intra-frame di AV1 sta sotto AVIF e batte JPEG di circa la metà a pari qualità percepita, usando predizione intra direzionale invece di affidarsi alla sola trasformata.
05La codifica con perdita come problema tasso-distorsione
Formalmente la compressione con perdita è il problema tasso-distorsione: minimizzare il bit rate sotto un vincolo di distorsione, dove la distorsione è definita da un modello percettivo invece che dall'errore quadratico. La matrice di quantizzazione del JPEG è un modello costruito a mano della sensibilità al contrasto - la risposta calante dell'occhio alle alte frequenze spaziali - e i successori moderni sostituiscono la messa a punto manuale con metriche percettive apprese. Il punto concettuale importante è che l'informazione scartata viene scelta da un modello dell'osservatore, ed è per questo che un codec messo a punto per l'occhio umano danneggia un'immagine medica in modi che un radiologo noterà.
Formule chiave
| Limite di conteggio | \(|\{x : |x| = n\}| = 2^n > 2^n - 1 = |\{y : |y| < n\}|\) | |
|---|---|---|
| Complessità di Kolmogorov | \(K(x) = \min\{|p| : U(p) = x\}\) | non calcolabile |
| Codifica aritmetica | \(\text{lunghezza} \approx \left\lceil -\log_2 \prod_i p(x_i) \right\rceil + 2\) | |
| Tasso-distorsione | \(R(D) = \min_{p(\hat{x}|x):\,\mathbb{E}[d] \le D} I(X;\hat{X})\) | |
Da sapere
- La complessità di Kolmogorov non è calcolabile, e la dimostrazione si riduce al problema della fermata. Il paradosso di Berry - "il più piccolo numero non descrivibile in meno di dodici parole" - è la stessa idea in italiano.
- Il premio Hutter paga per comprimere un estratto fisso da 1 GB di Wikipedia, sulla tesi esplicita che comprimere meglio un testo equivalga a capirlo meglio.
- I sistemi numerici asimmetrici, pubblicati nel 2009, hanno dato la compressione della codifica aritmetica a velocità simile a Huffman e oggi stanno dentro Zstandard, LZFSE e AV1. È una delle rare idee davvero nuove in un campo maturo.