Wie Huffman den optimalen Code aufbaut
Hamming präsentiert Huffman-Codierung als einen Greedy-Algorithmus, der einen präfixfreien Code mit minimaler durchschnittlicher Länge konstruiert. Die Schlüsselidee: Bauen Sie den Baum von unten nach oben auf, indem Sie immer die zwei unwahrscheinlichsten Symbole zusammenführen.
Der Forward Pass (Aufbau)
1. Sortieren Sie alle Symbole nach Wahrscheinlichkeit, von höchster zu niedrigster.
2. Nehmen Sie die zwei Symbole mit der niedrigsten Wahrscheinlichkeit. Kombinieren Sie sie zu einem neuen Meta-Symbol mit Wahrscheinlichkeit = Summe der beiden.
3. Fügen Sie das Meta-Symbol an seiner sortierten Position ein.
4. Wiederholen Sie, bis nur noch zwei Symbole übrig sind.
5. Weisen Sie den zwei verbleibenden Symbolen 0 und 1 zu.
Der Backward Pass (Codes zuweisen)
Machen Sie die Zusammenführungen rückwärts rückgängig: Bei jedem Split erhalten die zwei zusammengeführten Symbole die gleichen Präfix-Bits wie ihr kombiniertes übergeordnetes Element plus eine zusätzliche 0 (ein Kind) oder 1 (anderes Kind). Die 0/1-Zuweisung ist beliebig – beide sind gültig.
Warum dies optimal ist: Wenn ein anderer Code eine kleinere durchschnittliche Länge L' hätte, würde die Anwendung derselben Forward-Reduktion schließlich zwei Symbole mit durchschnittlicher Länge von weniger als 1 Bit erzeugen – unmöglich für einen Code mit 2 Symbolen. Widerspruch.
Den Algorithmus nachverfolgend
Beispiel von Hamming: vier Symbole A, B, C, D mit p(A)=0,5, p(B)=0,25, p(C)=0,125, p(D)=0,125.
Forward Pass:
Schritt 1: Sortiert: A(0,5), B(0,25), C(0,125), D(0,125). Die zwei niedrigsten: C, D.
Schritt 2: Zusammenführung CD mit p=0,25. Neue Liste: A(0,5), B(0,25), CD(0,25).
Schritt 3: Die zwei niedrigsten: B(0,25), CD(0,25). Zusammenführung BCD mit p=0,5.
Schritt 4: Zwei Symbole bleiben übrig: A(0,5), BCD(0,5). Weisen Sie A=0, BCD=1 zu.
Backward Pass:
BCD → B erhält 10, CD erhält 11. CD → C erhält 110, D erhält 111.
Finaler Code: 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.
Mehrere gültige Huffman-Codes
Hamming vermerkt zwei Quellen der Nicht-Eindeutigkeit:
1. Beliebige 0/1-Zuweisung. Bei jedem Split können Sie 0 einem beliebigen Kind zuweisen. Der Austausch von 0 und 1 überall ergibt einen anderen Code mit identischem L.
2. Tie-Breaking. Wenn zwei Knoten gleiche Wahrscheinlichkeit haben, kann einer 'höher' platziert werden (zuerst kombiniert). Unterschiedliche Tie-Breaking-Entscheidungen können strukturell verschiedene Bäume erzeugen – 'lange' vs 'buschig' – mit gleichem L aber unterschiedlichen Codlängenverteilungen.
Lang vs Buschig
Langer Baum (schief): ein Symbol auf jeder Tiefenebene (Fibonacci-ähnliche Struktur). Codlängen variieren stark: ein Symbol erhält einen kurzen Code, andere kaskadieren zu längeren Codes.
Buschiger Baum (ausgewogen): Symbole verteilt gleichmäßig über Tiefenebenen. Codlängen clustern nahe am Durchschnitt. Niedrigere Varianz.
Hamming empfiehlt: Wenn Sie eine Wahl haben, bevorzugen Sie den buschigen Baum. Gleiches L, aber kleinere Varianz in Codlängen → mehr gleichmäßige Decodierungszeit → kleinere Pufferspeicheranforderungen in Echtzeitanwendungen.
Berechnung der Codlängen-Varianz
Varianz der Codlängen: Var = E[l²] − (E[l])²
Für den Code {A=0 l=1, B=10 l=2, C=110 l=3, D=111 l=3} mit 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
Ein alternatives buschiger Code für gleichwahrscheinliche Symbole verwendet alle Codes der Länge 2: L=2, Var=0.
Kompressionsverstärkung vs Symbolverteilung
Hamming Regel: Huffman-Codierung zahlt sich nur aus, wenn sich Symbolwahrscheinlichkeiten wesentlich unterscheiden.
Gleiche Wahrscheinlichkeiten. Wenn alle 2^k Symbole gleiche Wahrscheinlichkeit 1/2^k haben, erzeugt Huffman einen Blockcode: jedes Symbol erhält Länge k. L = H = k. Kein Gewinn gegenüber dem einfachen Blockcode.
Schiefe Wahrscheinlichkeiten. Wenn ein Symbol dominiert (p >> 1/2^k für andere), weist Huffman ihm einen sehr kurzen Code zu (Länge 1 oder 2), wodurch L dramatisch sinkt.
Der Kommacode (Hamming Begriff). Wenn jede Wahrscheinlichkeit mehr als 2/3 des Rests überschreitet, erzeugt Huffman natürlicherweise: p(s1)→0, p(s2)→10, p(s3)→110, ..., hinunter zu zwei gleichlangen Codes am Ende. Dies ist ein 'Kommacode': die abschließende 0 nach einer Serie von 1ern wirkt wie ein Komma.
Hamming vermerkt: Echtkompressionsdaten (Sicherung, Dateiarchivierung) können Speicher um mehr als die Hälfte verringern, wenn die Quelle schiefe Wahrscheinlichkeiten hat – Englischer Text ist ein Paradebeispiel.
Huffman vs Blockcode: Numerischer Vergleich
Hamming zweites Beispiel: 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.
Blockcode: 8 Symbole → 3 Bits je → L_Blockcode = 3.
Hamming berechnet den Huffman-Code und berichtet L_Huffman ≈ 2,58 Bits.
Einsparungen: (3 − 2,58)/3 ≈ 14% Kompression gegenüber Blockcodierung.
Wenn sich Symbolwahrscheinlichkeiten stark unterscheiden (1/3 vs 1/30 hier, Verhältnis 10:1), zahlt sich Codierung variabler Länge wesentlich aus.
Selbstkompilingprogramme
Hamming endet Kapitel 11 mit einer auffallenden Idee: Ein Huffman-Encoder kann sich selbst codieren. Der Decodierungsbaum (der dem Decoder sagt, wie die komprimierte Nachricht zu lesen ist) wird zusammen mit den komprimierten Daten übertragen. Der Empfänger benötigt keine vorherige Kenntnis des Codes.
Der Encoder: Beispiel die Daten, schätzen Sie Wahrscheinlichkeiten, konstruieren Sie den Huffman-Code, codieren Sie den Decodierungsbaum als Header, codieren Sie dann die Daten.
Der Decoder: Lesen Sie den Header, um den Baum zu rekonstruieren, dekodieren Sie dann die Daten damit.
Hamming Punkt: Diese gesamte Pipeline kann als Bibliotheksfunktion ohne menschliches Eingreifen ausgeführt werden. Sie rufen sie auf, sie komprimiert und dekomprimiert automatisch. Moderne Archivierungsformate (ZIP, gzip, bzip2) implementieren genau dieses Muster.
Das tiefere Prinzip: Die Intelligenz liegt im Algorithmus, nicht in einer festen Codetabelle. Der Algorithmus passt sich an, was immer er empfängt. Dies ist das Muster, das Hamming über alle großen Ingenieurssysteme hinweg sieht: Anpassungsfähigkeit eingebaut, nicht aufgeschraubt.