Codifica di Huffman

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.

Foto: © Pixabay.

I nostri contenuti sono creati in collaborazione con esperti di high-tech, sotto la direzione di Jean-François Pillou, fondatore di CCM.net. CCM è un sito di high-tech leader a livello internazionale ed è disponibile in 11 lingue.
Il documento intitolato « Codifica di Huffman » dal sito CCM (it.ccm.net) è reso disponibile sotto i termini della licenza Creative Commons. È possibile copiare, modificare delle copie di questa pagina, nelle condizioni previste dalla licenza, finché questa nota appaia chiaramente.