La compressione dei dati spiegata

Ogni pagina web che carichi, ogni file ZIP e ogni immagine PNG è stato compresso: reso più piccolo senza perdere un solo bit, e decompresso di nuovo all'arrivo. I metodi che lo rendono possibile sono sorprendentemente semplici. Cercano ciò che si ripete e dicono “come prima” invece di ridirlo. Fin dove arriva questa idea, e dove si ferma, è una delle storie più eleganti dell'informatica.

Una riga di testo in cui i tratti ripetuti sono sostituiti da frecce che puntano alla loro prima comparsa, accanto a barre che mostrano la dimensione originale e quella compressa
Una riga di testo in cui i tratti ripetuti sono sostituiti da frecce che puntano alla loro prima comparsa, accanto a barre che mostrano la dimensione originale e quella compressa

Senza perdita e con perdita

La compressione è di due tipi. La compressione senza perdita restituisce esattamente l'originale, cosa essenziale per testi, programmi, fogli di calcolo e tutto ciò in cui anche un solo bit sbagliato conta. La compressione con perdita, usata per foto, musica e video, elimina dettagli che si percepiscono appena e raggiunge dimensioni molto più piccole, ma l'originale è perso per sempre. Questa pagina e il dimostratore riguardano la compressione senza perdita, che funziona trovando ed eliminando la ridondanza: le parti dei dati che si sarebbero potute prevedere.

La codifica run-length

Il metodo più semplice sostituisce una sequenza di simboli identici con un conteggio e il simbolo: dodici pixel bianchi diventano 12W (W sta per white, bianco). Lo usavano i fax, i primi formati bitmap e il formato d'immagine PCX, perché le pagine scansionate e i disegni semplici sono pieni di lunghe sequenze. Sul testo normale è inutile, anzi dannoso: le sequenze sono rare, e scrivere un conteggio per ogni singola lettera raddoppia la dimensione. La codifica run-length sopravvive comunque all'interno di altri metodi, per le sequenze di zeri lasciate da una prima trasformazione.

LZ77: rimandare indietro

Nel 1977 Abraham Lempel e Jacob Ziv, due ricercatori del Technion in Israele, pubblicarono un metodo che cambiò il settore. Il codificatore tiene una finestra del testo appena elaborato. Se i caratteri successivi sono già comparsi nella finestra, scrive una coppia: quanto indietro inizia la copia precedente e quanto è lunga. Altrimenti scrive il carattere stesso. Il decodificatore non ha bisogno di alcun dizionario, solo del testo che ha già ricostruito. Un riferimento può perfino sovrapporsi al testo che produce, così una sequenza di 100 lettere identiche diventa una lettera e un riferimento.

Abraham Lempel, che con Jacob Ziv al Technion nel 1977 pubblicò il metodo a finestra e riferimenti oggi noto come LZ77.
Abraham Lempel, che con Jacob Ziv al Technion nel 1977 pubblicò il metodo a finestra e riferimenti oggi noto come LZ77.

LZW: imparare un dizionario

Il secondo metodo di Lempel e Ziv, LZ78, costruisce un dizionario invece di guardare indietro in una finestra. Il perfezionamento di Terry Welch del 1984, LZW, parte da tutti i 256 valori di byte e, a ogni passo, invia il numero della stringa più lunga che conosce già e aggiunge come nuova voce quella stringa seguita dal carattere successivo. Il decodificatore ricostruisce lo stesso dizionario partendo solo dai numeri. LZW era veloce e semplice, e finì nel comando Unix compress, nel formato d'immagine GIF e nei file TIFF, finché i brevetti che lo coprivano non provocarono una lunga controversia negli anni '90.

Deflate, ZIP e oltre

Il metodo deflate di Phil Katz, introdotto con PKZIP 2 nel 1993, combina LZ77 con la codifica di Huffman: dopo aver trovato le ripetizioni, assegna i codici di bit più brevi ai letterali, alle lunghezze e alle distanze più comuni. Deflate è usato in ZIP, gzip, nelle immagini PNG e nella compressione delle pagine web, ed è il metodo che il dimostratore misura con il compressore integrato nel browser. Metodi più recenti come Zstandard, Brotli e xz usano finestre più grandi, una ricerca delle corrispondenze più intelligente e una codifica entropica più precisa, e riducono i file tipici di un ulteriore 10-30%.

Perché non tutto si può ridurre

Nessun metodo può rimpicciolire ogni file. Esistono 2ⁿ file di n bit ma solo 2ⁿ − 1 file più corti, quindi se un metodo li riducesse tutti, due finirebbero per coincidere e non potrebbero essere ripristinati entrambi: è il principio dei cassetti. Ogni compressore, quindi, ingrandisce alcuni input, di solito dati dall'aspetto casuale come file cifrati, file già compressi e rumore. È anche un test di casualità: i dati che nessun compressore riesce a ridurre sembrano casuali.

Il limite dell'entropia

Claude Shannon dimostrò nel 1948 che l'entropia di una sorgente è il minimo numero medio di bit per simbolo possibile per qualsiasi codice senza perdita. Contata lettera per lettera, l'entropia del testo inglese è di circa 4 bit per lettera, la metà degli 8 bit in cui è memorizzato. I metodi che usano il contesto, come LZ77, scendono sotto quel valore calcolato lettera per lettera su un testo ripetitivo, perché un riferimento sta per un intero tratto in una volta. I migliori compressori moderni, che prevedono ogni lettera da tutto ciò che la precede, portano l'inglese sotto i 2 bit per lettera.

Claude Shannon, che nel 1948, ai Bell Labs, precisò quanta informazione contiene un messaggio e la misurò in bit.
Claude Shannon, che nel 1948, ai Bell Labs, precisò quanta informazione contiene un messaggio e la misurò in bit.

Esploralo

Apri il dimostratore di compressione per applicare LZ77, LZW e la codifica run-length a un paragrafo, una canzone con ritornello, una riga di pixel, una tabella di dati, lettere casuali o DNA, oppure al tuo testo. Fai clic su un riferimento LZ77 per vedere che cosa copia, guarda crescere il dizionario di LZW e confronta tutti i metodi con ZIP e con il limite dell'entropia.

Domande frequenti

Che cosa significa un rapporto di compressione di 3 : 1?

Che l'originale è tre volte più grande della versione compressa, quindi il file compresso occupa un terzo dello spazio e ne fa risparmiare due terzi. Con ZIP il testo raggiunge di solito da 2 : 1 a 4 : 1; i dati molto ripetitivi, come i file di log, spesso molto di più.

Perché comprimere di nuovo un file ZIP non serve?

Il primo passaggio ha già eliminato le ripetizioni, e il suo risultato sembra quasi casuale. Un secondo passaggio non trova nulla a cui rimandare e aggiunge solo il proprio overhead, quindi il file resta della stessa dimensione o cresce leggermente.

Perché una finestra LZ77 più grande è migliore?

Una finestra più grande permette al codificatore di trovare ripetizioni che si trovano più indietro, come un ritornello che torna dopo diverse strofe. Il prezzo è che ogni distanza richiede più bit e che la ricerca richiede più tempo, ed è per questo che deflate si ferma a 32 KB mentre i metodi più recenti arrivano a diversi megabyte.

Compressione e crittografia sono la stessa cosa?

No. La compressione rende i dati più piccoli e chiunque può annullarla; la crittografia rende i dati illeggibili senza una chiave. Spesso vengono combinate, e in quel caso i dati vanno compressi prima: i dati cifrati sembrano casuali e non si possono più comprimere.

Pronto a provarlo?

Apri PictorX nel tuo browser: nessuna installazione, nessuna carta di credito richiesta per iniziare.

Apri il dimostratore di compressione