Nella lezione precedente abbiamo definito l'efficienza di un dato codice nella codifica di un dato messaggio come

E = Lunghezza messaggio in bit/Numero caratteri contenuti nel messaggio

Per esempio se codifichiamo la parola inglese (28 lettere)

ANTIDISESTABLISHMENTARIANISM

usando il codice ASCII che utilizza 8 bit per ogni carattere (compresi gli spazi) abbiamo una lunghezza totale di 8 x 28 = 224 bit da cui l'efficienza è pari a

E = 224/28 = 8 bit/carattere

come è ovvio che sia. Naturalmente questa non è la codifica più efficiente. Per esempio considerando il fatto che il nostro messaggio è composto solo da lettere maiuscole (senza minuscole, numeri, spazi o segni di interpunzione) potremmo usare un codice a 5 bit per rappresentare tutte le 26 lettere dell'alfabeto inglese. In questo modo la nostra efficienza diventerebbe pari a E = 5 bit/carattere.

Come abbiamo già visto, codifiche più efficienti sono quelle che sfruttano le diverse probabilità di occorrenza dei diversi caratteri. Se per esempio usiamo il codice Huffman per l'alfabeto inglese visto nella lezione precedente, possiamo calcolare la lunghezza in bit del messaggio codificato moltiplicando il numero di occorrenze di ciascuna lettera per la lunghezza in bit del codice necessario a rappresentarla. In pratica la parola ANTIDISESTABLISHMENTARIANISM contiene:

Lettera	Quantità	Codice	Bit codice	Bit totali
A	4	0011	4	16
B	1	11010	5	5
D	1	10010	5	5
E	2	000	3	6
H	1	10000	5	5
I	5	0111	4	20
L	1	10011	5	5
M	2	10110	5	10
N	3	0101	4	12
R	1	0110	4	4
S	4	10001	5	20
T	3	0010	4	12
Lunghezza totale messaggio in bit:				120

Pertanto l'efficienza del codice Huffman nel nostro caso è

E = 120/28 = 4,3 bit/carattere

Come si vede l'efficienza risulta ulteriormente migliorata. Occorre per inciso notare che il codice da noi proposto si basa sulle frequenze delle lettere in un generico testo in inglese e dunque non risulta ottimizzato per la trasmissione del nostro particolare messaggio (in cui alcune lettere, per esempio la C, non sono presenti, mentre altre, come la I, sono presenti in sovrabbondanza). Tuttavia questa osservazione è valida in generale, poiché il codice Huffman può essere ottimizzato rispetto a un dato messaggio solo se si conosce in anticipo il messaggio (e le sue probabilità) cioè, in pratica, se non c'è nulla di interessante da trasmettere!

Supponiamo ora di voler misurare l'efficienza del nostro codice non in relazione a uno specifico messaggio, ma in generale, cioè rispetto a un qualsiasi testo in lingua inglese. Immaginiamoci dunque un generico testo di lunghezza generica N (nel nostro esempio precedente era N=28). Quante volte, in media, comparirà ad esempio la lettera A nel nostro testo? Conoscendo la probabilità p_A associata alla lettera A (p_A = 0,0800) non è difficile stabilire che il numero di occorrenza N_A della lettera A in un testo generico (in inglese) di lunghezza N è dato da

N_A = p_A x N

Pertanto, se vogliamo stabilire quanti bit sono occupati in media in generale dalla lettera A in un generico messaggio codificato in questo modo, basta calcolare

L_A = n_bit^A x N_A = n_bit^A x p_A x N

Possiamo dunque calcolare la lunghezza totale in bit (L_bit) della codifica di un generico messaggio di lunghezza N così:

dove L_A, L_B, L_C etc. rappresentano il numero di bit occupati in media dalle singole lettere A, B, C fino a Z nel nostro generico messaggio.

Per calcolare l'efficienza generale del nostro codice basta dividere L_bit per il numero di caratteri N del generico messaggio:

da cui raccogliendo N a numeratore e semplificando con N a denominatore:

Il risultato ottenuto è molto importante è afferma che: "l'efficienza media generale di un dato codice può essere misurata moltiplicando la probabilità di ogni simbolo per il numero di bit della codifica e sommando tutti i risultati ottenuti". Si tratta in sostanza di una misura della lunghezza media pesata, cioè del numero medio di bit che occorrono per rappresentare ogni simbolo con quella data codifica.

La formula precedente può essere ulteriormente generalizzata a un qualsiasi codice composto da k simboli con probabilità p_k e numero di bit associati n_k ciascuno:

Tornando al codice Huffman di esempio, per valutarne l'efficienza media in generale dobbiamo moltiplicare la probabilità di ogni lettera per la lunghezza del codice relativo e poi sommare tutti i risultati così ottenuti:

Lettera	Probabilità	Codice	Probabilità x Lunghezza codice
A	0,0800	0011	0,0800 x 4 = 0,32
B	0,0150	11010	0,0150 x 5 = 0,075
C	0,0300	10100	0,0300 x 5 = 0,15
D	0,0400	10010	0,0400 x 5 = 0,2
E	0,1300	000	0,1300 x 3 = 0,39
F	0,0200	10111	0,0200 x 5 = 0,1
G	0,0150	11100	0,0150 x 5 = 0,075
H	0,0600	10000	0,0600 x 5 = 0,3
I	0,0650	0111	0,0650 x 4 = 0,26
J	0,0050	111100	0,0050 x 6 = 0,03
K	0,0050	111101	0,0050 x 6 = 0,03
L	0,0350	10011	0,0350 x 5 = 0,175
M	0,0300	10110	0,0300 x 5 = 0,15
N	0,0700	0101	0,0700 x 4 = 0,28
O	0,0800	0100	0,0800 x 4 = 0,32
P	0,0200	11000	0,0200 x 5 = 0,1
Q	0,0025	1111110	0,0025 x 6 = 0,015
R	0,0650	0110	0,0650 x 4 = 0,26
S	0,0600	10001	0,0600 x 5 = 0,3
T	0,0900	0010	0,0900 x 4 = 0,36
U	0,0300	10101	0,0300 x 5 = 0,15
V	0,0100	11101	0,0100 x 5 = 0,05
W	0,0150	11011	0,015 x 5 = 0,075
X	0,0050	111110	0,005 x 6 = 0,03
Y	0,0200	11001	0,02 x 5 = 0,1
Z	0,0025	1111111	0,0025 x 6 = 0,015
Efficienza media:			4,31 bit/carattere

 

 

precedente - successiva

Sito realizzato in base al template offerto da

http://www.graphixmania.it

Segui @ElePrograMania