Nella lezione precedente abbiamo imparato a misurare l'efficienza di un sistema di codifica per un certo insieme di caratteri (con associate probabilità) in base alla formula generale:

Tale formula fornisce il numero di bit per carattere utilizzato in media dal codice scelto per codificare un generico messaggio. Facciamo ancora un esempio. Consideriamo il codice Huffman per la codifica di un set di caratteri A,B,C e D con le probabilità indicate:

Carattere	A	B	C	D
Codice	0	10	110	111
Probabilità	0,7	0,1	0,1	0,1

L'applicazione della formula precedente ci permette di calcolare l'efficienza media del nostro codice:

E = p_A^.n_A + p_B^.n_B + p_C^.n_C + p_D^.n_D = 0,7 x 1 + 0,1 x 2 + 0,1 x 3 + 0,1 x 3 = 1,5 bit/carattere

Il risultato afferma che in media i messaggi codificati usando il precedente codice utilizzeranno 1,5 bit per ogni carattere codificato.

Vogliamo ora domandarci se esiste e come si può calcolare il limite minimo teorico all'efficienza che si può raggiungere dato un set di caratteri con le relative probabilità. In altre parole, quanto sarebbe possibile comprimere "al massimo" i nostri messaggi ovvero qual è l'efficienza associata al codice più efficiente che è possibile trovare? Ricordiamoci, a questo proposito, che l'efficienza massima si raggiunge quando E (numero di bit per carattere) assume il valore minimo.

Shannon dimostrò che la compressione teorica più efficiente si ottiene quando ogni carattere è codificato con un numero di bit pari alla quantità di informazione associata al carattere stesso, ovvero:

H (misurata in bit/carattere) rappresenta il valore minimo teorico possibile per l'efficienza E e viene detto entropia del codice.

Possiamo pensare all'entropia come la quantità di informazione media contenuta in ogni simbolo di un dato codice o alfabeto (intendendo il termine "alfabeto" nel senso più ampio del termine). Oppure possiamo definire l'entropia come la quantità di informazione media che acquisiamo al verificarsi di un certo evento. Facciamo di nuovo l'esempio del lancio della moneta non truccata, dove ci sono due eventi possibili entrambi con probabilità 0,5. In questo caso l'entropia è data da

H = p_testa^.I_testa + p_croce^.I_croce = 0,5 x log₂(1/0,5) +  0,5 x log₂(1/0,5) = 1 bit/carattere

cioè per ogni lancio della moneta noi acquisiamo un'informazione media pari a 1 bit. Se la moneta avesse due facce uguali e fornisse sempre un unico risultato (es. testa), l'entropia varrebbe:

H = p_testa^.I_testa + p_croce^.I_croce = 1 x log₂(1/1)  = 0 bit/carattere

cioè non si ottiene nessuna informazione utile dal lancio della moneta (poiché sapevamo già in anticipo il risultato). 

Prima di discutere ancora sui significati di H, proviamo a calcolarci l'entropia per il nostro codice Huffman associato all'alfabeto di quattro simboli A,B,C,D. L'informazione associata a ogni simbolo è data da:

I_A = log₂(1/P_A) = log₂(1/0,7) = 0,5 bit
I_B = I_C = I_D = log₂(1/P_BCD) = log₂(1/0,1) = 3,3 bit

da cui:

H = p_A^.I_A + p_B^.I_B + p_C^.I_C + p_D^.I_D = 0,7 x 0,5 + 0,1 x 3,3 + 0,1 x 3,3 + 0,1 x 3,3 = 1,34 bit/car

Il valore di H rappresenta la miglior efficienza che sarebbe in teoria raggiungibile col nostro codice. Il codice Huffman, come si è detto, rappresenta il codice binario più efficiente, cioè quello che si avvicina maggiormente al valore teorico. Infatti nel nostro caso l'efficienza valeva E = 1,5 bit/car, non molto al di sopra del limite teorico H = 1,34 bit/car.

Ripetiamo ora il calcolo dell'entropia per il codice Huffman per i caratteri dell'alfabeto inglese:

Lettera	Probabilità	Informazione	Probabilità x Info
A	0,0800	3,64385619	0,291508495
B	0,0150	6,058893689	0,090883405
C	0,0300	5,058893689	0,151766811
D	0,0400	4,64385619	0,185754248
E	0,1300	2,943416472	0,382644141
F	0,0200	5,64385619	0,112877124
G	0,0150	6,058893689	0,090883405
H	0,0600	4,058893689	0,243533621
I	0,0650	3,943416472	0,256322071
J	0,0050	7,64385619	0,038219281
K	0,0050	7,64385619	0,038219281
L	0,0350	4,836501268	0,169277544
M	0,0300	5,058893689	0,151766811
N	0,0700	3,836501268	0,268555089
O	0,0800	3,64385619	0,291508495
P	0,0200	5,64385619	0,112877124
Q	0,0025	8,64385619	0,02160964
R	0,0650	3,943416472	0,256322071
S	0,0600	4,058893689	0,243533621
T	0,0900	3,473931188	0,312653807
U	0,0300	5,058893689	0,151766811
V	0,0100	6,64385619	0,066438562
W	0,0150	6,058893689	0,090883405
X	0,0050	7,64385619	0,038219281
Y	0,0200	5,64385619	0,112877124
Z	0,0025	8,64385619	0,02160964
Entropia:			4,192511

Il valore di E così calcolato può essere confrontato quindi con l'efficienza del codice Huffman calcolata precedentemente (E = 4,31 bit/car), valore molto vicino dunque al massimo teorico.

 

precedente - successiva

Sito realizzato in base al template offerto da

http://www.graphixmania.it

Segui @ElePrograMania