Codifica di Huffman

Appunto di informatica che spiega i vari tipi di codifica, in che cosa consiste la codifica di Huffman e perché è vantaggiosa.

…continua

Autore

mathlover24

4 pagine

50 download

Informatica Vota

Scarica

Stampa
Condividi

Estratto del documento

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%!

Anteprima

Vedrai una selezione di 1 pagina su 4

Sintesi

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.