Hoe Huffman de optimale code bouwt
Hamming presenteert Huffman-codering als een hebzuchtig algoritme dat een code met minimale gemiddelde lengte zonder prefix construeert. Het kernidee: bouw de boom van beneden naar boven, en voeg altijd de twee minst waarschijnlijke symbolen samen.
De voorwaartse pas (Bouwen)
1. Sorteer alle symbolen op waarschijnlijkheid, van hoog naar laag.
2. Neem de twee laagst waarschijnlijke symbolen. Combineer ze in een nieuw meta-symbool met waarschijnlijkheid = som van de twee.
3. Plaats het meta-symbool op zijn gesorteerde positie.
4. Herhaal totdat slechts twee symbolen overblijven.
5. Wijs 0 en 1 toe aan de twee resterende symbolen.
De achterwaartse pas (Codes toewijzen)
Maak de samenvoegingen in omgekeerde volgorde ongedaan: bij elke splitsing ontvangen de twee symbolen die werden samengevoegd dezelfde prefix bits als hun gecombineerde ouder, plus een extra 0 (één kind) of 1 (ander kind). De 0/1 toewijzing is willekeurig — beide zijn geldig.
Waarom dit optimaal is: als enige ander code een kleinere gemiddelde lengte L' zou hebben, zou dezelfde voorwaartse reductie uiteindelijk twee symbolen opleveren met gemiddelde lengte minder dan 1 bit — onmogelijk voor een 2-symbool code. Tegenspraak.
Het algoritme stap voor stap uitvoeren
Voorbeeld uit Hamming: vier symbolen A, B, C, D met p(A)=0,5, p(B)=0,25, p(C)=0,125, p(D)=0,125.
Voorwaartse pas:
Stap 1: Gesorteerd: A(0,5), B(0,25), C(0,125), D(0,125). De twee laagsten: C, D.
Stap 2: Voeg CD samen met p=0,25. Nieuwe lijst: A(0,5), B(0,25), CD(0,25).
Stap 3: De twee laagsten: B(0,25), CD(0,25). Voeg BCD samen met p=0,5.
Stap 4: Twee symbolen resten: A(0,5), BCD(0,5). Wijs A=0, BCD=1 toe.
Achterwaartse pas:
BCD → B krijgt 10, CD krijgt 11. CD → C krijgt 110, D krijgt 111.
Eindcode: A=0 (l=1), B=10 (l=2), C=110 (l=3), D=111 (l=3).
L = 0,5·1 + 0,25·2 + 0,125·3 + 0,125·3 = 1,75 bits.
Meerdere geldige Huffman codes
Hamming merkt twee bronnen van niet-uniekheid op:
1. Willekeurige 0/1 toewijzing. Bij elke splitsing kun je 0 aan elk kind geven. Als je 0 en 1 door het hele proces heen omwisselt, krijg je een andere code met identieke L.
2. Gelijkspel-doorbreking. Wanneer twee knooppunten gelijke waarschijnlijkheid hebben, kan elk 'hoger' worden geplaatst (eerst gecombineerd). Verschillende keuzen kunnen structureel verschillende bomen opleveren — 'lang' vs 'dicht' — met dezelfde L maar verschillende codelengteverspreiding.
Lang vs Dicht
Lange boom (scheef): een symbool op elk diepteniveau (Fibonacci-achtige structuur). Codelengtes variëren sterk: één symbool krijgt een korte code, anderen cascaderen naar langere codes.
Dichte boom (gebalanceerd): symbolen verspreid over diepteniveaus. Codelengtes clusteren dicht bij het gemiddelde. Lagere variantie.
Hamming's aanbeveling: geef, wanneer je de keuze hebt, de voorkeur aan de dichte boom. Dezelfde L, maar kleinere variantie in codelengtes → meer eenduidige decodeertijd → kleinere buffervereisten in realtime applicaties.
Variantie van codelengtes berekenen
Variantie van codelengtes: Var = E[l²] − (E[l])²
Voor de code {A=0 l=1, B=10 l=2, C=110 l=3, D=111 l=3} met p=[0,5, 0,25, 0,125, 0,125]:
E[l] = L = 1,75
E[l²] = 0,5·1² + 0,25·2² + 0,125·3² + 0,125·3² = 0,5 + 1,0 + 1,125 + 1,125 = 3,75
Var = 3,75 − 1,75² = 3,75 − 3,0625 = 0,6875
Een alternatieve dichte code voor gelijk waarschijnlijke symbolen gebruikt alle lengte-2 codes: L=2, Var=0.
Compressiewinsten vs symboolverspreiding
Hamming's regel: Huffman-codering loont alleen wanneer symboolwaarschijnlijkheden aanzienlijk verschillen.
Gelijke waarschijnlijkheden. Als alle 2^k symbolen gelijke waarschijnlijkheid 1/2^k hebben, produceert Huffman een blokcode: elk symbool krijgt lengte k. L = H = k. Geen winst ten opzichte van de eenvoudige blokcode.
Scheefgeziene waarschijnlijkheden. Als één symbool domineert (p >> 1/2^k voor anderen), wijst Huffman het een zeer korte code toe (lengte 1 of 2), wat L drastisch vermindert.
De kommacode (Hamming's term). Wanneer elke waarschijnlijkheid meer dan 2/3 van de resterende totaal overschrijdt, produceert Huffman natuurlijk: p(s1)→0, p(s2)→10, p(s3)→110, ..., tot twee gelijk lange codes aan het eind. Dit is een 'kommacode': de volgende 0 na een reeks 1s werkt als een komma.
Hamming merkt op: compressie in de echte wereld (back-up, bestandsarchivering) kan opslag met meer dan de helft reduceren wanneer de bron scheefgeziene waarschijnlijkheden heeft — Engelse tekst is een priemvoorbeeld.
Huffman vs blokcode: numerieke vergelijking
Hamming's tweede voorbeeld: p(s1)=1/3, p(s2)=1/5, p(s3)=1/6, p(s4)=1/10, p(s5)=1/12, p(s6)=1/20, p(s7)=1/30, p(s8)=1/30.
Blokcode: 8 symbolen → 3 bits elk → L_blok = 3.
Hamming berekent de Huffman code en rapporteert L_Huffman ≈ 2,58 bits.
Besparing: (3 − 2,58)/3 ≈ 14% compressie ten opzichte van blokcoden.
Wanneer symboolwaarschijnlijkheden sterk verschillen (1/3 vs 1/30 hier, een 10:1 verhouding), loont codes met variabele lengte aanzienlijk.
Zelf compilerende programma's
Hamming sluit hoofdstuk 11 af met een opvallend idee: een Huffman encoder kan zichzelf coderen. De decoderingsboom (die de decoder vertelt hoe het gecomprimeerde bericht leest) wordt samen met de gecomprimeerde gegevens verzonden. De ontvanger hoeft geen voorafgaande kennis van de code te hebben.
De encoder: steekproef de gegevens, schat waarschijnlijkheden, construeer de Huffman code, codeer de decoderingsboom als header, codeer dan de gegevens.
De decoder: lees de header om de boom te reconstrueren, decodeer dan de gegevens met behulp ervan.
Hamming's punt: deze gehele pijplijn kan als bibliotheekfunctie zonder menselijke betrokkenheid draaien. Je roept het aan, het comprimeert en decomposeert automatisch. Moderne archiveringsformaten (ZIP, gzip, bzip2) implementeren exact dit patroon.
Het diepere principe: de intelligentie zit in het algoritme, niet in een vaste codetabel. Het algoritme past zich aan aan welke gegevens het ook ontvangt. Dit is het patroon dat Hamming in alle grote technische systemen ziet: aanpassingsvermogen ingebouwd, niet vastgeplakt.