L'entropia spiegata
Nel 1948 un ingegnere dei Bell Labs, Claude Shannon, si pose una domanda che nessuno aveva mai formulato con precisione: quanta informazione contiene un messaggio? La sua risposta fu un numero, misurato in bit, che non dipende da che cosa significa un messaggio ma da quanto è sorprendente. Quel numero, l'entropia, fissa i limiti di ogni programma di compressione, di ogni collegamento di rete e di ogni dispositivo di memoria, e spiega perché alcuni testi si riducono a una frazione della loro dimensione mentre altri non si lasciano comprimere affatto.
L'informazione è sorpresa
L'intuizione di Shannon fu misurare l'informazione in base a quanto un messaggio è inatteso, non a che cosa significa. Se conosci già la risposta, sentirla non ti dice nulla; se poteva essere una cosa fra mille, ti dice molto. Un messaggio che individua una fra due possibilità ugualmente probabili porta un bit. Una fra quattro richiede due bit, una fra otto tre bit, e in generale una fra N possibilità ugualmente probabili richiede log₂ N bit. Un simbolo che compare con probabilità p porta quindi −log₂ p bit: più è raro, più ti dice.
La formula di Shannon
L'entropia è l'informazione media per simbolo: H = −Σ p log₂ p, sommata su tutti i simboli, ciascuno con la sua probabilità p. Per una moneta equa H vale 1 bit. Per una moneta che dà testa il 90% delle volte vale solo 0,47 bit, perché di solito il risultato non sorprende. L'entropia è massima quando tutti i simboli sono ugualmente probabili, log₂ n bit per n simboli, e nulla quando un simbolo è certo. Shannon scelse il nome su consiglio di John von Neumann, perché la stessa formula compare in fisica, dove l'entropia misura il disordine.
Il limite della compressione
Il teorema della codifica di sorgente di Shannon afferma che nessun codice senza perdita può usare in media meno bit per simbolo dell'entropia della sorgente, e che i codici possono avvicinarsi a essa quanto si vuole. La codifica di Huffman, inventata da David Huffman nel 1952 quando era studente, assegna codici brevi ai simboli frequenti e codici lunghi a quelli rari e arriva a meno di un bit per simbolo dall'entropia; la codifica aritmetica si avvicina ancora di più. L'entropia non è quindi solo una descrizione ma un limite invalicabile: un file di byte casuali, con 8 bit di entropia per byte, non può essere compresso affatto.
Contesto e ridondanza
Le lettere di un testo non sono indipendenti. In inglese dopo Q viene U, dopo un punto una maiuscola, e una parola che inizia con INFORMA quasi certamente prosegue con TION. Tenere conto dei simboli precedenti dà l'entropia condizionata, che è più bassa dell'entropia dei simboli contati uno per uno. La differenza è la ridondanza: la parte del messaggio che si sarebbe potuta prevedere. I programmi di compressione come ZIP, che usa il metodo deflate, trovano le stringhe ripetute e le sostituiscono con brevi riferimenti, e i compressori moderni prevedono ogni simbolo a partire dal suo contesto.
Quanta informazione c'è nell'inglese?
Contando lettera per lettera, con le frequenze dell'inglese, una lettera porta circa 4,1 bit, contro 4,7 per lettere scelte a caso. Nel 1951 Shannon andò oltre: mostrò ad alcune persone l'inizio di un testo e chiese loro di indovinare la lettera successiva, contando quanti tentativi servivano. Dalle loro risposte stimò che l'inglese porta solo da 0,6 a 1,3 bit circa per lettera. In altre parole, circa tre quarti dell'inglese scritto sono ridondanza, ed è per questo che un testo a cui mancano delle lettere di solito si riesce ancora a leggere.
Casualità e password
L'entropia misura anche l'imprevedibilità, da cui dipende la sicurezza. Una chiave o una password scelta in modo uniforme fra N possibilità ha log₂ N bit di entropia, e un attaccante deve provarne in media circa la metà. Una password casuale di 12 lettere prese dalle 26 minuscole ha circa 56 bit; una parola comune ne ha molti meno, per quanto sia lunga. I generatori di numeri casuali si collaudano verificando che il loro output abbia l'entropia piena di una sorgente casuale, e i sistemi operativi raccolgono entropia dal rumore delle temporizzazioni per inizializzarli.
Dove compare l'entropia
L'entropia stabilisce quanti bit servono per una telefonata, una foto o un flusso video, e quanto un modem o un collegamento Wi-Fi può avvicinarsi alla capacità del suo canale. I biologi la usano per misurare l'informazione nel DNA, dove quattro basi possono portare al massimo 2 bit ciascuna, e la diversità di un ecosistema. Nell'apprendimento automatico, gli alberi di decisione scelgono la domanda che riduce di più l'entropia, e la funzione di perdita di entropia incrociata addestra la maggior parte delle reti neurali. I linguisti confrontano le lingue in base alla loro entropia per carattere e per parola.
Esplorala
Apri il calcolatore di entropia per misurare qualsiasi testo per caratteri, parole o byte. Confronta un paragrafo con lettere, bit, cifre e DNA casuali, guarda la sorpresa di ogni simbolo, quanta informazione contiene il testo rispetto alla sua dimensione memorizzata, e come i bit per simbolo scendono man mano che si conosce più contesto, accanto a ciò che ottiene davvero ZIP.
Domande frequenti
Perché l'entropia si misura in bit?
Perché Shannon usò i logaritmi in base 2, così che una scelta sì o no fra due opzioni equivalenti conti come un'unità. Con il logaritmo naturale l'unità è il nat, circa 1,44 bit, e in base 10 l'hartley, circa 3,32 bit; li usano i fisici e alcuni statistici.
Un testo può avere un'entropia maggiore del log₂ del suo alfabeto?
No. Con n simboli diversi l'entropia è al massimo log₂ n bit per simbolo, valore raggiunto solo quando tutti sono ugualmente frequenti. Qualsiasi squilibrio, e qualsiasi prevedibilità dovuta al contesto, la abbassa.
L'entropia della teoria dell'informazione è la stessa della fisica?
Le formule hanno la stessa forma: Boltzmann e Gibbs scrissero l'entropia fisica come una somma sulle probabilità degli stati microscopici di un sistema. Il significato è affine, perché entrambe misurano quanto non si sa, e da allora i fisici hanno dimostrato che cancellare un bit di informazione deve liberare una piccola quantità di calore.
Perché comprimere un file già compresso non serve?
Un buon compressore elimina gran parte della ridondanza, quindi il suo output è quasi casuale, con quasi 8 bit di entropia per byte. Non resta nulla da eliminare, e comprimerlo di nuovo di solito lo rende un po' più grande a causa del sovraccarico del compressore stesso.
Pronto a provarlo?
Apri PictorX nel tuo browser: nessuna installazione, nessuna carta di credito richiesta per iniziare.
Apri il calcolatore di entropia