Code als een Boom
Een prefixvrije code wordt afgebeeld op een binaire boom: de wortel vertegenwoordigt het begin van decodering, linkertakken vertegenwoordigen bit 0, rechtertakken vertegenwoordigen bit 1, en bladeren vertegenwoordigen volledige codewoorden.
De geometrische beperking: elk blad beëindigt een pad van wortel naar blad. Geen blad kan een afstammeling hebben (als het dat deed, zou zijn codewoord een prefix zijn van het codewoord van de afstammeling, waardoor de prefixvrije eigenschap wordt geschonden).
Dit geeft de Kraft-ongelijkheid een geometrische interpretatie:
Elk blad op diepte d 'neemt' een fractie 2^(−d) van de totale boomcapaciteit in beslag. De totale capaciteit van een volledige binaire boom op diepte D is 1. Een prefixvrije code gebruikt bladeren op verschillende dieptes; de Kraft-som meet de totale bezetting.
Kraft-som = 1: volledige code (elk pad eindigt op een blad — perfecte verpakking).
Kraft-som < 1: onvolledige code (enige boomcapaciteit ongebruikt — meer symbolen zouden kunnen worden toegevoegd).
Kraft-som > 1: onmogelijk voor prefixvrije codes (sommige paden zouden een blad moeten delen).
Diepere Bladeren = Langere Codes = Minder Capaciteit
Een blad op diepte 1 gebruikt half van de boomcapaciteit (2^(−1) = 0.5).
Een blad op diepte 3 gebruikt een-achtste (2^(−3) = 0.125).
Een kort codewoord hoog in de boom plaatsen blokkeert al zijn afstammelingen van gebruik — je ruilt één korte code in voor veel mogelijke langere codes.
Een Prefixvrije Boom Bouwen
Beschouw 5 symbolen met lengtes l = {1, 2, 3, 3, 3}. Kraft-som = 2^(−1) + 2^(−2) + 3·2^(−3) = 0.5 + 0.25 + 0.375 = 1.125 > 1.
Dit overschrijdt 1: deze lengtes zijn incompatibel met een prefixvrije code. Ten minste één lengte moet toenemen.
Oplossing: verander l_1 van 1 naar 2. Nieuwe lengtes {2, 2, 3, 3, 3}: Kraft = 2·2^(−2) + 3·2^(−3) = 0.5 + 0.375 = 0.875 < 1. Geldig, maar onvolledig.
Oplossing: verander l_1 van 2 naar 2, voeg l_2 = 3 toe om restcapaciteit te gebruiken. Kraft = 0.875; resterend = 0.125 = 2^(−3): ruimte voor nog één diepte-3 blad.
Waarom Entropie de Codelengtes Beperkt
Kraft's ongelijkheid beperkt code structuur (lengtes moeten in de boom passen). Shannon's entropie beperkt code efficiëntie (gemiddelde lengte kan niet beter zijn dan een theoretische ondergrens).
Optimale codelengtes. Voor een symbool met waarschijnlijkheid p_i is de ideale codelengtes log₂(1/p_i). Zeldzame symbolen verdienen lange codes; frequente symbolen verdienen korte. Dit weerspiegelt de Kraft-gelijkheid: 2^(−l_i) = p_i wanneer l_i = log₂(1/p_i).
Maar log₂(1/p_i) is zelden een geheel getal. Naar boven afronden naar ⌈log₂(1/p_i)⌉ geeft de Huffman-lengte, die H ≤ L < H + 1 voldoet.
Geometrische interpretatie. Zet elk symbool als een punt op de binaire boom op diepte l_i. De Kraft-som meet de totale bladbedekking. Entropie meet de gewogen gemiddelde diepte, gewogen naar waarschijnlijkheid. Shannon's stelling: waarschijnlijkheid-gewogen gemiddelde diepte ≥ waarschijnlijkheid-gewogen informatie-inhoud.
Verificatie van Entropie-Gebonden
Het uitgewerkte voorbeeld: p = [1/2, 1/4, 1/8, 1/8] voor symbolen {A, B, C, D}.
Optimale lengtes: l_A = log₂(2) = 1, l_B = log₂(4) = 2, l_C = log₂(8) = 3, l_D = log₂(8) = 3.
Dit zijn allemaal gehele getallen — een perfecte overeenkomst. Huffman-code: A=0, B=10, C=110, D=111.
L = 0.5·1 + 0.25·2 + 0.125·3 + 0.125·3 = 0.5 + 0.5 + 0.375 + 0.375 = 1.75.
H = 0.5·1 + 0.25·2 + 0.125·3 + 0.125·3 = 1.75. L = H exact: optimale code.
Een Volledig Uitgewerkt Voorbeeld
Volledige pijplijn: gegeven waarschijnlijkheden, bereken entropie, verifieer dat een code aan de grens voldoet.
Bron: p(A)=0.5, p(B)=0.25, p(C)=0.125, p(D)=0.125.
H = 1.75 bits (berekend hierboven).
Een naïeve blokcode: 4 symbolen → 2 bits elk → L = 2.0. Overhead over entropie: 2.0 − 1.75 = 0.25 bits/symbool = 12.5% verspilling.
De variabele-lengtecode bespaart 12.5% vergeleken met vaste lengte. Voor grote berichten is dit aanzienlijk.
Entropiesnelheid van Engels. Shannon schatte dat de entropie van geschreven Engels ongeveer 1.0 tot 1.3 bits per teken bedraagt, ondanks het gebruik van 5-bits ASCII-codes. Die 4:1-verhouding weerspiegelt de enorme redundantie in natuurlijke taal — veel voorkomende letters clusteren, woorden herhalen, grammatica beperkt sequenties.
Compressie Kan Entropie Niet Verslaan
Compressieverhouding: H / (blokcodelengtes). Voor ons voorbeeld: 1.75/2.0 = 0.875 — 87.5% efficiëntie.
Kun je verder comprimeren? Alleen door context te gebruiken: als je paren of drielingen van symbolen samen codeert, kan de gezamenlijke entropie H(X,Y) kleiner zijn dan 2·H(X) vanwege statistische afhankelijkheden. Dit is de uitbreiding van de storingsvrije coderingstelling naar n-grammen.