Waarom de Hebzuchtige Strategie Optimaal Is
Het Huffman-algoritme is een hebzuchtig algoritme: bij elke stap maakt het de lokaal optimale keuze (merge de twee goedkoopste knooppunten) zonder vooruit te kijken. Hebzuchtige algoritmen zijn niet altijd globaal optimaal — maar hier zijn ze dat wel.
Het Optimaliteitsargument
Stel dat een code C minimale gemiddelde lengte L heeft. Beschouw de twee symbolen met de laagste waarschijnlijkheid, zeg p_a en p_b. In elke optimale code moeten deze twee symbolen als broer-zusknooppunten op het diepste niveau van de boom voorkomen. Waarom?
Als ze geen gemeenschappelijke ouder hadden, zou je het diepere symbool kunnen ruilen voor een kortere code — wat L vermindert. Daarom moeten de diepste bladeren de minst waarschijnlijke symbolen zijn.
Nu, als je a en b combineert in een metasymbool ab (met p_ab = p_a + p_b), is elke optimale code voor het gereduceerde alfabet minus één symbool precies de Huffman-code op het gereduceerde probleem. Inductie voltooit het argument.
Geometrische Weergave
Het Huffman-algoritme construeert de binaire boom van beneden naar boven, waarbij de minst waarschijnlijke symbolen op de grootste diepte worden geplaatst. Dit minimaliseert Σ p_i · depth(i) = L.
Een equivalent standpunt: je wijst labels toe aan boombladen om de gewogen padlengte te minimaliseren, waarbij het gewicht van elk blad zijn waarschijnlijkheid is.
De Hebzuchtige Stappen Uitvoeren
Waarschijnlijkheden: p(A)=0,4, p(B)=0,3, p(C)=0,2, p(D)=0,1. Som = 1,0 ✓
Stap 1: Laagste twee: C(0,2), D(0,1). Merge → CD(0,3). Lijst: A(0,4), B(0,3), CD(0,3).
Stap 2: Laagste twee: B(0,3), CD(0,3) (gelijkspel — beide geldig). Merge → BCD(0,6). Lijst: A(0,4), BCD(0,6).
Stap 3: Merge A(0,4), BCD(0,6) → root(1,0). Ken A=0, BCD=1 toe.
Achterwaarts: BCD → B=10 (l=2), CD=11 → C=110 (l=3), D=111 (l=3).
L = 0,4·1 + 0,3·2 + 0,2·3 + 0,1·3 = 0,4+0,6+0,6+0,3 = 1,9 bits.
Variantie van Codelengdes
Twee Huffman-codes kunnen dezelfde L bereiken maar verschillende verdelingen van codelengdes hebben. De variantie van codelengdes meet deze spreiding:
Var(l) = E[l²] − (E[l])²
waarbij E[l] = L (gemiddelde codelengde) en E[l²] = Σ p_i · l_i².
Waarom variantie belangrijk is:
1. Buffervereisten. Bij real-time decodering neemt elk symbool een variabel aantal bits in beslag. Hoge variantie betekent dat sommige symbolen veel bits nemen — je hebt een grotere invoerbuffer nodig om altijd een volledig symbool te kunnen lezen.
2. Decoderingslatentie. Codes met hoge variantie hebben lange worst-case decoderingspaden. Codes met lage variantie (breed) begrenzen het worst-case tighter.
3. Robuustheid. Een verloren bit in een code met hoge variantie veroorzaakt meer synchronisatieschade omdat lange codewoorden volledig opnieuw moeten worden gelezen.
Aanbeveling van Hamming: wanneer meerdere geldige Huffman-codes bestaan (tie-breaking-keuzes), geef de voorkeur aan degene met lagere variantie — de brede boom.
Variantie voor Twee Bomen Berekenen
Met p(A)=0,4, p(B)=0,3, p(C)=0,2, p(D)=0,1 en de code A=0, B=10, C=110, D=111:
E[l] = L = 1,9
E[l²] = 0,4·1² + 0,3·2² + 0,2·3² + 0,1·3² = 0,4+1,2+1,8+0,9 = 4,3
Var = 4,3 − 1,9² = 4,3 − 3,61 = 0,69
3-Symbool Huffman-code van Begin tot Eind
Een volledig voorbeeld van begin tot eind: bouw Huffman-code, bereken L, bereken H, verifieer L ≥ H, bereken Var.
Bron: p(X)=0,6, p(Y)=0,3, p(Z)=0,1.
Huffman-constructie:
Stap 1: Gesorteerd: X(0,6), Y(0,3), Z(0,1). Laagste twee: Y(0,3), Z(0,1).
Merge → YZ(0,4). Lijst: X(0,6), YZ(0,4).
Stap 2: Merge X(0,6), YZ(0,4) → root(1,0). Ken X=0, YZ=1 toe.
YZ → Y=10, Z=11.
Code: X=0 (l=1), Y=10 (l=2), Z=11 (l=2).
L = 0,6·1 + 0,3·2 + 0,1·2 = 0,6 + 0,6 + 0,2 = 1,4 bits.
Entropie: H = −0,6·log₂(0,6) − 0,3·log₂(0,3) − 0,1·log₂(0,1)
log₂(0,6) ≈ −0,737, log₂(0,3) ≈ −1,737, log₂(0,1) ≈ −3,322
H = 0,6·0,737 + 0,3·1,737 + 0,1·3,322 = 0,442 + 0,521 + 0,332 = 1,295 bits.
L = 1,4 ≥ H = 1,295 ✓. L/H = 1,4/1,295 ≈ 1,081. 8,1% boven entropie.
Variantie: E[l²] = 0,6·1 + 0,3·4 + 0,1·4 = 0,6+1,2+0,4 = 2,2. Var = 2,2 − 1,4² = 2,2 − 1,96 = 0,24.
Jouw Beurt: Een Volledige Pijplijn
log₂ waarden ter referentie: log₂(0,5)=−1,000, log₂(0,25)=−2,000, log₂(0,125)=−3,000, log₂(0,375)≈−1,415, log₂(0,625)≈−0,678.