Codifica di Huffman

La codifica di Huffman

Introduzione

Codifica a lunghezza variabile e codifica a lunghezza fissa
Teoricamente parlando, per codifica intendiamo un insieme di simboli utili alla trasmissione di un informazione. Questo insieme di simboli è definito codice.
Distinguiamo due tipi di codifica: la codifica a lunghezza fissa e la codifica a lunghezza variabile.
Parliamo di codifica a lunghezza fissa quando si codificano i caratteri di un'informazione ciascuno con il medesimo numero di bit.
La codifica a lunghezza variabile, un esempio è la Codifica di Huffman, utilizza un numero variabile di bit per ogni carattere da codificare.

La Codifica di Huffman

Abbiamo detto che la Codifica di Huffman è una codifica che utilizza un numero variabile di bit per ogni carattere. Come determinare la codifica di ogni carattere? Qui entra in gioco la frequenza, ovvero il numero di volte che un carattere è presente all'interno di un file.
È importante ricordare che la frequenza di un carattere e la sua lunghezza (il numero di bit necessari a codificarlo) sono inversamente proporzionali.
Un carattere piuttosto ricorrente in un file avrà una lunghezza di codifica minore.
Una codifica a lunghezza variabile è vantaggiosa perché permette un notevole risparmio di memoria generalmente compreso tra il 20% e il 90% del file codificato a lunghezza fissa. Infatti i codici di Huffman sono molto utilizzati nella compressione di alcuni file particolari (.zip, .mp3, .jpeg)
Il procedimento della Codifica di Huffman è spiegato nel file allegato.