Come funziona la compressione dei dati senza perdita | Rivista Quanta

Con oltre 9 miliardi di gigabyte di informazioni che viaggiano su Internet ogni giorno, i ricercatori sono costantemente alla ricerca di nuovi modi per comprimere i dati in pacchetti più piccoli. Le tecniche all'avanguardia si concentrano su approcci con perdita, che ottengono la compressione "perdendo" intenzionalmente informazioni da una trasmissione. Google, ad esempio, ha recentemente svelato una strategia con perdite in cui il computer mittente elimina i dettagli da un'immagine e il computer ricevente utilizza l'intelligenza artificiale per indovinare le parti mancanti. Anche Netflix utilizza un approccio con perdita, declassando la qualità del video ogni volta che l'azienda rileva che un utente sta guardando su un dispositivo a bassa risoluzione.

Al contrario, sono attualmente in corso pochissime ricerche sulle strategie senza perdite, in cui le trasmissioni vengono ridotte, ma nessuna sostanza viene sacrificata. La ragione? Gli approcci senza perdita sono già notevolmente efficienti. Alimentano tutto, dallo standard di immagine JPEG all'onnipresente utility software PKZip. Ed è tutto a causa di uno studente laureato che stava semplicemente cercando una via d'uscita da un duro esame finale.

Settant'anni fa, un professore del Massachusetts Institute of Technology di nome Robert Fano ha offerto agli studenti della sua classe di teoria dell'informazione una scelta: sostenere un esame finale tradizionale o migliorare un algoritmo leader per la compressione dei dati. Fano può o non può aver informato i suoi studenti che era un autore di quell'algoritmo esistente, o che era alla ricerca di un miglioramento da anni. Quello che sappiamo è che Fano ha proposto ai suoi studenti la seguente sfida.

Considera un messaggio composto da lettere, numeri e punteggiatura. Un modo semplice per codificare un messaggio di questo tipo sarebbe assegnare a ciascun carattere un numero binario univoco. Ad esempio, un computer potrebbe rappresentare la lettera A come 01000001 e un punto esclamativo come 00100001. Ciò si traduce in codici facili da analizzare — ogni otto cifre, o bit, corrispondono a un unico carattere — ma terribilmente inefficienti, perché lo stesso numero di cifre binarie viene utilizzato sia per le voci comuni che per quelle non comuni. Un approccio migliore sarebbe qualcosa di simile al codice Morse, dove la frequente lettera E è rappresentata da un solo punto, mentre la meno comune Q richiede il più lungo e laborioso trattino-trattino-punto-trattino.

Eppure anche il codice Morse è inefficiente. Certo, alcuni codici sono brevi e altri sono lunghi. Ma poiché la lunghezza del codice varia, i messaggi in codice Morse non possono essere compresi a meno che non includano brevi periodi di silenzio tra la trasmissione di ogni carattere. In effetti, senza quelle pause costose, i destinatari non avrebbero modo di distinguere il messaggio Morse trattino punto-trattino-punto punto-punto trattino punto ("banale") da trattino punto-trattino-punto punto-punto-trattino punto ("vero" ).

Fano aveva risolto questa parte del problema. Si rese conto che poteva usare codici di lunghezza variabile senza bisogno di spazi costosi, purché non usasse mai lo stesso modello di cifre sia come codice completo che come inizio di un altro codice. Ad esempio, se la lettera S fosse così comune in un particolare messaggio che Fano le avesse assegnato il codice estremamente breve 01, allora nessun'altra lettera in quel messaggio sarebbe stata codificata con qualcosa che iniziasse con 01; codici come 010, 011 o 0101 sarebbero tutti vietati. Di conseguenza, il messaggio in codice poteva essere letto da sinistra a destra, senza alcuna ambiguità. Ad esempio, con la lettera S assegnata 01, la lettera A assegnata 000, la lettera M assegnata 001 e la lettera L assegnata 1, improvvisamente il messaggio 0100100011 può essere immediatamente tradotto nella parola "piccolo" anche se L è rappresentato da uno cifra, S di due cifre e le altre lettere di tre ciascuna.

Per determinare effettivamente i codici, Fano ha costruito alberi binari, posizionando ogni lettera necessaria alla fine di un ramo visivo. Il codice di ciascuna lettera è stato quindi definito dal percorso dall'alto verso il basso. Se il sentiero si diramava a sinistra, Fano aggiungeva uno 0; i rami giusti hanno ottenuto un 1. La struttura ad albero ha reso facile per Fano evitare quelle sovrapposizioni indesiderate: una volta che Fano ha inserito una lettera nell'albero, quel ramo sarebbe terminato, il che significa che nessun codice futuro avrebbe potuto iniziare allo stesso modo.

Per decidere quali lettere sarebbero andate dove, Fano avrebbe potuto testare in modo esaustivo ogni possibile schema per la massima efficienza, ma sarebbe stato poco pratico. Così, invece, sviluppò un'approssimazione: per ogni messaggio, organizzava le lettere rilevanti per frequenza e quindi assegnava le lettere ai rami in modo che le lettere a sinistra in una data coppia di rami fossero usate nel messaggio all'incirca lo stesso numero di volte del lettere a destra. In questo modo i caratteri usati di frequente finirebbero su rami più corti e meno fitti. Un piccolo numero di lettere ad alta frequenza bilancerebbe sempre un numero maggiore di lettere a bassa frequenza.

Il risultato è stata una compressione straordinariamente efficace. Ma era solo un'approssimazione; doveva esistere una migliore strategia di compressione. Così Fano ha sfidato i suoi studenti a trovarlo.

Fano aveva costruito i suoi alberi dall'alto verso il basso, mantenendo quanta più simmetria possibile tra i rami appaiati. Il suo studente David Huffman ha capovolto il processo, costruendo gli stessi tipi di alberi ma dal basso verso l'alto. L'intuizione di Huffman era che, qualunque cosa accada, in un codice efficiente i due caratteri meno comuni dovrebbero avere i due codici più lunghi. Quindi Huffman identificò i due caratteri meno comuni, li raggruppò insieme come una coppia ramificata, e poi ripeté il processo, questa volta cercando le due voci meno comuni tra i caratteri rimanenti e la coppia che aveva appena costruito.

Si consideri un messaggio in cui l'approccio di Fano vacilla. In "schoolroom", O appare quattro volte e S/C/H/L/R/M una volta ciascuna. L'approccio di bilanciamento di Fano inizia assegnando la O e un'altra lettera al ramo sinistro, con i cinque usi totali di quelle lettere che bilanciano le cinque apparizioni delle lettere rimanenti. Il messaggio risultante richiede 27 bit.

Huffman, al contrario, inizia con due delle lettere non comuni - diciamo, R e M - e le raggruppa insieme, trattando la coppia come una singola lettera.

Il suo grafico di frequenza aggiornato gli offre quindi quattro scelte: la O che appare quattro volte, il nuovo nodo RM combinato che viene utilizzato funzionalmente due volte e le singole lettere S, C, H e L. Huffman sceglie nuovamente le due opzioni meno comuni, corrispondenti (dire) H con L.

Il grafico si aggiorna di nuovo: O ha ancora un peso di 4, RM e HL ora hanno ciascuno un peso di 2 e le lettere S e C sono autonome. Huffman continua da lì, in ogni passaggio raggruppando le due opzioni meno frequenti e quindi aggiornando sia l'albero che il grafico delle frequenze.

Alla fine, "schoolroom" diventa 11101111110000110110000101, eliminando un po' l'approccio top-down di Fano.

Un bit potrebbe non sembrare molto, ma anche i piccoli risparmi crescono enormemente se scalati di miliardi di gigabyte.

In effetti, l'approccio di Huffman si è rivelato così potente che, oggi, quasi tutte le strategie di compressione senza perdita utilizzano l'intuizione di Huffman in tutto o in parte. Hai bisogno di PKZip per comprimere un documento Word? Il primo passo implica un'altra strategia intelligente per identificare la ripetizione e quindi comprimere la dimensione del messaggio, ma il secondo passo è prendere il messaggio compresso risultante ed eseguirlo attraverso il processo di Huffman. Archiviare un'immagine come JPEG? Il tuo computer prima traduce l'immagine in una rappresentazione basata su testo e poi, ancora una volta, utilizza la codifica Huffman per comprimere quel testo.

Non male per un progetto originariamente motivato dal desiderio di uno studente laureato di saltare un esame finale.