Nella lezione precedente abbiamo visto come, calcolando la diversa probabilità delle lettere dell'alfabeto inglese, è possibile, almeno in teoria, inventare codici più efficienti e con una migliore compressione. Non abbiamo tuttavia ancora visto come potrebbe essere fatto un codice "compresso", cioè un codice realizzato in modo da sfruttare le differenti probabilità associate ai vari simboli.

Data la complessità dell'argomento, conviene per il momento lasciar perdere le lettere dell'alfabeto e considerare un esempio più semplice. Consideriamo dunque un alfabeto composto da soli quattro simboli: A, B, C e D (l'esempio è meno astratto di quanto potrebbe sembrare: il nostro DNA usa un "alfabeto" composto da solo quattro codici, detti basi: adenina, guanina, citosina e timina). Se tutti i simboli hanno la stessa probabilità di comparire (P =1/4 = 0,25), l'informazione contenuta in ogni simbolo è la stessa e uguale a

I =  log₂(1/P) = log₂(1/0,25) = 2 bit

Ciò è in accordo col fatto che occorrono 2 bit per codificare 4 simboli diversi (es. A=00, B=01, C=10, D=11).

Supponiamo ora che le probabilità associate ai quattro simboli siano diverse e che la A sia il simbolo più probabile (P_A = 0,7), mentre gli altri tre simboli hanno tutti la stessa probabilità (P_B=P_C=P_D=0,1). Ciò significa che un tipico messaggio scritto nel nostro alfabeto avrà un aspetto di questo tipo:

AAAABAAAAAAAAADAAAAAAAABAAACDAAA

Calcoliamo ora la quantità di informazione associata ai diversi simboli:

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

Come abbiamo già osservato, i risultati del calcolo di I possono fornire numeri con la virgola. Naturalmente non possiamo inventarci un codice che assegni alla A mezzo bit (I_A=0,5) e agli altri caratteri 3,3 bit ciascuno, come suggerisce la formula di Shannon.

Quello che possiamo fare è inventare un codice che usi il minor numero possibile di bit per rappresentare la A e quindi un numero di bit maggiore per rappresentare gli altri tre simboli. Qualcuno potrebbe pensare che potremmo usare un solo bit, es. 0, per la A, ancora un solo bit, es. 1, per rappresentare una qualsiasi delle altre lettere (es. la B) e quindi due bit ciascuno per rappresentare C (es. 00) e D (es. 01), come mostrato in tabella:

A	B	C	D
0	1	00	01

Questo codice, sebbene semplice, non funziona. Supponiamo infatti di ricevere il seguente messaggio:

01001100....

Il primo bit '0' potrebbe rappresentare una A, ma potrebbe anche essere l'inizio di una D (01). Così, nel nostro esempio, l'inizio del messaggio potrebbe essere letto come AB oppure come D.

Nell'inventare un codice dobbiamo dunque fare in modo che esso possa essere letto da sinistra a destra (nell'ordine con cui vengono emessi e ricevuti i simboli) senza ambiguità. Un codice di questo tipo è detto codice prefisso (prefix code) perché nessuna parola del codice deve essere l'inizio di un'altra parola. Si consideri per esempio la seguente codifica a prefisso:

A	B	C	D
0	100	110	111

In questo caso non esiste nessuna ambiguità possibile perché la stringa

01001100....

verrebbe decodificata come:

0 100 110 0....
A   B   C   A....

Si noti, per inciso, che l'alfabeto Morse non presenta questo tipo di problemi dal momento che le singole lettere di una parola venivano separate da una pausa e una pausa ancora più lunga veniva inserita fra una parola e l'altra (in questo senso si potrebbe dire che il codice Morse usa in realtà 4 simboli: il punto, la linea, la pausa e la pausa lunga).

Poniamoci ora il problema di valutare il grado di efficienza di un codice per un dato insieme di simboli. Dal nostro punto di vista il codice più efficiente è quello che codifica un messaggio col minor numero di bit possibili, cioè con la massima compressione.

Riprendiamo il nostro esempio dell'alfabeto composto da soli 4 simboli (A, B, C, D) e consideriamo di nuovo la stringa da codificare (32 caratteri):

AAAABAAAAAAAAADAAAAAAAABAAACDAAA

Se usiamo 2 bit per ogni carattere la lunghezza totale del messaggio codificato è di 32x2=64bit. Se invece usiamo il codice prefisso A=0, B=100, C=110 e D=111 la codifica risulta la seguente (per un totale di 42 bit):

000010000000000011100000000100000110111000

Un modo più veloce per calcolare la lunghezza del messaggio è contare il numero di A, B, C e D che contiene e moltiplicare ognuno di tali numeri per la lunghezza del codice corrispondente. Nel nostro messaggio c'erano 27 A (ciascuna da 1 bit), 2 B (3 bit ciascuna), 1 C (3 bit) e 2 D (3 bit) per un totale di 27 x 1 + 2 x 3 + 1 x 3 + 2 x 3 = 42 bit.

Come possiamo osservare il codice che tiene conto della diversa probabilità dei vari simboli è più efficiente in quanto consente di codificare il messaggio con soli 42 bit invece dei 64 che occorrevano assegnando due bit a tutti i simboli indifferentemente.

Naturalmente questo "risparmio" sulla lunghezza del codice si basa sull'ipotesi fondamentale che le probabilità calcolate siano corrette per il messaggio in questione. Se per esempio il nostro trasmettitore dovesse inviare un messaggio dove le A non sono prevalenti, la codifica basata sulle probabilità produrrebbe un codice più lungo invece di uno più breve.

Come possiamo dunque misurare l'efficienza di un codice? Un modo molto semplice e naturale consiste nel misurare la lunghezza totale del messaggio (in bit) diviso il numero di caratteri trasmessi. Chiamando questa misura di efficienza E l'efficienza del codice che usa due bit per trasmettere ogni carattere è data da:

E_{codice non compresso} = Lunghezza messaggio/Numero caratteri = 64/32 = 2 bit/carattere

come è ovvio che sia. Considerando invece il nostro codice compresso, la sua efficienza è data da:

E_{codice compresso} = Lunghezza messaggio/Numero caratteri = 42/32 = 1,3 bit/carattere

Si noti l'unità di misura di E (bit per carattere) e il miglioramento ottenuto usando un codice compresso basato sulle probabilità.

Si presti attenzione al fatto che in generale il codice più efficiente è quello che presenta un valore di E minimo, cioè che utilizza il minor numero di bit per carattere. Ciò può provocare qualche confusione poiché per rendere massima l'efficienza del codice occorre minimizzare E (e non renderlo massimo, come si potrebbe pensare).

Ora che abbiamo trovato un'unità di misura per valutare l'efficienza di un dato codice, possiamo domandarci se il codice compresso che abbiamo trovato sia la soluzione migliore (cioè la più efficiente) per codificare il nostro messaggio. La risposta è no. Si consideri il seguente diverso codice prefisso per i caratteri A, B, C, D:

A	B	C	D
0	10	110	111

Si noti che abbiamo "tolto un bit" alla codifica di B. In questo modo il codice rimane valido, cioè interpretabile senza ambiguità (in quanto ogni carattere è codificato con una sequenza di bit che non è l'inizio di nessun altro codice), ma produce messaggi codificati più brevi. Per esempio considerando di nuovo la sequenza

AAAABAAAAAAAAADAAAAAAAABAAACDAAA

in questo caso abbiamo che la lunghezza totale è data da 27 x 1 + 2 x 2 + 1 x 3 + 2 x 3 = 40 bit. L'efficienza risulta dunque

E_{nuovo codice compresso} = Lunghezza messaggio/Numero caratteri = 40/32 = 1,25 bit/carattere

Come si può notare abbiamo ulteriormente migliorato, anche se di poco, l'efficienza della codifica.

L'ultima codifica usata è stata generata in base a un algoritmo detto di Huffman che, sarebbe possibile dimostrare, produce in generale il codice prefisso binario più efficiente possibile. In altre parole si potrebbe dimostrare che non esiste nessun altro codice prefisso binario che genera una codifica più efficiente del codice Huffman. Cioè il codice Huffman è la migliore codifica possibile per un dato insieme di simboli con un dato insieme di probabilità note.

Senza voler qui approfondire l'argomento di come funzioni l'algoritmo di Huffman per generare il codice più efficiente, riportiamo qui sotto il codice Huffman per l'alfabeto inglese, tenendo conto della diversa distribuzione di probabilità delle diverse lettere dell'alfabeto:

Lettera	Probabilità	Codice
A	0,0800	0011
B	0,0150	11010
C	0,0300	10100
D	0,0400	10010
E	0,1300	000
F	0,0200	10111
G	0,0150	11100
H	0,0600	10000
I	0,0650	0111
J	0,0050	111100
K	0,0050	111101
L	0,0350	10011
M	0,0300	10110
N	0,0700	0101
O	0,0800	0100
P	0,0200	11000
Q	0,0025	1111110
R	0,0650	0110
S	0,0600	10001
T	0,0900	0010
U	0,0300	10101
V	0,0100	11101
W	0,0150	11011
X	0,0050	111110
Y	0,0200	11001
Z	0,0025	1111111

Osserviamo che:

• si tratta di un codice prefisso poiché nessuna lettera è codificata usando la sequenza iniziale di bit di un'altra lettera;
  
  
• le lettere più probabili sono codificate usando meno bit (es. la E rappresentata con solo 3 bit) rispetto alle lettere meno probabili (es. la Q rappresentata con 7 bit);
  
  
• il codice Huffman per un dato insieme di simboli e probabilità non è unico, dal momento che l'efficienza e le proprietà del codice rimangono le stesse anche se si scambiano fra loro i codici di due lettere con uguale lunghezza (es. la R e la T potrebbero benissimo essere codificate con R=0010 e T=0110 senza che cambi nulla);
  
  
• il codice Huffman dipende strettamente dalle probabilità di occorrenza dei simboli (usando il codice in esempio per un testo in lingua italiana non si otterrebbe sicuramente la codifica più efficiente!);
  
  
• data un insieme di simboli (nel nostro caso le 26 lettere dell'alfabeto inglese) e di probabilità (quelle riportate in tabella) si potrebbe dimostrare che non si può trovare una codifica più efficiente di questa, cioè un codice che utilizzi meno bit per rappresentare un messaggio;
  
  
• per semplicità il codice proposto non contiene nessuna codifica per spazi, segni di interpunzione etc; a meno che non si voglia trasmettere un'unica parola, sarà necessario attribuire un codice almeno anche allo spazio (basandosi anche in questo caso sulla probabilità di occorrenza del carattere "spazio" nei testi inglesi).

Algoritmo interattivo per generare il codice Huffman dato un testo qualsiasi.

 

precedente - successiva

Sito realizzato in base al template offerto da

http://www.graphixmania.it

Segui @ElePrograMania