Capacità — 13. Compressione

“La volta scorsa abbiamo visto cosa significa raggiungere il punto di massima entropia”.

“Sì, è quando tutto è inaspettato, equiprobabile, non puoi scommettere su niente”.

“Esatto, sì. Ma nei sistemi reali non sempre si raggiunge la massima entropia, a volte c'è qualche informazione più probabile”.

“Certo”.

“Per esempio, quando lanci due dadi e ne fai la somma”.

“Vero: non tutti i risultati sono equiprobabili. È più difficile fare 2 o 12 che non 7”.

“E quindi l'informazione sull'uscita del 7 porta con sé meno informazione rispetto a quella che ti dice che è uscito 12”.

“Se vogliamo metterla in questi termini, sì. Ma ancora non mi è del tutto chiaro il significato di questa affermazione”.

“Questo perché il concetto di entropia è difficile da digerire. Ma analizziamo l'esempio dei dadi: lanciando una coppia di dadi si possono avere 36 possibili risultati”.

“Questo se distingui il primo dal secondo, però”.

“Certo. Per ora distinguiamo tutto, poi mettiamo insieme. Per esempio, la somma 2 la puoi ottenere in un solo modo”.

“Quando il primo dado mi dà 1 e il secondo dado anche”.

“Sì. Invece 7 lo puoi ottenere in molti modi”.

“Già. Faccio uno schema:”.

 2: (1,1)
 3: (1,2), (2,1)
 4: (1,3), (2,2), (3,1)
 5: (1,4), (2,3), (3,2), (4,1)
 6: (1,5), (2,4), (3,3), (4,2), (5,1)
 7: (1,6), (2,5), (3,4), (4,3), (5,2), (6,1)
 8: (2,6), (3,5), (4,4), (5,3), (6,2)
 9: (3,6), (4,5), (5,4), (6,3)
10: (4,6), (5,5), (6,4)
11: (5,6), (6,5)
12: (6,6)

“Ottimo, guarda come si vede bene la struttura”.

“Vedo. Una volta su 36 ottengo 2, 6 volte su 36 ottengo 7”.

“E quindi l'uscita di un 7 ti stupirebbe di meno dell'uscita di un 2”.

“Sì, il 7 me l'aspetto di più.”.

“Questa è la tabella delle frequenze, e delle probabilità di uscita di ogni valore”.

 2: 1 — 0.028
 3: 2 — 0.056
 4: 3 — 0.083
 5: 4 — 0.111
 6: 5 — 0.139
 7: 6 — 0.167
 8: 5 — 0.139
 9: 4 — 0.111
10: 3 — 0.083
11: 2 — 0.056
12: 1 — 0.028

“Molto bene. E adesso?”.

“Adesso calcoliamo l'entropia: ricordi che per ogni valore bisogna calcolare il prodotto tra la probabilità di uscita e il logaritmo in base 2 del reciproco”.

“plog₂(1/p), ricordo. Faccio la tabella:”.

 2: 0.144
 3: 0.232
 4: 0.299
 5: 0.352
 6: 0.396
 7: 0.431
 8: 0.396
 9: 0.352
10: 0.299
11: 0.232
12: 0.144

“Bene, ora somma tutto”.

“Risulta 3.274. Cosa significa?”.

“Significa che, alla lunga, ti bastano 2^3.274 domande per sapere quale valore è uscito. O, in alternativa, la somma di due dadi può rappresentare 2^3.274 = 9.676 valori equiprobabili”.

“Uhm, vabbé”.

“Mettiamola così: i possibili valori che può assumere la somma di due dadi sono 11, ma sono troppi. Possiamo usarne meno, ma non per indovinare che valore è uscito una volta. Immagina di avere una sequenza molto lunga di lanci, diciamo un milione, e di doverla trasmettere. Come potresti fare?”.

“Beh, faccio un elenco e li trasmetto, no?”.

“Vorrei una descrizione più precisa: come è fatto l'elenco?”.

“Una roba del genere: 2, 5, 6, 12, 9, eccetera”.

“Così c'è un gran spreco di roba, però”.

“In che senso?”.

“Hai usato una virgola per separare ogni numero, e anche uno spazio”.

“Ah”.

“Puoi risparmiare spazio, poi la codifica decimale è esagerata”.

“Mh. Ho undici simboli, in qualche modo li devo scrivere”.

“Già, ma te ne bastano 11, non ne servono di più. Per esempio, potresti usare la base 11, e usare questi simboli: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A”.

“Risparmio un carattere per il 10, l'11 e il 12”.

“Non solo, risparmi anche le virgole e gli spazi. Se scrivi una cosa tipo questa, 71264A03191A26A, non hai bisogno di separare le cifre”.

“Giusto. Ma allora potrei fare di meglio: questi caratteri vengono memorizzati dal computer in modo da sprecare spazio, perché uso un byte per ognuno di essi”.

“Forse anche di più, dipende dalla codifica. Una volta si usava la codifica ASCII a 7 bit, poi siamo passati a 8, poi con l'UNICODE possiamo arrivare a 32 bit”.

“Che spreco. Potrei allora creare una codifica apposta, e rimanere sui 7 bit”.

“Ma sono ancora tanti, no? Con 7 bit si possono codificare 128 simboli, a te ne bastano molti meno”.

“Fino a quanto posso scendere, quindi?”.

“Fino a una codifica di massima entropia”.

“Ah”.

“Qui sta il bello: la codifica migliore è quella che usa soltanto 9.676 simboli, e la puoi ottenere con 3.274 bit. Ovviamente questo è un valore teorico, ma più lunga è la sequenza che vuoi codificare, più vicino puoi arrivare a questo numero”.

“Oh, bello. Ma questo discorso c'entra forse qualcosa con la compressione dei dati?”.

“Certo: ti dice qual è il massimo teorico che puoi raggiungere comprimendo quei dati”.

“Ah. E come si fa a raggiungerlo, in generale? Prendendo una sequenza qualsiasi, voglio dire, non solo la sequenza dei lanci di due dadi”.

“Ah, boh. Il teorema di Shannon ti dice solo che si può fare, non ti dice mica come”.