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.
| Carattere | Spazio | R | T | E | G | I | O | C | N |
|---|---|---|---|---|---|---|---|---|---|
| Frequenza | 3 | 3 | 2 | 2 | 2 | 2 | 2 | 1 | 1 |
| Codifica l. fissa | 0000 | 0001 | 0010 | 0011 | 0100 | 0101 | 0110 | 0111 | 1000 |
La frase sarà quindi codificata:
000101000011000000100110011101011000000100000101011000010100001100000010
(72 bit)
Codifica lunghezza variabile
Costruiamo una tabella con le frequenze di ciascun carattere.
| Carattere | Spazio | 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%!
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.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo
