Alla fine degli anni 40, agli albori della Teoria dell'Informazione, nuove ed efficienti tecniche di codifica cominciavano ad essere scoperte ed i concetti di entropia e ridondanza venivano introdotti. L'entropia è una misura dell'incertezza con la quale un testo viene prodotto da una sorgente (per esempio un fax, un modem ecc.). Ciò che in quegli anni si proponeva di realizzare, vista l'assenza di elaboratori elettronici, era definire degli algoritmi che riuscissero a codificare testi in modo che questi potessero essere inviati da una sorgente ad una destinazione senza che nessuno, tranne il destinatario, potesse carpirne il contenuto oppure algoritmi che potessero permettere al destinatario di capire se un testo codificato fosse stato trasmesso con errori, dovuti alla trasmissione o ad un sabotaggio da parte di terzi. Nasce in tal modo il concetto di codice e di codifica. Un codice può essere visto come una tabella con due colonne: la prima colonna contiene i caratteri contenuti nel testo originario, la seconda contiene le parole di codice. Codificare un testo significa sostituire ciascuna parola (o carattere) del testo originario con la corrispondente parola di codice presente nella tabella del codice. Un codice è univocamente decodificabile se è possibile decodificare ogni carattere del testo in input in modo univoco. Nell'ambito dei codici univocamente decodificabili è possibile riconoscere i codici prefissi. Un codice è prefisso se è possibile decodificare correttamente una parola di codice non appena essa è riconosciuta nel testo codificato T, poiché nessuna parola di codice è prefisso di un'altra parola di codice. In generale una parola W è prefisso di un'altra parola W' se W' = Wa. Di seguito è mostrato un esempio di codice prefisso a lunghezza variabile

Se il testo codificato è T = 0001111, allora scorrendo T si riconosce dapprima il carattere A, quindi, il carattere B ed infine il carattere E, per cui il testo decodificato sarà ABE. Una codifica, d'altronde, è una regola che associa ad ogni carattere (o parola) del testo una parola di codice. Con l'avvento dei moderni calcolatori elettronici si è sviluppato parallelamente alla teoria dei codici il concetto di compressione dati. Supponiamo di avere a che fare con un testo su di un file: ogni carattere viene rappresentato da una stringa di 8 bit, quindi se riuscissimo a codificare un carattere utilizzando meno di otto bit, sarebbe possibile diminuire lo spazio occupato dal testo originale. Utilizzando i concetti di entropia e ridondanza è stato possibile sviluppare algoritmi capaci di risalire alla codifica di un carattere, conoscendone il numero di occorrenza in un dato testo in modo tale da ridurre la taglia complessiva del testo stesso. E possibile affermare che il primo di tali algoritmi è stato l'algoritmo proposto da C. Shannon e R. M. Fano. Prima di descriverlo è importante ricordare che, fissato un codice, affinché esso sia efficiente, deve accadere che parole di codice associate a caratteri meno frequenti siano costituite da più bit, mentre parole di codice associate a caratteri più frequenti siano costituite da meno bit. Detto ciò possiamo definire ed analizzare l'algoritmo di Shannon-Fano. Esso innanzitutto costruisce una lista L formata da coppie del tipo (Carattere, Numero di occorrenza) ordinata in modo non decrescente rispetto al numero di occorrenza, dove per numero di occorrenza si intende il numero di volte che tale carattere compare nel testo. Di seguito viene mostrata la procedura di creazione del codice:

ShannonFanoCode(L)

1. if |L| == 1 then
2.     return 0
3. if |L| >= 2 then
4.     "dividere L in due sottoliste L₁ ed L₂ , considerando le coppie nell'ordine in cui si presentano in L₁ , in modo tale che la differenza tra _(x,n)   n e _(x,n) n sia minima"
5.     "aggiungere uno 0 alla parola di codice w_x per tutti i caratteri x : (x,n) L₁"
6.    "aggiungere uno 1 alla parola di codice w_x per tutti i caratteri x : (x,n) L₂"
7.     if |L₁| == 1 then
8.         return w_x
9.     else
10.         ShannonFanoCode(L₁)
11.     if |L₂| == 1 then
12.         return w_x
13.     else
14.         ShannonFanoCode(L₂)

La Figura 1 dà un esempio di esecuzione dell'algoritmo di Shannon-Fano. Il codice prodotto non porta ad una codifica ottima dal punto di vista della lunghezza media delle parole di codice prodotte, dove per lunghezza media di parole di codice si intende il valore M = (_i=1^N  n_il_i)/N con N numero di caratteri presenti nel testo ed l_i lunghezza della parola di codice associata al carattere i-esimo, mentre n_i rappresenta il numero di occorrenza del carattere i-esimo. Con riferimento al codice prodotto in Figura 1 si ha che la lunghezza media delle parole di codice prodotte è pari a M = (15 * 2 + 7 * 2 + 6 * 2 + 6 * 3 + 5 * 3)/39 = 2.28. Un algoritmo che minimizza M è l'algoritmo di Huffman, che riprende alcuni concetti di base dell'algoritmo di Shannon-Fano. La procedura per la costruzione del codice è semplice ed elegante. A differenza dell'algoritmo di Shannon-Fano viene creata una lista L di nodi ognuno dei quali contiene due informazioni: carattere e numero di occorrenza; essa avrà tanti nodi quanti sono i caratteri distinti nel testo. L'algoritmo, che porterà alla costruzione di un albero, si basa sui seguenti passi:

1. ogni nodo di L viene inizializzato con un carattere distinto del testo e con il numero di occorrenza corrispondente;
2. la lista viene ordinata in modo non decrescente rispetto al numero di occorrenza;
3. se |L| >= 2 allora viene eseguito il passo 4, altrimenti l'algoritmo termina restituendo un nodo, ossia la radice dell'albero;
4. i due nodi con numero di occorrenza più basso vengono cancellati dalla lista e divengono figli di un nuovo nodo, che contiene numero di occorrenza pari alla somma dei numeri di occorrenza dei figli ed un carattere fittizio;
5. il nuovo nodo viene inserito nella lista in posizione tale da lasciarla ordinata e si ritorna al passo 2.

Figura l: Algoritmo di Shannon-Fano: le linee orizzontali stanno ad indicare le divisioni che subisce la lista L ad ogni passo dell'algoritmo, mentre nelle righe risultanti è possibile leggere le parole di codice associate a ciascun carattere.

L'albero così costruito viene chiamato Albero di Huffman. Una volta costruito tale albero, si procede alla codifica dei caratteri, contenuti nei nodi foglia, scendendo dalla radice verso i nodi foglia ed aggiungendo uno 0 alla parola di codice, se si scende a sinistra, ed un 1, se si scende a destra (il tutto non cambia se si aggiunge 1, quando si scende a sinistra, e uno 0, quando si scende a destra). Nel caso in cui l'albero fosse costituito da un nodo soltanto, viene assegnato indifferentemente 0 oppure 1 alla parola di codice associata al carattere presente nel nodo. Segue un esempio di albero di Huffman ottenuto dall'esecuzione dell'algoritmo descritto:

Esempio 1.1 Facendo riferimento al numero di occorrenza dei caratteri relativi alla Figura 1, viene costruito l'albero di Huffman, dato in Figura 2. Di seguito è mostrata una tabella contenente le codifiche dei caratteri derivanti dall'albero di Huffman di Figura 2:

Figura 2: Albero di Huffman: ogni foglia contiene un carattere del testo ed il numero di occorrenze mentre i nodi interni contengono solo il numero di occorrenze

E' possibile ora confrontare le prestazioni dei due algoritmi in termini della lunghezza delle parole di codice prodotte e della lunghezza del testo codificato risultante. Tutto questo è mostrato nella seguente tabella:

La quarta e la sesta colonna stanno ad indicare i bit totali necessari per codificare tutte le occorrenze di un carattere, mentre la seconda e la quinta specificano il numero di bit necessari per codificare ciascun carattere. Come si può notare i bit necessari per codificare il testo iniziale sono 89, utilizzando l'algoritmo di Shannon-Fano, e solo 87, utilizzando l'algoritmo di Huffman. Il risparmio in termini di bit nel semplice caso trattato è di circa il 3%, ma, come si può immaginare, nel caso di testi più lunghi il miglioramento può essere notevole. Osserviamo che i codici generati dall'algoritmo di Shannon-Fano e dall'algoritmo di Huffman sono codici prefissi.