Questo articolo espone in forma introduttiva i princìpi che stanno alla base della codificazione di messaggi. In particolare, viene mostrata una intuitiva applicazione della codifica Huffman e delle tecniche di compressione a perdere.
Nella teoria della comunicazione, sviluppata dal matematico statunitense Claude Shannon, sono introdotti i seguenti concetti fondamentali:
Definiamo informazione un processo in cui vengono trasmesse delle notizie da un punto ad un altro. Ciò si verifica anche nella comunissima situazione di due persone che conversano. Gli interlocutori, comportandosi alternativamente da trasmettitore e da ricevitore, si servono di suoni comprensibili, i quali costituiscono un linguaggio naturale che, grazie ad un fondo comune di segnali, costituisce il codice che permette di scambiarsi i messaggi. In questo caso, il corrispondente canale attraverso cui vengono trasmesse le informazioni, è l'atmosfera.
Gli aspetti materiali ed energetici non interessano la teoria dell'informazione: di quelli si occupano il fisico e l'ingegnere. Infatti, l'informazione in sé non è né materia né energia; semplicemente essa imprime a certe strutture una opportuna forma funzionale, e in questo caso il punto fondamentale non è la quantità di energia necessaria per ottenere tale forma funzionale, bensì la quantità d'informazione.
Supponiamo di voler insegnare ad una scimmia il linguaggio gestuale in modo da farle scegliere di volta in volta il cibo che desidera mangiare: banane, budino, arachidi, torta di lamponi. Un modo semplice è insegnare alla scimmia due segnali per comunicare i propri desideri: per esempio, alzare la mano sinistra oppure la destra (codifica 1 di tab. I). Ognuno di questi due segnali fornisce l'informazione di 1 bit (il più piccolo segnale richiesto per comporre il messaggio).
| cibo | frequenza | codifica 1 | codifica 2 | codifica 3 |
| banana | 9 | D | DD | D |
| budino | 6 | S | DS | SD |
| torta | 2 | DD | SS | SSD |
| arachidi | 1 | DS | SD | SSS |
Ben presto, però, con questa codificazione si incontrerebbero le prime difficoltà di interpretazione. Supponiamo che la scimmia alzi tre volte la mano destra (DDD). Che cosa significa? Vuole tre banane, oppure una banana e due fette di torta?
Certo, si potrebbe ovviare aggiungendo un segnale di interruzione fra un messaggio e l'altro: ad esempio toccarsi la fronte con la mano destra. Ma questo sarebbe un terzo segnale e noi vogliamo utilizzarne solo due (praticamente il numero zero ed il numero 1).
Convenendo di indicare ogni cibo con due alzate di mano (codifica 2 di tab. I), la scelta diventa inequivocabile. La sequenza DDSDSSSS significa: una banana, una busta di arachidi, due porzioni di torta. In base a questa convenzione, possiamo affermare che ogni singola richiesta della scimmia comporta due segnali ossia 2 bit d'informazione, mentre per il menù completo (4 portate) occorrono 8 bit. Questa codificazione è efficiente (raggiunge il risultato) ma non è detto che sia efficace (raggiunge il risultato nel miglior modo possibile).
Se osserviamo le richieste della scimmia nell'arco di una settimana, potremmo ad esempio constatare che le arachidi non sono il cibo preferito dalla scimmia, mentre lo sono le banane. In altre parole, il segnale SD (arachidi) si presenta molto raramente, mentre il segnale DD (babane) è assai frequente. Di questo fatto bisogna tener conto per una codificazione ottimale. Supponiamo di aver constatato che la scimmia mangi ogni giorno nove banane, sei porzioni di budino, due fette di torta, una busta di arachidi.
Se la codificazione deve essere ottimale, occorre individuare per l'ordinazione delle banane, un segnale quanto più possibile breve. Invece, il segnale per l'ordinazione delle arachidi potrebbe essere più lungo.
Nel corso di una giornata, la scimmia consuma 18 portate le quali, nella efficiente codificazione 2 di tab.I, richiedono 36 segnali, ossia 36 bit.
Supponiamo di codificare le banane con l'alzata della mano destra: segnale D. Per evitare l'ambiguità nella scelta del prossimo cibo, il prossimo segnale deve essere SD. Infatti, in una sequenza di segnali, la combinazione DD farebbe sorgere il dubbio che fossero desiderate due volte banane. Anche DS potrebbe in qualche modo lasciare una certa ambiguità. Insomma, con un pò di tentativi (in pratica con la codifica Huffman, della quale non ci occuperemo), si può costruire la codificazione 3 di tab. 1.
L'ordinazione di 9 banane al giorno richiede ora soltanto 9 bit, contro i 18 bit della precedente codificazione. In più, sono da aggiungere quotidianamente 12 bit per le 6 porzioni di budino, 6 bit per le 2 fette di torta, 3 bit per la busta di arachidi. In totale 30 bit in confronto ai 36 della codificazione: questa nuova codificazione è senz'altro efficiente, ed è anche più efficace della codificazione 2. Al contrario, la codificazione 1, pur richiedendo solo 21 bit non è efficiente e dunque è da scartare.
Quanto accennato è sufficiente per comprendere come sia possibile compattare i files di dati e programmi riducendone le dimensioni. Sono in commercio programmi (uno dei più noti è WINZIP) che permettono facilmente di effettuare la compressione. Con lo stesso principio funzionano i programmi che permettono di aumentare lo spazio su disco: i dati vengono compressi durante il loro salvataggio e quindi decompressi durante la lettura; è ovvio che il tempo di accesso ai dati aumenta in conseguenza delle operazioni di codifica-decodifica, ma il continuo aumento della velocità di elaborazione dei processori, rende l'operazione interessante. D'altro canto, la continua riduzione del prezzo degli hard disk porta a preferire l'acquisto di un nuovo hardware piuttosto che installare un programma che, comunque, potrebbe andare in crash.
A questo punto, ci si potrebbe chiedere la ragione per cui i messaggi non sono già codificati nel modo più efficace. La risposta è semplice: non tutti i segnali si presentano con la stessa frequenza. Per esempio, se applichiamo ad un uomo la codificazione 3 proposta per la scimmia, questa non sarà altrettanto efficace in quanto i gusti gastronomici sono probabilmente differenti. Questa osservazione porta a considerare altri criteri per ridurre la dimensione dei segnali.
Oltre a queste tecniche di ottimizzazione della codificazione, ve ne sono altre che permettono di ridurre le dimensioni di un file di dati, rinunciando ad una parte delle sue informazioni. Per esempio, si consideri il messaggio:
| Oggi preso il treno potrò raggiungerti a Milano |
la semantica di questa frase non cambia eliminando un articolo ed un prefisso:
| Oggi preso treno potrò raggiungerti Milano |
anche l'eliminazione di un verbo non altera la comprensione del messaggio:
| Oggi preso treno raggiungerti Milano |
infine, se l'ospite è residente, si può eliminare la destinazione:
| Oggi preso treno raggiungerti |
sebbene l'ultima compressione del messaggio sia molto drastica, il senso è ancora comprensibile. Questo significa che un messaggio è generalmente ridondante, ossia contiene elementi in eccesso non necessari per la sua comprensione. Questa compressione è "a perdere", ossia una parte dell'informazione viene eliminata e non può essere ricostruita. Lo svantaggio di questa tecnica consiste nel fatto che la riduzione della ridondanza riduce la possibilià di interferenza con i disturbi. Se per esempio, si perde il verbo "prendere" nella prima frase, il senso della stessa è inalterato, ma se lo stesso verbo è danneggiato nell'ultimo messaggio, il destinatario non capirà se la parte mancante comprende il verbo "prendere" oppure "perdere"...
| Oggi p..so treno raggiungerti |
in pratica, questa eventualità si può aggirare con l'impiego di algoritmi per controllare che il messaggio inviato sia uguale al messaggio ricevuto. Con queste tecniche, il ricevitore controlla automaticamente (senza rinviare il messaggio all'emittente, che dopo dovrebbe confermare con un terzo messaggio la correttezza del primo) la correttezza del segnale ricevuto.
Ora, poniamoci in una situazione più complessa. Consideriamo il quadro di un grande pittore. Forme e colori sono il linguaggio usato dall'artista per comunicarci qualcosa... un'emozione, una sensazione di stupore o di serenità, un'informazione.
Ed ecco ciò che può sembrare un'eresia: è possibile descrivere in maniera rigorosa e completa il quadro utilizzando un'altra forma di linguaggio? Certo, sembrerebbe incredibile poter esprimere in altra forma questo oggetto d'arte senza perdere qualcosa del suo contenuto. Con le parole, potremmo decrivere la scena raffigurata, il numero e la posizione degli elementi che la costituiscono, ma certo avremmo una difficoltà con i colori e le loro sfumature, con la luce e la traccia del pennello, ecc.
Però questa evidente limitazione del linguaggio non è una ragione per abbandonare l'impresa. Potremmo immaginare di dividere la superficie del quadro con una quadrettatura molto fitta in modo da permettere l'esame di piccole superfici elementari ognuna delle quali considerabile come uniforme per colore. E questo anche in conseguenza delle imperfezioni dell'occhio (ecco che si presenta il concetto di "rumore" con le inevitabili limitazioni ad esso legate). Delimitate così le piccole superfici elementari del quadro, potremo attribuire ad ognuna di esse un insieme di risultati derivanti dalle osservazione: posizione dell'elemento all'interno della superficie superficie, colore e grana della trama. Questi risultati potranno essere codificati in modo che ogni informazione contenuta nel quadro sarà convertita in un insieme ordinato di molti numeri. Così, le forme e i colori, ossia il linguaggio pittorico dell'artista, saranno rimpiazzati da una serie di numeri che sono il lessico di un linguaggio del tutto diverso dal primo, sebbene equivalenti dal punto di vista dell'informazione (il valore che attribuiamo all'opera originale è ovviamente una questione del tutto diversa).
Dimostrato con un esempio suggestivo che qualsiasi immagine può essere codificata in forma numerica, è ovvio che le codificazioni comportanti l'eliminazione parziale del messaggio, possono essere applicate alle immagini. Per esempio, uniformando le zone con limitate variazioni di colore e contrasto: maggiore è la variazione tollerata, maggiore è la riduzione delle dimensioni del messaggio. Anche in questo caso, tuttavia è possibile un controllo del messaggio compresso per garantire che, comunque, non vengano perse informazioni superiori alla tolleranza prevista. E' questo il principio con cui si ottengono immagini con contenuto d'informazione minore: le dimensioni restano invariate, però si perde parte del messaggio.
