Capacità — 14. L'algoritmo di Shannon-Fano

“L'altra volta avevo detto che sappiamo quale sia il massimo teorico che possiamo raggiungere comprimendo dei dati, ma non sappiamo come raggiungerlo”.

“Sì”.

“Beh, non è proprio così”.

“Ma come?”.

“Eh, bisogna capire bene di cosa stiamo parlando”.

“Come al solito”.

“Esatto. C'è un teorema che dice quale sarà la massima entropia che puoi ottenere, ma non ti dice quale codifica devi usare per ottenerla”.

“Ok”.

“Poi esistono dei metodi, degli algoritmi, che ti permettono di analizzare un flusso di dati e creare una codifica che possa cercare di avvicinarsi il più possibile a quel punto”.

“Quando un Vero Matematico comincia a usare frasi del genere, c'è da preoccuparsi”.

“Eh, lo so. Bisogna vedere il contesto: stiamo approssimando un flusso di dati in tempo reale, o possiamo dare un'occhiata a tutti i dati in anticipo? Dobbiamo tenere conto del fatto che ci possono essere errori che vanno corretti, oppure no? Insomma, come al solito ci sono tante sottigliezze che fanno la differenza”.

“Sgrunt”.

“Quindi, prendiamo un caso molto semplice, presentato anche da Shannon in due modi leggermente diversi. Uno ideato da lui, il secondo ideato indipendentemente da Fano (Shannon ha gentilmente specificato quell'indipendentemente, rendendo onore a Fano)”.

“Fair Play Matematico”.

“Già. Questo metodo ha bisogno di conoscere in anticipo le probabilità di ogni simbolo trasmesso”.

“E non è sempre così?”.

“Beh, no. Immagina di dover comprimere la Divina Commedia: possiedi il testo, lo analizzi, vedi le frequenze delle singole lettere. Immagina invece di dover comprimere un discorso trascritto in tempo reale: non puoi analizzare il testo, perché non è ancora stato scritto. Puoi però utilizzare le tabelle di frequenza relative alla lingua in cui è pronunciato quel discorso. Immagina infine di dover comprimere le cifre di pi greco che ti vengono calcolate al volo da un computer: come si fa a fare delle previsioni?”.

“Eh, mi sa che in quel caso sia un problema non da poco”.

“Infatti. Parliamo quindi del caso semplice: conosciamo le frequenze dei vari caratteri. Ti faccio un esempio super facile che abbiamo già visto tempo fa”.

“Benissimo”.

“Supponiamo che ci siano quattro caratteri, A, B, C e D. Supponiamo che le probabilità, cioè le frequenze relative, siano le seguenti:”.

A: 1/2
B: 1/4
C: 1/8
D: 1/8

“Ok, finora è chiaro, pare semplice”.

“Bene. I caratteri devono essere ordinati dal più probabile al meno probabile, come ho fatto”.

“Ok, lo sono”.

“Ora bisogna dividerli in due gruppi, in modo tale che la somma delle probabilità del primo gruppo sia uguale a quella del secondo”.

“Beh, qui è facile: i due gruppi sono {A} e {B, C, D}”.

“Esatto. Associamo il numero 0 al primo gruppo e il numero 1 al secondo”.

A:       0
B, C, D: 1

“Fin qui ci sono”.

“Bene, l'algoritmo è questo: si ripete di nuovo lo stesso procedimento per tutti i gruppi che non siano composti da un unico elemento”.

“Ah. Allora dovrei spezzare il secondo gruppo”.

“Sì”.

“Direi che si debba spezzare dopo B, dato che B ha probabilità 1/4 e {C, D} ha la stessa probabilità. Ora come faccio con l'associazione con 0 e 1?”.

“Aggiungi il nuovo numero al vecchio, così:”.

A:    0
B:    10
C, D: 11

“Ah, ecco. Ora devo spezzare il gruppo {C, D} e aggiungere un'altra cifra?”.

“Esatto. Vedi che le codifiche più lunghe sono associate ai simboli meno probabili, e le codifiche più corte a quelli più probabili”.

“Concludo, allora. Dovrei avere una tabella del genere:”.

A: 0
B: 10
C: 110
D: 111

“Ottimo”.

“E quindi è finito? Mi basta sostituire ai simboli quelle codifiche?”.

“Esatto”.

“Ma così risulta una codifica più lunga di quella precedente, come facciamo a dire che abbiamo compresso i dati?”.

“No, in realtà no, quella codifica che abbiamo creato è in bit, in cifre binarie, mentre i simboli A, B, C e D vanno pure loro codificati in questo modo”.

“Uhm, non mi è ben chiaro”.

“Immagina di voler codificare la stringa AAAABBCD in binario, come fai?”.

“Ah, devo usare il codice ASCII?”.

“Se usi quello, allora è evidente che stiamo comprimendo: quella stringa è formata da 8 caratteri, ogni carattere sta in un byte, totale 64 bit. Con l'algoritmo di Shannon-Fano invece diventa 00001010110111, solo 14 bit”.

“Uh, comincio a capire. Beh, la codifica ASCII è esagerata per solo quattro simboli, in effetti”.

“Esattamente. Ma se usi una codifica a lunghezza costante, analoga alla codifica ASCII, per quei quattro simboli, potresti fare una cosa del genere:”.

A: 00
B: 01
C: 10
D: 11

“Giusto, fammi fare i conti: la stringa AAAABBCD diventerebbe 0000000001011011, 16 bit”.

“Esatto: di 2 bit più lunga”.

“E non si può fare di meglio della codifica di Shannon-Fano?”.

“Facciamo i conti: quanto è la sua entropia?”.

“Oh, uhm. Per ogni lettera devo moltiplicare la probabilità per il logaritmo del suo reciproco, e sommare tutto”.

“Sì, la formula dice quello. Ecco il conto:”.

(1/2) log₂(2) + (1/4) log₂(4) + (1/8) log₂(8) + (1/8) log₂(8) = 1/2 + 2/4 + 3/8 + 3/8 = 7/4

“E questo risultato come lo interpreto?”.

“Ci dice che hai bisogno di 7/4 di bit per ogni carattere, e dato che tu hai trasmesso 8 caratteri…”.

“Ho bisogno di 14 bit! E in effetti ne ho usati proprio 14, bello. Non potevo fare di meglio”.

“Sì, questo era un esempio facile facile, con dei numeri belli, senza approssimazioni, ma ci fa capire come funziona l'idea”.

“Molto bene. Però, ho un dubbio”.

“Quale?”.

“Nella codifica simil-ASCII con due bit per carattere, io so dove finisce la codifica di un carattere e dove inizia quella del successivo, ma nella codifica di Shannon-Fano, che è a lunghezza variabile, come faccio?”.

“Ottima domanda. L'idea geniale di quel tipo di codifica è che essa è un codice prefisso, come dicono gli esperti”.

“Cosa significa?”.

“Significa che nessuna stringa di bit è anche prefisso di qualche altra stringa”.

“Ripeto la domanda: cosa significa?”.

“Guarda la tabella: A è associata a 0. C'è qualche altra lettera che ha un codice che incomincia con 0?”.

“No”.

“Quindi se in una stringa incontri uno 0, sai che hai trovato una A e che da quel punto comincia un altro simbolo”.

“Ah”.

“Invece, se trovi un 1 sai che devi andare avanti. Se trovi 10, sai che lì finisce il simbolo, perché 10 non compare da nessuna parte se non nella codifica di B”.

“Ma è davvero geniale! Se trovo 11, so che devo andare avanti e vedere se ho 110 oppure 111”.

“Proprio così. Questa codifica non è solo un'idea teorica usata per dimostrare qualcosa, ma viene usata davvero nella realtà. Nel metodo IMPLODE della compressione ZIP, per la precisione”.

“Ah, ma guarda, una parte di matematica che serve davvero a qualcosa”.

“Incredibile, eh?”.