vuoi
o PayPal
tutte le volte che vuoi
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.
CODIFICA DI HUFFMAN
Esercizio svolto
Supponiamo di avere la frase “tigre contro tigre”, e di volerla codificare sia
a lunghezza fissa che lunghezza variabile.
CODIFICA LUNGHEZZA FISSA
Costruiamo una tabella con le frequenze di ciascun carattere e la sua
codifica. Spazio
Carattere R T E G I O C N
Frequenza 3 3 2 2 2 2 2 1 1
Codifica l. 0000 0001 0010 0011 0100 0101 0110 0111 1000
fissa
La frase sarà quindi codificata:
000101000011000000100110011101011000000100000101011000010100001100000010
(72 bit) CODIFICA LUNGHEZZA VARIABILE
Costruiamo una tabella con le frequenze di ciascun carattere.
Spazio
Carattere R T E G I O C N
Frequenza 3 3 2 2 2 2 2 1 1
Sommiamo SEMPRE le ultime due frequenze e ricostruiamo la tabella.
Carattere R T CN E G I O Spazio
Frequenza 3 3 2 2 2 2 2 2
Carattere OSpazio R T CN E G I
Frequenza 4 3 3 2 2 2 2
Carattere GI OSpazio R T CN E
Frequenza 4 4 3 3 2 2
Carattere CNE GI OSpazio R T
Frequenza 4 4 4 3 3
Carattere RT CNE GI OSpazio
Frequenza 6 4 4 4
Carattere GIOSpazio RT CNE
Frequenza 8 6 4
Carattere RTCNE GIOSpazio
Frequenza 10 8
0 1
1 0 1
0 0 1 1 0 1
E
0 1 0
0 1
T R N C I G Spazio O
Osserva: come si può vedere in figura, è stato costruito il cosiddetto Albero di
Huffman, raggruppando tutti i caratteri a due a due, nell’ordine con il quale abbiamo
sommato le frequenze. Una volta costruito l’albero, si inserisce lo 0 su ogni
diramazione di sinistra, e l’1 su ogni diramazione a destra.
Costruiamo adesso una tabella di codifica aiutandoci con l’albero.
Carattere R T E G I O Spazio C N
Frequenza 3 3 2 2 2 2 2 1 1
Codifica 001 000 011 101 100 111 110 0101 0100
Ora codifichiamo la frase:
00010010100101111001011110100000001111110000100101001011 (56 bit)
Grazie alla codifica a lunghezza variabile abbiamo ottenuto un risparmio del 22,2%!
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo
