3 COMPLESSITÀ DEI SISTEMI ECOLOGIC
3.3 U N METODO PER LA COSTRUZIONE DI UN CODICE A RIDONDANZA MINIMA
Un efficiente metodo per inviare i messaggi è quello di trasmettere, al loro posto, una sequenza di simboli.
Si consideri un insieme di simboli
€
S = s
{
1,s2,...,sn}
. Allora un codice è una mappaturareversibile di tutte le possibili sequenze dei simboli di S in sequenze di simboli (codewords) di un altro alfabeto
€
X = x
{
1, x2,..., xq}
. S rappresenta l’alfabeto della fonte, X l’alfabeto di codice(Abramson, 1963). Un codice è non singolare se tutte le parole del codice sono distinte. Un codice è univocamente decodificabile se e solo se ogni stringa può essere decodificata in un solo modo, ossia se e solo se la k-esima estenzione è non singolare per ogni k finito. Un codice univocamente decodificabile è istantaneo se è possibile decodificare ciascuna stringa senza doversi riferire a stringhe successive.
Dati un alfabeto di fonte e un alfabeto di codice è possibile costruire codici univocamente decodificabili e istantanei. Il criterio per la selezione tra questi, consiste nello scegliere quella codifica che permette di ottenere una lunghezza media minima.
Si assuma che ciascun simbolo richieda lo stesso tempo per la sua trasmissione, quindi il tempo necessario alla trasmissione di un messaggio è direttamente proporzionale al numero di simboli ad esso associati. Per una formalizzazione rigorosa, i simboli del codice saranno rappresentati da numeri. Il numero di messaggi nel suo insieme può essere chiamato N e sia pi la
probabilità associata all’i-esimo messaggio. Allora:
€
pi = 1 i=1
N
∑
(3.4)La lunghezza del messaggio li è il numero di simboli ad esso associato.
Quindi, la lunghezza media del messaggio è data dalla seguente formula:
L = pili i=1
N
Anand e Orloci (1996) utilizzano la lunghezza media del messaggio come misura di complessità totale.
Il problema è trovare un metodo di codifica che sia ottimo, cioè che rispetti le seguenti tre condizioni:
1) non possono esserci due messaggi con lo stesso codice;
2) il codice che trasmette il messaggio deve essere costruito in modo tale che non sarà necessario specificare nessuna ulteriore indicazione su dove il codice inizia e finisce dato che il punto di partenza della sequenza di messaggi è noto.
3) Il codice deve essere tale per cui la ridondanza di segnale sia minima
La restrizione 2 necessita che nessun messaggio possa essere codificato in modo tale che il suo codice appaia come la prima parte di un codice messaggio di lunghezza maggiore.
Per ottenere un ottimo codice, la lunghezza di un dato messaggio non può mai essere meno lungo di uno più probabile. Se ci sono diversi messaggi che hanno la stessa probabilità, allora è possibile che i codici per questi messaggi possano avere la stessa lunghezza. In questo caso i codici possono essere intercambiati senza influenzare la lunghezza media del codice per il messaggio d’insieme.
La codifica di Huffman (1952) è un algoritmo di codifica dell’entropia usato per la compressione dei dati, fondato sul principio di trovare un sistema ottimale per codificare stringhe, basato sulla frequenza relativa di ciascun carattere.
L’algoritmo per la costruzione del codice Huffman si basa sull’albero binario di codifica ed opera nel modo seguente:
1. Passa in rassegna il messaggio originale per analizzare il numero di ricorrenze di ciascun elemento che lo costituisce, ad esempio le occorrenze di diversi taxa di una stazione di campionamento, e le dispone in ordine di frequenza decrescente.
2. Unisce i due elementi meno frequenti trovati nel messaggio in un nuovo blocco che rappresenta in un certo modo un elemento di frequenza uguale alla somma delle frequenze dei due elementi e che può essere usato nelle costruzione di nuovi blocchi. Questo nuovo blocco rappresenta un nodo dell'albero (fig 3.2).
3. Identifica i due successivi elementi meno frequenti e li riunisce in un nuovo blocco, usando lo stesso procedimento descritto al punto 2.
4. Procede in questo modo finché tutti i simboli fanno parte dell'albero binario, chiamato albero di Huffman. Gli elementi più frequenti saranno quindi situati più vicino alla radice, mentre quelli più rari saranno a un cammino più lungo dalla radice dell'albero.
5. Assegna 1 a tutti i rami verso destra e 0 a tutti quelli verso sinistra (o viceversa). A ciascuna unità iniziale viene associato il codice ottenuto unendo in sequenza i bit che contraddistinguono i rami che si sono attraversati nel cammino dalla radice fino all'unità considerata. In questa maniera gli elementi più frequenti sono identificati da un codice breve, viceversa gli elementi rari ricevono una codifica lunga (fig. 3.3). Nel caso in cui l'albero fosse costituito da un nodo soltanto, il codice associato al carattere è indifferentemente 0 oppure 1.
6. Dopo aver creato le corrispondenze tra elementi e codifica, si produce in output il nuovo testo compresso, sostituendo a ogni elemento il codice ottenuto (tabella 3.1).
Figura 3.2 Metodo per la costruzione del codice Huffman
Figura 3.3 Albero binario di codifica
codewords li
A 0 1
B 11 2
C 100 3
D 101 3
Tabella 3.1 Codewords e relativa lunghezza di codice (li)
La codifica di Huffmann è ottima in quanto permette di ottenere la lunghezza media di codice minima, quindi è quella che meglio approssima l’entropia della sorgente.
Ne segue il primo teorema di Shannon:
La lunghezza media L di ogni codice binario C univocamente decodificabile per la variabile aleatoria x verifica la seguente disuguaglianza:
L≥H (3.6)
L’entropia H rappresenta pertanto il limite inferiore della lunghezza media di ogni codice univocamente decodificabile. L può essere più grande di H ma mai più piccolo: le due misure sono uguali nel caso in cui tutte le probabilità di occorrenza sono le stesse. Conoscendo questa relazione, si può dire che L è una misura di complessità totale (Anand e Orloci, 1996), mentre si può identificare H come una misura di complessità basata sul disordine. La differenza tra L e H definisce un’altra misura di complessità basata sull’organizzazione della rete, la cui interpretazione va valutata a seconda del caso studio.