Codifica di Huffman

Ultimo aggiornamento lunedì 6 novembre 2017 à 14:08 da Antonello Ciccarello.

David Huffman ha proposto nel 1952 un metodo statistico che permette di attribuire una parola di codice binario ai diversi simboli da comprimere (pixel o caratteri ad esempio). La lunghezza di ogni parola del codice non è identica per tutti i simboli: i simboli più frequenti (che appaiono più spesso) sono codificati con delle piccole parole di codice, mentre i simboli più rari ricevono dei codici binari più lunghi.

Si parla allora di codifica a lunghezza variabile (in inglese VLC per variable code length) prefissata per designare questo tipo di codifica dato che nessun codice è il prefisso di un altro. Così, la serie finale di parole codificate a lunghezza variabile sarà in media più piccolo rispetto ad un codice di dimensione costante.

Il codificatore di Huffman crea un arborescenza partendo da tutti i simboli e dalla loro frequenza di comparsa. I rami sono costruiti all'occorrenza partendo dai simboli meno frequenti. La costruzione dell'albero avviene ordinando in un primo tempo i simboli per frequenza di comparsa. Successivamente i due simboli che appaiono meno di frequente sono ritirati dalla lista e collegati ad un nodo il cui peso è uguale alla somma delle frequenze dei due simboli. Il simbolo di peso minore è assegnato al ramo 1, l'altro al ramo 0 e così via considerando ogni nodo formato come un nuovo simbolo, fino ad ottenere un nodo genitore detto radice.

Il codice di ogni simbolo corrisponde alla serie dei codici lungo il percorso che vanno da questo carattere alla radice. Quindi, più il simbolo è "profondo" nell'albero, più la parola del codice sarà lunga. Prendiamo la frase seguente: "COMMENT_CA_MARCHE". Ecco le frequenze di apparizione delle lettere:

M	A	C	E	_	H	O	N	T	R
3	2	2	2	2	1	1	1	1	1

Ed ecco l'albero corrispondente:

albero di huffman

I codici corrispondenti ad ogni carattere sono tali che i codici dei caratteri più frequenti sono corti e quelli corrispondenti ai simboli meno frequenti sono lunghi:

M	A	C	E	_	H	O	N	T	R
00	100	110	010	011	1110	1111	1010	10110	10111

Le compressioni basate su questo tipo di codifica danno dei buoni tassi di compressione, in particolare per le immagini monocromatiche (i fax ad esempio). Lo si usa soprattutto nelle raccomandazioni T4 e T5 dell'ITU-T.