Codifica di Huffman
In informatica, per Codifica di Huffaman si intende un algoritmo di codifica dell'entropia usato per la compressione di dati, basato sul principio di trovare il sistema ottimale per codificare stringhe basato sulla frequenza relativa di ciascun carattere. Essa è stata sviluppata nel 1952 da David A. Huffman, uno studente dottorando presso il MIT, e pubblicata su A Method for the Construction of Minimum-Redundancy Codes (Un Metodo per la Costruzione di Codici con Minima Ridondanza).La codifica di Huffman usa un metodo specifico per scegliere la rappresentazione di ciascun simbolo, risultando in un codice senza prefissi (cioè in cui nessuna stringa binaria di nessun simbolo è il prefisso della stringa binaria di nessun altro simbolo) che esprime il carattere più frequente nella maniera più breve possibile. È stato dimostrato che la codifica di Huffman è il più efficiente sistema di compressione di questo tipo: nessun'altra mappatura di simboli in stringhe binarie può produrre un risultato più breve nel caso in cui le frequenze di simboli effettive corrispondono a quelle usate per creare il codice.
Per un insieme di simboli la cui cardinalità è una potenza di due e con una distribuzione probabilistica uniforme, la codifica di Huffman equivale alla semplice codifica a blocchi binari.
Nel 1951 a David Huffman e ad un suo collega al corso del MIT di Teoria dell'Informazione venna data la scelta tra una tesi scritta o un esame. Il docente, Robert M. Fano, assegnò una tesi sul problema di trovare il codice binario più efficiente. Huffman, incapace di dimostrare un qualsiasi codice che fosse il più efficiente, si stava rassegnando all'idea di mettersi a studiasre per l'esame, quando gli venne l'idea di usare un albero binario ordinato in base alla frequenza, e così dimostrò velocemente che questo metodo era il più efficiente.
Un'idea simile era stata usata in precedenza nella Codifica di Shannon-Fano (creata da Claude Shannon, inventore della teoria dell'informazione, e Fano, il docente di Huffman!), ma Huffman sistemò la sua più grande lacuna costruendo un albero ascendente anziché uno discendente.
Questa tecnica funziona creando un albero binario di simboli:
Le frequenze usate possono essere quelle generiche nel dominio dell'applicazione basate su medie precalcolate, o possono essere le frequenze trovate nel testo che deve essere compresso (questa variante richiede che la tabella di frequenza sia registrata insieme al testo compresso; vi sono diverse implementazioni che adottano dei trucchi per registrare queste tabelle efficientemente).
La codifica di Huffman è ottimale quando la probabilità di ciascun simbolo in input è una potenza di due. Le codifiche senza prefissi tendono ad essere inefficienti sui piccoli alfabeti, quando le probabilità spesso cadono tra potenze di due. L'espansione di simboli adiacenti in "parole" prima della codifica di Huffman può essere di aiuto.
Casi limite della codifica di Huffman sono collegati alla Sequenza di Fibonacci.
La Codifica Aritmetica produce dei leggeri guadagni su quella di Huffman, ma in pratica questi guadagni non sono abbastanza ampi da coprire la maggiore complessità computazionale richiesta dalla Codifica Aritmetica, che inoltre è coperta da brevetto IBM nei suoi concetti centrali.
Oggi spesso la codifica di Huffman è spesso usata come complemento di altri metodi di compressione: sono esempi
DEFLATE (l'algoritmo di PKZIP) e codec multimediali quali JPEG ed MP3.
Storia
Tecnica base
Caratteristiche principali
Variazioni
Codifica Adattiva di Huffman
Una variazione detta adattiva calcola le frequenze dinamicamente in base alle frequenze effettive più recenti nella stringa sorgente, in maniera analoga alla famiglia di algoritmi LZ.Algoritmo di Huffman a Template
Spesso i pesi usati nelle implementazioni di Huffman rappresentano delle probabilità numeriche, ma l'algoritmo in sè non lo richiede: esso richiede solamente una maniere di orfinare i pesi e di sommarli. La codifica di Huffman a Template permette l'uso di pesi non numerici (costi, frequenze e così via).Codifica di Huffman a base n
L'algoritmo di Huffman a base n usa l'alfabeto {0, 1, ..., n-1} per codificare il messaggio e costruire un albero a base n.Codifica di Huffman con costi per lettera diseguali
Nel problema standard della codifica di Huffman, è dato un insieme di parole e per ciascuna parole una frequenza positiva. Lo scopo è di codifica ogni parola 'p' con una parola-codice 'c' in un dato alfabeto.
La Codifica di Huffman con costi per lettera diseguali è una generalizzazione in cui le lettere dell'alfabeto di codifica possono avere lunghezze non uniformi. L'obiettivo è di minimizzare la media pesata della lunghezza delle parole-codice.Applicazioni
Link esterni
