Varför den griga strategin är optimal
Huffman-algoritmen är en girig algoritm: vid varje steg gör den det lokalt optimala valet (sammanslå de två billigaste noderna) utan att titta framåt. Griga algoritmer är inte alltid globalt optimala — men här är de.
Optimalitetsargumentet
Antag att en kod C har minsta medelängd L. Betrakta de två symbolerna med lägst sannolikhet, säg p_a och p_b. I någon optimal kod måste dessa två symboler visas som bladsyskon på träets djupaste nivå. Varför?
Om de inte delade en förälder, kunde du byta den djupare symbolen mot en kortare kod — reducerar L. Därför måste de djupaste bladen vara de minst sannolika symbolerna.
Nu, om du kombinerar a och b i en metasymbol ab (med p_ab = p_a + p_b), är någon optimal kod för det reducerade alfabetet minus en symbol exakt Huffman-koden på det reducerade problemet. Induktion avslutar argumentet.
Geometrisk vy
Huffman-algoritmen konstruerar det binära trädet nedifrån och upp, och placerar de minst sannolika symbolerna på största djupet. Detta minimerar Σ p_i · depth(i) = L.
En motsvarande vy: du tilldelar etiketter till trädblad för att minimera den vägda väglängden, där varje blads vikt är dess sannolikhet.
Genomförande av de griga stegen
Sannolikheter: p(A)=0.4, p(B)=0.3, p(C)=0.2, p(D)=0.1. Summa = 1.0 ✓
Steg 1: Två lägsta: C(0.2), D(0.1). Sammanslå → CD(0.3). Lista: A(0.4), B(0.3), CD(0.3).
Steg 2: Två lägsta: B(0.3), CD(0.3) (oavgjort — båda giltiga). Sammanslå → BCD(0.6). Lista: A(0.4), BCD(0.6).
Steg 3: Sammanslå A(0.4), BCD(0.6) → rot(1.0). Tilldela A=0, BCD=1.
Bakåt: 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 bitar.
Kodlängdsvarians
Två Huffman-koder kan uppnå samma L men ha olika kodlängdsfördelningar. Kodlängdernas varians mäter denna spridning:
Var(l) = E[l²] − (E[l])²
där E[l] = L (genomsnittlig kodlängd) och E[l²] = Σ p_i · l_i².
Varför varians är viktigt:
1. Bufferkrav. Vid realtidsdekodning tar varje symbol ett varierande antal bitar. Hög varians betyder att vissa symboler tar många bitar — du behöver en större inmatningsbuffert för att garantera att du alltid kan läsa en fullständig symbol.
2. Avkodningsfördröjning. Högvariantkoder har långa värstafallsavkodningsvägar. Lågvarianskoder (täta) begränsar värstafallet mer nära.
3. Robusthet. En förlorad bit i en högjanstkod orsakar mer synkroniseringsskada eftersom långa kodord måste läsas helt om.
Hammings rekommendation: när flera giltiga Huffman-koder existerar (oavgjortbeslut), föredra den med lägre varians — det täta trädet.
Beräkning av varians för två träd
Använd p(A)=0.4, p(B)=0.3, p(C)=0.2, p(D)=0.1 och koden 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-symbols Huffman-kod från början till slut
Ett fullständigt exempel från början till slut: bygg Huffman-kod, beräkna L, beräkna H, verifiera L ≥ H, beräkna Var.
Källa: p(X)=0.6, p(Y)=0.3, p(Z)=0.1.
Huffman-konstruktion:
Steg 1: Sorterad: X(0.6), Y(0.3), Z(0.1). Två lägsta: Y(0.3), Z(0.1).
Sammanslå → YZ(0.4). Lista: X(0.6), YZ(0.4).
Steg 2: Sammanslå X(0.6), YZ(0.4) → rot(1.0). Tilldela X=0, YZ=1.
YZ → Y=10, Z=11.
Kod: 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 bitar.
Entropi: 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 bitar.
L = 1.4 ≥ H = 1.295 ✓. L/H = 1.4/1.295 ≈ 1.081. 8.1% över entropi.
Varians: 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.
Din tur: En fullständig pipeline
log₂-värden som referens: 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.