Wie Huffman den optimalen Code erstellt
Hamming stellt den Huffman-Codierungsalgorithmus als einen gierigen Algorithmus dar, der einen minimalen durchschnittlichen präfixfreien Code erstellt. Das Schlüsselelement: Der Baum wird von unten nach oben aufgebaut, immer die beiden am wahrscheinlichsten vorkommenden Symbole kombinieren.
Der Vorwärts-Pass (Erstellen)
1. Sortiere alle Symbole nach Wahrscheinlichkeit, von der höchsten zur niedrigsten.
2. Nimm die beiden niedrigstwahrscheinlichen Symbole. Verbinde sie zu einem neuen Meta-Symbol mit Wahrscheinlichkeit = Summe der beiden.
3. Füge das Meta-Symbol in seiner sortierten Position ein.
4. Wiederhole, bis nur noch zwei Symbole übrig bleiben.
5. Weise 0 und 1 den beiden verbleibenden Symbolen zu.
Der Rückschritt (Codes zuweisen)
Mache die Verknüpfungen rückgängig in umgekehrter Reihenfolge: Bei jedem Splitter erhalten die beiden Symbole, die miteinander verknüpft wurden, die gleichen Präfix-Bits wie ihr kombiniertes Elternteil, plus ein zusätzliches 0 (ein Kind) oder 1 (das andere Kind). Die 0/1-Zuweisung ist willkürlich - beide sind gültig.
Warum ist dies optimal: Wenn ein anderer Code eine kleinere durchschnittliche Länge L' hätte, würde die gleiche vorwärts-Reduktion schließlich zwei Symbole mit einer durchschnittlichen Länge von weniger als 1 Bit ergeben - unmöglich für einen 2-Symbol-Code. Widerspruch.
Nachverfolgung des Algorithmus
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.
Vorwärts-Pass:
Schritt 1: Geordnet: A(0.5), B(0.25), C(0.125), D(0.125). Niedrigste zwei: C, D.
Schritt 2: Verbinde CD mit p=0.25. Neue Liste: A(0.5), B(0.25), CD(0.25).
Schritt 3: Niedrigste zwei: B(0.25), CD(0.25). Verbinde BCD mit p=0.5.
Schritt 4: Zwei Symbole übrig bleiben: A(0.5), BCD(0.5). Weise A=0, BCD=1 zu.
Rückschritt:
BCD → B erhält 10, CD erhält 11. CD → C erhält 110, D erhält 111.
Endgültiger 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 weist zwei Quellen für Nicht-Einzigartigkeit aus:
1. Willkürliche 0/1-Zuweisung. Bei jedem Split können Sie 0 beiden Kindern geben. Das Umkehren von 0 und 1 gibt ein anderes Code mit identischen L.
2. Unentschieden. Wenn zwei Knoten die gleiche Wahrscheinlichkeit haben, kann jedes als 'höher' (zuerst kombiniert) platziert werden. Verschiedene Entscheidungen im Hinblick auf das Unentschieden können strukturiert verschiedene Bäume - 'lang' vs 'buschig' - mit dem gleichen L, aber verschiedenen Code-Längenverteilungen erzeugen.
Lang vs Buschig
Lang (verzerrt): Ein Symbol auf jeder Tiefeebene (Fibonacci-artige Struktur). Code-Längen variieren stark: Ein Symbol erhält ein kurzes Code, andere stürzen sich in längere Codes.
Buschige Baum (ausgewogen): Symbole werden gleichmäßig über die Tiefebenen verteilt. Code-Längen sind in der Nähe des Durchschnitts konzentriert. Niedrigere Varianz.
Empfehlung von Hamming: Wenn Sie eine Wahl haben, bevorzugen Sie den buschigen Baum. Das gleiche L, aber kleinere Varianz in den Code-Längen → gleichmäßigere Dekodierzeit → kleinere Pufferanforderungen in Echtzeit-Anwendungen.
Rechnen Sie die Varianz der Code-Längen
Variance der Code-Lä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
Eine alternative buschige Code für gleichwahrscheinliche Symbole verwendet alle Länge-2-Codes: L=2, Var=0.
Kompressionsgewinne vs. Symbolverteilung
Hamming-Regel: Huffman-Codierung zahlt sich nur aus, wenn die Symbolwahrscheinlichkeiten sich erheblich unterscheiden.
Gleiche Wahrscheinlichkeiten. Wenn alle 2^k Symbole eine gleichwahrscheinlichkeit von 1/2^k haben, erzeugt Huffman einen Blockcode: Jedes Symbol erhält eine Länge von k. L = H = k. Kein Gewinn über den einfachen Blockcode.
Ungleichgewichtliche Wahrscheinlichkeiten. Wenn ein Symbol dominiert (p >> 1/2^k für andere), kodiert Huffman es mit einer sehr kurzen Code (Länge 1 oder 2), was L dramatisch reduziert.
Das Komma-Code (Hamming's Begriff). Wenn jede Wahrscheinlichkeit 2/3 des verbleibenden Gesamtbetrags überschreitet, erzeugt Huffman natürlich: p(s1)→0, p(s2)→10, p(s3)→110, ..., bis zu zwei gleichen Länge-Codes am Ende. Dies ist ein 'Komma-Code': Das führende 0 nach einer Folge von 1s wirkt wie ein Komma.
Hamming bemerkt: Die reale Datenkompression (Backup, Dateiarchivierung) kann die Speicherung um mehr als die Hälfte reduzieren, wenn die Quelle ungleiche Wahrscheinlichkeiten hat - Englisch-Text ist ein hervorragendes Beispiel.
Huffman vs. Blockcode: Numerischer Vergleich
Hamming's 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 jedes → L_block = 3.
Hamming berechnet den Huffman-Code und berichtet L_Huffman ≈ 2,58 Bit.
Sparsen: (3 − 2,58)/3 ≈ 14% Komprimierung über Blockcodierung.
Wenn die Symbolwahrscheinlichkeiten stark voneinander abweichen (1/3 vs 1/30 hier, ein Verhältnis von 10:1), zahlt die Variable-Länge-Codierung erheblich.
Selbstkompilende Programme
Hamming beendet Kapitel 11 mit einer beeindruckenden Idee: Eine Huffman-Encoder kann sich selbst codieren. Die Dekodiertaste (die dem Decoder zeigt, wie er die komprimierte Nachricht lesen soll) wird zusammen mit den komprimierten Daten übertragen. Der Empfänger benötigt keine vorherige Kenntnis des Codes.
Der Encoder: Probiert die Daten ab, schätzt Wahrscheinlichkeiten, erstellt den Huffman-Code, kodiert den Dekodiertree als Header und codiert dann die Daten.
Der Decoder: Liest den Header, um den Baum wiederherzustellen, und dann codiert die Daten, indem er ihn verwendet.
Hamming's Punkt: Dieser gesamte Prozess kann als Bibliotheksfunction mit keiner menschlichen Beteiligung laufen. Sie rufen es auf, es komprimiert und dekompiliert automatisch. Moderne Archivierungsformate (ZIP, gzip, bzip2) implementieren genau diesen Muster.
Das tiefergehende Prinzip: Die Intelligenz liegt im Algorithmus, nicht in einem festen Codiertabelle. Der Algorithmus passt sich den Daten an, die er empfängt. Dies ist das Muster, das Hamming über alle großartigen Ingenieur-Systeme sieht: Anpassungsfähigkeit, die eingebaut ist, nicht nachgerüstet.