Kioskea
Seguici Kioskea / Facebook
Cerca

Codifica di Huffman

Marzo 2015

La 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
MACE_HONTR
3222211111


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 :
MACE_HONTR
001001100100111110111110101011010111


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
Per poter consultare questo documento offline, ne potete scaricare gratuitamente una versione in formato PDF:
Codifica-di-huffman.pdf

Vedi anche


Huffman coding
Huffman coding
Código Huffman
Código Huffman
Huffman-Kodierung
Huffman-Kodierung
Codage de Huffman
Codage de Huffman
Codificação de Huffman
Codificação de Huffman
Il documento intitolato « Codifica di Huffman » da Kioskea (it.kioskea.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.