Il codice di Huffman: cos’è e come funziona

Con Huffman codici più brevi ai simboli più frequenti

La codifica di Huffman è un algoritmo che basa la propria codifica di un testo sulla frequenza dei caratteri. Pubblicato nel 1952 da David A. Huffman, la codifica di Huffman effettua un’analisi statistica del dato da comprimere, da cui inizia una fase di analisi per decidere i codici da assegnare ad ogni simbolo in base alla loro frequenza nel testo. Ad esempio, dato un testo il codice di Huffman analizza la frequenza di ogni carattere (il numero di volte che ogni carattere si ripete nel testo), dopodiché ai caratteri che si ripetono più frequentemente viene assegnato un codice più breve, al contrario ai caratteri che sono meno presenti viene assegnato un codice più lungo.

La codifica di Huffman rappresenta il sistema di compressione più efficiente basato sull’analisi della frequenza dei simboli in un dato. I passi che bisogna eseguire per comprimere un dato con la codifica di Huffman possono essere riassunti in tre passi:

  1. Analizzare la frequenza dei simboli in un dato;
  2. Raggruppare le coppie di simboli con frequenza minore ed aggiungerli all’Albero di Huffman;
  3. Costruire il codice assegnando una codifica più piccola ai simboli più frequenti nel testo.

L’albero di Huffman e l’assegnazione dei codici

Wikipedia offre un ottimo esempio animato sul funzionamento della codifica di Huffman con la frase in francese “Here’s an example of optimized Huffman coding using the French subject string j’aime aller sur le bord de l’eau les jeudis ou les jours impairs“, contando i vari caratteri possiamo sciverci la frequenza di ogni simbolo (ad esempio la lettera J si ripete 3 volte, la lettera a si ripete 4 volte e così via). Mettendo in ordine crescente la frequenza dei simboli, ad ogni passo prendiamo i caratteri con frequenza minore e li unire in un albero fino ad aggiungere ogni carattere del testo.

Come funziona il codice di Huffman

Completato l’albero di Huffman, a partire dal nodo radice si assegna al ramo sinistro il codice 0 e al ramo destro il codice 1. Ogni lettera del testo verrà codificata dai codici dato dal percorso dell’albero dalla radice fino al nodo che contiene la lettera. Ad esempio nell’immagine sottostante possiamo dedurre che la lettera a viene codificata con il codice 0110, la lettera e con il codice 100 e così via.

Come funziona il codice di Huffman

Da questi esempi possiamo notare che le lettere con una frequenza minore sono state codificate con codici più lunghi rispetto alle lettere che si presentano più spesso nel testo.

L’algoritmo del codice di Huffman si può realizzare utilizzando una coda a priorità e un albero binario in cui assegnare un nodo foglia ad ogni simbolo del testo. Ad ogni passo si possono collegare i due nodi con frequenza minore ed assegnargli la somma delle loro frequenze. Questo valore viene inserito in una lista che servirà per creare un albero di Huffman ed ottenere il codice da assegnare ai simboli alle somme delle frequenze assegnate.
L’utilizzo di una coda a priorità per un algoritmo di Huffman comporta una complessità di O(n^2), invece utilizzando una versione più avanzata dell’algoritmo con una coda a priorità basata su heap avremo un tempo di esecuzione di O(n log n).

La codifica ottenuta mediante Huffman non è univoca, si possono invertire i codici assegnati ai simboli con la stessa frequenza (se presenti) ed ottenere lo stesso livello di compressione.
L’algoritmo di Huffman è un tipico esempio di algoritmo
greedy perchè ad ogni iterazione fonde i due nodi più piccoli dell’albero indipendentemente dagli altri nodi e non li modifica più.

Photo credit: Wiki Commons

Pubblicato in Sistemi Informativi Taggato con: , , , ,

Lascia un commento

Il tuo indirizzo email non sarà pubblicato. I campi obbligatori sono contrassegnati *

*