La codifica di Huffman spiegata
Di solito i computer memorizzano ogni lettera con lo stesso numero di bit, otto nel semplice ASCII. È semplice ma dispendioso, perché alcune lettere sono molto più comuni di altre. Nel 1951 uno studente trovò il modo migliore per dare a ogni simbolo un codice di lunghezza propria, breve per i simboli frequenti e lungo per quelli rari, con una costruzione così semplice da stare in poche righe. Oggi la codifica di Huffman si trova in quasi ogni file compresso, immagine e suono che apri.
Codici brevi per i simboli comuni
Il codice Morse usava già l'idea negli anni Trenta dell'Ottocento: la E, la lettera più comune in inglese, è un solo punto, mentre la Q è linea linea punto linea. Un codice del genere fa risparmiare tempo e spazio ogni volta che alcuni simboli compaiono più spesso di altri. Ma le lunghezze variabili pongono un problema che il Morse risolveva con le pause: come si sa dove finisce un codice e dove comincia il successivo? E quali lunghezze dare a ogni simbolo per rendere il totale il più piccolo possibile?
Codici prefissi
Il primo problema scompare se nessun codice è l'inizio di un altro. Con i codici A = 0, B = 10, C = 110 e D = 111, i bit 0101100 si possono leggere solo come A B C A: appena i bit letti fin lì formano un codice, quel codice è completo. Questi codici prefissi corrispondono esattamente agli alberi binari con i simboli nelle foglie, in cui ogni ramo sinistro sta per 0 e ogni ramo destro per 1. Scegliere un codice significa scegliere un albero.
La costruzione di Huffman
Parti da una foglia per simbolo, pesata con la frequenza con cui compare. Prendi i due alberi più leggeri e uniscili sotto un nuovo nodo il cui peso è la loro somma, e ripeti finché non resta un solo albero. Questo è tutto l'algoritmo. I simboli rari vengono uniti per primi e finiscono in profondità nell'albero, con codici lunghi; quelli comuni vengono uniti per ultimi e restano vicino alla cima, con codici brevi. Con una coda di priorità richiede un tempo proporzionale a n log n per n simboli.
Perché è ottimo
In un albero ottimo, i due simboli più rari si possono sempre mettere come fratelli al livello più profondo: scambiarli con ciò che vi si trova può solo accorciare il totale. Uniscili in un solo simbolo con il loro peso combinato e il resto è lo stesso problema con un simbolo in meno, quindi il passo greedy non preclude mai la risposta migliore. Il numero totale di bit usati è uguale alla somma dei pesi di tutti i nodi interni, che le unioni mantengono il più piccola possibile.
Una tesina invece di un esame
Nel 1951 David Huffman, dottorando al MIT, seguiva il corso di teoria dell'informazione di Robert Fano. Fano diede ai suoi studenti una scelta: sostenere l'esame finale o scrivere una tesina sulla ricerca del codice binario più efficiente. Huffman stava quasi per rinunciare alla tesina, poi capì che costruire l'albero dal basso verso l'alto, invece di dividerlo dall'alto verso il basso come nel metodo di Shannon–Fano, dà sempre il risultato migliore. Lo pubblicò nel 1952; il metodo dello studente batté quello che il suo professore aveva messo a punto con Claude Shannon.
Vicino all'entropia
Claude Shannon dimostrò che nessun codice può usare in media meno bit per simbolo dell'entropia della sorgente. Un codice di Huffman raggiunge esattamente l'entropia quando ogni probabilità è una potenza di un mezzo, e non la supera mai di un bit intero per simbolo. Il divario conta quando un simbolo è molto comune: un simbolo con una quota del 99% ha comunque bisogno di almeno un bit intero, anche se porta solo circa 0,015 bit di informazione. La codifica aritmetica e i sistemi numerici asimmetrici (ANS) dei compressori più recenti evitano questo limite.
Codici di Huffman ovunque
La codifica di Huffman si usa raramente da sola, ma costituisce l'ultimo stadio di molti formati. Deflate, dentro ZIP, gzip e PNG, prima sostituisce le ripetizioni con riferimenti e poi scrive il risultato con codici di Huffman. JPEG li usa per i numeri che restano dopo la sua trasformazione dell'immagine, MP3 per i suoi dati audio e i fax per le lunghezze delle sequenze di bianco e di nero. Di solito i formati trasmettono un codice di Huffman canonico, in cui vanno memorizzate solo le lunghezze dei codici, perché i codici stessi si possono ricostruire a partire da esse.
Esploralo
Apri il costruttore di codici di Huffman per costruire, un passo alla volta, l'albero di ABRACADABRA, di MISSISSIPPI RIVER, di una tua frase o di qualsiasi altro testo. Guarda i due alberi più leggeri unirsi a ogni passo, fai clic su una foglia per vedere il suo codice, segui un simbolo attraverso i bit codificati e confronta il totale con un codice a lunghezza fissa, con UTF-8 e con l'entropia.
Domande frequenti
Qual è la differenza tra la codifica di Huffman e quella di Shannon–Fano?
La codifica di Shannon–Fano costruisce l'albero dall'alto, dividendo i simboli più e più volte in due gruppi di peso quasi uguale. Spesso è buona, ma non sempre ottima. Huffman costruisce l'albero dal basso unendo i due alberi più leggeri, e dà sempre il codice prefisso più breve possibile.
Il decodificatore ha bisogno dell'albero?
Sì, ha bisogno dello stesso codice. Per questo i file compressi lo memorizzano, di solito come elenco di lunghezze dei codici per un codice canonico, che occupa solo qualche decina di byte. Per testi brevi questo sovraccarico può superare il risparmio; il costruttore conta solo i bit codificati.
La codifica di Huffman può rendere un file più grande?
I simboli codificati non occupano mai più bit di un codice a lunghezza fissa per gli stessi simboli. Ma bisogna memorizzare anche la tabella dei codici, quindi per dati molto brevi o quasi casuali il risultato può essere leggermente più grande dell'originale.
Che cosa dice la disuguaglianza di Kraft?
Che un codice prefisso con lunghezze dei codici l₁, l₂, … esiste esattamente quando la somma di 2 elevato a −l su tutti i simboli è al massimo 1. Per un albero completo, come ogni albero di Huffman con almeno due simboli, la somma è esattamente 1.
Pronto a provarlo?
Apri PictorX nel tuo browser: nessuna installazione, nessuna carta di credito richiesta per iniziare.
Apri il costruttore di codici di Huffman