Entropie uitgelegd
In 1948 stelde een ingenieur bij Bell Labs, Claude Shannon, een vraag die nog niemand precies had gemaakt: hoeveel informatie bevat een bericht? Zijn antwoord was een getal, gemeten in bits, dat niet afhangt van wat een bericht betekent, maar van hoe verrassend het is. Dat getal, entropie, bepaalt de grenzen van elk compressieprogramma, elke netwerkverbinding en elk opslagmedium, en het verklaart waarom sommige teksten krimpen tot een fractie van hun grootte terwijl andere helemaal niet kleiner te krijgen zijn.
Informatie is verrassing
Het inzicht van Shannon was om informatie te meten naar hoe onverwacht een bericht is, niet naar wat het betekent. Als je het antwoord al weet, vertelt het je niets; als het één van duizend dingen had kunnen zijn, vertelt het je veel. Een bericht dat één van twee even waarschijnlijke mogelijkheden aanwijst, draagt één bit. Eén van vier kost twee bits, één van acht drie bits, en in het algemeen kost één van N even waarschijnlijke mogelijkheden log₂ N bits. Een symbool dat voorkomt met waarschijnlijkheid p draagt dus −log₂ p bits: hoe zeldzamer het is, hoe meer het je vertelt.
De formule van Shannon
Entropie is de gemiddelde informatie per symbool: H = −Σ p log₂ p, opgeteld over elk symbool met zijn waarschijnlijkheid p. Voor een eerlijke munt is H 1 bit. Voor een munt die in 90% van de gevallen op kop valt, is het maar 0,47 bits, omdat de uitkomst meestal geen verrassing is. Entropie is het grootst als alle symbolen even waarschijnlijk zijn, log₂ n bits voor n symbolen, en nul als één symbool zeker is. Shannon koos de naam op advies van John von Neumann, omdat dezelfde formule voorkomt in de natuurkunde, waar entropie wanorde meet.
De grens van compressie
Het broncoderingstheorema van Shannon zegt dat geen verliesvrije code gemiddeld minder bits per symbool kan gebruiken dan de entropie van de bron, en dat codes er zo dicht bij kunnen komen als je wilt. Huffmancodering, in 1952 als student uitgevonden door David Huffman, geeft veelvoorkomende symbolen korte codes en zeldzame lange codes en komt tot op één bit per symbool bij de entropie; aritmetische codering komt nog dichterbij. Entropie is dus niet alleen een beschrijving maar een harde grens: een bestand met willekeurige bytes, met 8 bits entropie per byte, is helemaal niet te comprimeren.
Context en redundantie
Letters in een tekst zijn niet onafhankelijk. In het Engels komt na Q een U, na een punt een hoofdletter, en een Engels woord dat begint met INFORMA gaat vrijwel zeker verder met TION. Als je de vorige symbolen meerekent, krijg je de voorwaardelijke entropie, die lager is dan de entropie van de symbolen die één voor één worden geteld. Het verschil is redundantie: het deel van het bericht dat voorspeld had kunnen worden. Compressieprogramma's zoals ZIP, dat de deflate-methode gebruikt, vinden herhaalde reeksen en vervangen die door korte verwijzingen, en moderne compressors voorspellen elk symbool uit zijn context.
Hoeveel informatie zit er in het Engels?
Letter voor letter geteld, met de frequenties van het Engels, draagt een letter ongeveer 4,1 bits, tegen 4,7 voor willekeurig gekozen letters. In 1951 ging Shannon verder: hij liet mensen het begin van een tekst zien, vroeg hun de volgende letter te raden en telde hoeveel pogingen ze nodig hadden. Uit hun antwoorden schatte hij dat Engels maar ongeveer 0,6 tot 1,3 bits per letter draagt. Met andere woorden: ongeveer drie kwart van geschreven Engels is redundantie, en daarom is een tekst waarin letters ontbreken meestal nog te lezen.
Willekeur en wachtwoorden
Entropie meet ook onvoorspelbaarheid, en daar hangt beveiliging van af. Een sleutel of wachtwoord dat uniform uit N mogelijkheden wordt gekozen, heeft log₂ N bits entropie, en een aanvaller moet er gemiddeld ongeveer de helft van proberen. Een willekeurig wachtwoord van 12 letters uit de 26 kleine letters heeft ongeveer 56 bits; een gangbaar woord heeft er veel minder, hoe lang het ook is. Toevalsgeneratoren worden getest door te controleren of hun uitvoer de volledige entropie van een willekeurige bron heeft, en besturingssystemen verzamelen entropie uit ruis in tijdmetingen om ze te initialiseren.
Waar entropie opduikt
Entropie bepaalt hoeveel bits een telefoongesprek, een foto of een videostream nodig heeft, en hoe dicht een modem of wifiverbinding bij de capaciteit van zijn kanaal kan komen. Biologen gebruiken haar om de informatie in DNA te meten, waar vier basen elk hoogstens 2 bits kunnen dragen, en de diversiteit van een ecosysteem. In machine learning kiezen beslisbomen de vraag die de entropie het meest verlaagt, en de meeste neurale netwerken worden getraind met kruisentropie als verliesfunctie. Taalkundigen vergelijken talen op hun entropie per teken en per woord.
Probeer het zelf
Open de entropiecalculator om elke tekst te meten per teken, woord of byte. Vergelijk een alinea met willekeurige letters, bits, cijfers en DNA, bekijk de verrassing van elk symbool, hoeveel informatie de tekst bevat tegenover zijn opgeslagen grootte, en hoe het aantal bits per symbool daalt naarmate meer context bekend is, naast wat ZIP werkelijk bereikt.
Veelgestelde vragen
Waarom wordt entropie gemeten in bits?
Omdat Shannon logaritmen met grondtal 2 gebruikte, zodat één ja-neekeuze tussen gelijke opties als één eenheid telt. Met de natuurlijke logaritme is de eenheid de nat, ongeveer 1,44 bits, en met grondtal 10 de hartley, ongeveer 3,32 bits; natuurkundigen en sommige statistici gebruiken die.
Kan een tekst meer entropie hebben dan log₂ van zijn alfabet?
Nee. Met n verschillende symbolen is de entropie hoogstens log₂ n bits per symbool, en dat alleen als ze allemaal even vaak voorkomen. Elke onbalans, en elke voorspelbaarheid uit context, verlaagt haar.
Is entropie in de informatietheorie hetzelfde als in de natuurkunde?
De formules hebben dezelfde vorm: Boltzmann en Gibbs schreven de fysische entropie als een som over de waarschijnlijkheden van de microscopische toestanden van een systeem. De betekenis is verwant, want beide meten hoeveel je niet weet, en natuurkundigen hebben sindsdien aangetoond dat het wissen van één bit informatie een kleine hoeveelheid warmte moet vrijmaken.
Waarom helpt het niet om een gecomprimeerd bestand nog eens te comprimeren?
Een goede compressor verwijdert het grootste deel van de redundantie, dus zijn uitvoer is bijna willekeurig, met bijna 8 bits entropie per byte. Er valt niets meer te verwijderen, en opnieuw comprimeren maakt het bestand meestal iets groter door de eigen overhead van de compressor.
Klaar om het te proberen?
Open PictorX in je browser - geen installatie, geen creditcard nodig om te starten.
Open de entropiecalculator