Entropi förklarad

År 1948 ställde en ingenjör vid Bell Labs, Claude Shannon, en fråga som ingen tidigare hade formulerat exakt: hur mycket information innehåller ett meddelande? Hans svar var ett tal, mätt i bitar, som inte beror på vad ett meddelande betyder utan på hur överraskande det är. Det talet, entropin, sätter gränserna för varje komprimeringsprogram, varje nätverksförbindelse och varje lagringsenhet, och det förklarar varför vissa texter krymper till en bråkdel av sin storlek medan andra inte går att pressa ihop alls.

Staplar med bokstävers sannolikheter som bleknar från vanliga till ovanliga, med entropikurvan som sjunker när mer kontext är känd
Staplar med bokstävers sannolikheter som bleknar från vanliga till ovanliga, med entropikurvan som sjunker när mer kontext är känd

Information är överraskning

Shannons insikt var att mäta information efter hur oväntat ett meddelande är, inte efter vad det betyder. Om du redan vet svaret säger det dig ingenting att höra det; om det kunde ha varit en av tusen saker säger det dig mycket. Ett meddelande som pekar ut en av två lika sannolika möjligheter bär en bit. En av fyra kräver två bitar, en av åtta tre bitar, och i allmänhet kräver en av N lika sannolika möjligheter log₂ N bitar. En symbol som förekommer med sannolikheten p bär därför −log₂ p bitar: ju ovanligare den är, desto mer säger den.

Shannons formel

Entropin är den genomsnittliga informationen per symbol: H = −Σ p log₂ p, summerat över varje symbol med dess sannolikhet p. För ett rättvist mynt är H 1 bit. För ett mynt som visar krona 90 % av gångerna är den bara 0,47 bitar, eftersom utfallet oftast inte är någon överraskning. Entropin är som störst när alla symboler är lika sannolika, log₂ n bitar för n symboler, och noll när en symbol är säker. Shannon valde namnet på inrådan av John von Neumann, eftersom samma formel förekommer i fysiken, där entropi mäter oordning.

Claude Shannon, som 1948 på Bell Labs preciserade hur mycket information ett meddelande innehåller och mätte den i bitar.
Claude Shannon, som 1948 på Bell Labs preciserade hur mycket information ett meddelande innehåller och mätte den i bitar.

Komprimeringens gräns

Shannons källkodningssats säger att ingen förlustfri kod i genomsnitt kan använda färre bitar per symbol än källans entropi, och att koder kan komma hur nära den som helst. Huffmankodning, som David Huffman uppfann 1952 som student, ger vanliga symboler korta koder och ovanliga långa, och hamnar inom en bit per symbol från entropin; aritmetisk kodning kommer ännu närmare. Entropin är alltså inte bara en beskrivning utan en hård gräns: en fil med slumpmässiga byte, med 8 bitar entropi per byte, går inte att komprimera alls.

David Huffman, fotograferad som professor vid UC Santa Cruz. Som doktorand vid MIT hittade han 1951 sin optimala kod i en uppsats för Robert Fanos kurs.
David Huffman, fotograferad som professor vid UC Santa Cruz. Som doktorand vid MIT hittade han 1951 sin optimala kod i en uppsats för Robert Fanos kurs.

Kontext och redundans

Bokstäverna i en text är inte oberoende. På engelska kommer U efter Q, efter en punkt kommer en versal, och ett ord som börjar med INFORMA fortsätter nästan säkert med TION. Om man tar hänsyn till de föregående symbolerna får man den betingade entropin, som är lägre än entropin för symbolerna räknade en och en. Skillnaden är redundans: den del av meddelandet som hade kunnat förutsägas. Komprimeringsprogram som ZIP, som använder metoden deflate, hittar upprepade strängar och ersätter dem med korta hänvisningar, och moderna komprimeringsprogram förutsäger varje symbol utifrån dess kontext.

Hur mycket information finns i engelska?

Räknat bokstav för bokstav, med engelskans frekvenser, bär en bokstav ungefär 4,1 bitar, mot 4,7 för slumpmässigt valda bokstäver. År 1951 gick Shannon längre: han visade människor början av en text och bad dem gissa nästa bokstav, och räknade hur många gissningar de behövde. Utifrån deras svar uppskattade han att engelska bara bär ungefär 0,6 till 1,3 bitar per bokstav. Med andra ord är ungefär tre fjärdedelar av skriven engelska redundans, och därför går en text där bokstäver saknas oftast ändå att läsa.

Slump och lösenord

Entropi mäter också oförutsägbarhet, och det är den som säkerhet hänger på. En nyckel eller ett lösenord som väljs likformigt bland N möjligheter har log₂ N bitar entropi, och en angripare måste i genomsnitt pröva ungefär hälften av dem. Ett slumpmässigt lösenord på 12 bokstäver ur de 26 gemena bokstäverna a–z har ungefär 56 bitar; ett vanligt ord har betydligt färre, hur långt det än är. Slumptalsgeneratorer testas genom att man kontrollerar att deras utdata har den fulla entropin hos en slumpkälla, och operativsystem samlar entropi från tidsbrus för att initiera dem.

Där entropi dyker upp

Entropi avgör hur många bitar ett telefonsamtal, ett foto eller en videoström behöver, och hur nära ett modem eller en wifi-förbindelse kan komma kanalens kapacitet. Biologer använder den för att mäta informationen i DNA, där fyra baser kan bära högst 2 bitar var, och mångfalden i ett ekosystem. Inom maskininlärning väljer beslutsträd den fråga som minskar entropin mest, och förlustfunktionen korsentropi tränar de flesta neurala nätverk. Lingvister jämför språk efter deras entropi per tecken och per ord.

Utforska

Öppna entropikalkylatorn för att mäta valfri text efter tecken, ord eller byte. Jämför ett stycke med slumpmässiga bokstäver, bitar, siffror och DNA, se varje symbols överraskning, hur mycket information texten innehåller jämfört med sin lagrade storlek och hur antalet bitar per symbol sjunker när mer kontext är känd, bredvid vad ZIP faktiskt åstadkommer.

Ofta ställda frågor

Varför mäts entropi i bitar?

Därför att Shannon använde logaritmer med basen 2, så att ett ja-eller-nej-val mellan lika alternativ räknas som en enhet. Med den naturliga logaritmen är enheten nat, ungefär 1,44 bitar, och med basen 10 hartley, ungefär 3,32 bitar; de används av fysiker och en del statistiker.

Kan en text ha mer entropi än log₂ av sitt alfabet?

Nej. Med n olika symboler är entropin högst log₂ n bitar per symbol, vilket bara nås när alla är lika vanliga. Varje obalans, och varje förutsägbarhet från kontexten, sänker den.

Är entropi i informationsteorin samma sak som i fysiken?

Formlerna har samma form: Boltzmann och Gibbs skrev den fysikaliska entropin som en summa över sannolikheterna för ett systems mikroskopiska tillstånd. Betydelsen är besläktad, eftersom båda mäter hur mycket man inte vet, och fysiker har sedan dess visat att det måste frigöras en liten mängd värme när en bit information raderas.

Varför hjälper det inte att komprimera en komprimerad fil?

En bra komprimerare tar bort det mesta av redundansen, så dess utdata är nära slumpmässiga, med nästan 8 bitar entropi per byte. Det finns inget kvar att ta bort, och att komprimera igen gör oftast filen något större, på grund av den extra information som komprimeraren själv lägger till.

Redo att prova det?

Öppna PictorX i din webbläsare - ingen installation, inget kreditkort krävs för att starta.

Öppna entropikalkylatorn