Warum die Greedy-Strategie optimal ist
Der Huffman-Algorithmus ist ein Greedy-Algorithmus: In jedem Schritt trifft er die lokal optimale Wahl (Merge der beiden billigsten Knoten), ohne voraus zu schauen. Greedy-Algorithmen sind nicht immer global optimal — aber hier sind sie es.
Das Optimalitätsargument
Angenommen, ein Code C hat minimale durchschnittliche Länge L. Betrachten Sie die beiden Symbole mit der niedrigsten Wahrscheinlichkeit, sagen wir p_a und p_b. In jedem optimalen Code müssen diese beiden Symbole als Geschwisterblätter auf der tiefsten Ebene des Baums erscheinen. Warum?
Wenn sie kein gemeinsames Elternteil hätten, könnten Sie das tiefere Symbol gegen einen kürzeren Code austauschen — wodurch L reduziert würde. Daher müssen die tiefsten Blätter die am wenigsten wahrscheinlichen Symbole sein.
Wenn Sie nun a und b in ein Meta-Symbol ab kombinieren (mit p_ab = p_a + p_b), ist jeder optimale Code für das reduzierte Alphabet minus ein Symbol genau der Huffman-Code auf dem reduzierten Problem. Induktion vervollständigt das Argument.
Geometrische Ansicht
Der Huffman-Algorithmus konstruiert den Binärbaum von unten nach oben, indem er die am wenigsten wahrscheinlichen Symbole in der größten Tiefe platziert. Dies minimiert Σ p_i · depth(i) = L.
Eine äquivalente Ansicht: Sie weisen Baumblättern Labels zu, um die gewichtete Pfadlänge zu minimieren, wobei das Gewicht jedes Blatts seine Wahrscheinlichkeit ist.
Ausführen der Greedy-Schritte
Wahrscheinlichkeiten: p(A)=0,4, p(B)=0,3, p(C)=0,2, p(D)=0,1. Summe = 1,0 ✓
Schritt 1: Niedrigste zwei: C(0,2), D(0,1). Merge → CD(0,3). Liste: A(0,4), B(0,3), CD(0,3).
Schritt 2: Niedrigste zwei: B(0,3), CD(0,3) (Unentschieden — beide gültig). Merge → BCD(0,6). Liste: A(0,4), BCD(0,6).
Schritt 3: Merge A(0,4), BCD(0,6) → Wurzel(1,0). Weisen Sie A=0, BCD=1 zu.
Rückwärts: 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.
Varianz der Codelängen
Zwei Huffman-Codes können die gleiche L erreichen, aber verschiedene Codelängenverteilungen haben. Die Varianz der Codelängen misst diese Ausbreitung:
Var(l) = E[l²] − (E[l])²
wobei E[l] = L (durchschnittliche Codelänge) & E[l²] = Σ p_i · l_i².
Warum Varianz wichtig ist:
1. Puffervorgaben. Bei der Echtzeit-Decodierung nimmt jedes Symbol eine variable Anzahl von Bits an. Hohe Varianz bedeutet, dass einige Symbole viele Bits benötigen — Sie brauchen einen größeren Eingabepuffer, um zu garantieren, dass Sie immer ein komplettes Symbol lesen können.
2. Decodierungslatenz. Codes mit hoher Varianz haben lange schlechteste Fall-Decodierungspfade. Codes mit niedriger Varianz (buschig) begrenzen den schlechtesten Fall enger.
3. Robustheit. Ein verlorenes Bit in einem Code mit hoher Varianz verursacht mehr Synchronisationsschaden, da lange Codewörter vollständig neu gelesen werden müssen.
Hamming's Empfehlung: Wenn mehrere gültige Huffman-Codes existieren (Tie-Breaking-Entscheidungen), bevorzugen Sie denjenigen mit niedrigerer Varianz — den buschigen Baum.
Berechnen der Varianz für zwei Bäume
Unter Verwendung von p(A)=0,4, p(B)=0,3, p(C)=0,2, p(D)=0,1 & dem 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-Symbol-Huffman-Code von Anfang bis Ende
Ein vollständiges Beispiel von Anfang bis Ende: Huffman-Code bauen, L berechnen, H berechnen, L ≥ H überprüfen, Var berechnen.
Quelle: p(X)=0,6, p(Y)=0,3, p(Z)=0,1.
Huffman-Konstruktion:
Schritt 1: Sortiert: X(0,6), Y(0,3), Z(0,1). Niedrigste zwei: Y(0,3), Z(0,1).
Merge → YZ(0,4). Liste: X(0,6), YZ(0,4).
Schritt 2: Merge X(0,6), YZ(0,4) → Wurzel(1,0). Weisen Sie X=0, YZ=1 zu.
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% über der Entropie.
Varianz: 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.
Ihre Aufgabe: Eine vollständige Pipeline
log₂-Werte zum Nachschlagen: 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.