Huffman-Kodierungs-Visualisierer

Gib Text ein, um zu sehen, wie die Huffman-Kodierung häufigen Zeichen kürzere Codes zuweist.

Rechenbeispiel — Huffman-Kodierungs-Visualisierer

Original (8-Bit-ASCII)	88
Huffman-codierte Bits	32
Ersparnis	63.6%
'l' (3×)	10
'␣' (1×)	000
'w' (1×)	001
'r' (1×)	010
'd' (1×)	011

Das sind die Werte, die der Rechner beim Öffnen der Seite anzeigt. Ändere oben eine Eingabe, um sie neu zu berechnen.

Interaktive Simulation wird geladen...

Huffman kann nie weniger als ein Bit ausgeben 🖖

Huffman-Codes sind optimal, aber nur innerhalb einer Regel, die sie teuer macht: jedes Symbol muss eine ganze Zahl von Bits erhalten. Nach Shannons Grenze ist ein Symbol, das in 90% der Fälle auftritt, etwa 0,15 Bit wert, und eine Quelle aus 90% einem Zeichen und 10% einem anderen trägt nur 0,469 Bit Entropie pro Symbol. Huffman kann keinen Bruchteil eines Bits schreiben und vergibt daher 1 und 1 — mehr als das Doppelte des Informationswerts. Diese Lücke ist der Grund, weshalb stark schiefe Daten hier enttäuschend komprimieren, und weshalb es arithmetische und Range-Coder gibt: sie kodieren die ganze Nachricht als eine Zahl und dürfen gebrochene Bits ausgeben. Huffman ist optimal unter den Ganz-Bit-Codes, was eine engere Aussage ist als optimal.

Immer die zwei seltensten verschmelzen 🖖

Der Baum wächst von unten nach oben: Zunächst wird jedes Zeichen nach seiner Häufigkeit aufgelistet, dann werden wiederholt die zwei seltensten Elemente zu einem kleinen Teilbaum zusammengefasst und als ein Bündel behandelt. Das wiederholt sich, bis ein einziger Baum übrig bleibt; die Codes liest man dann von oben ab — links ist 0, rechts ist 1. Diese "gierige" Gewohnheit, stets die zwei kleinsten zu vereinen, wirkt kurzsichtig, erzeugt aber beweisbar die kürzestmöglichen Codes.

Eine Seminararbeit, die den Professor schlug 🖖

David Huffman entwickelte das Verfahren 1951 als Doktorand am MIT, als Professor Robert Fano seiner Klasse die Wahl zwischen einer Abschlussprüfung und einer Arbeit über den effizientesten Code ließ. Fano und Claude Shannon hatten es bereits versucht und ihre Bäume von oben nach unten gebaut. Huffman gab fast auf, erkannte dann aber, dass der Aufbau von unten — zuerst die seltensten Symbole verschmelzen — optimal ist, und übertraf damit die Methode seines eigenen Lehrers.

HUFFMAN-CODIERUNG — WANN HILFT SIE, UND WIE NAH AM OPTIMUM IST SIE?

In welchem Kompressionsfall bist du?

Huffman gibt häufigen Zeichen kurze und seltenen lange Codes und ist beweisbar das Beste, solange jedes Zeichen eine ganze Zahl von Bits bekommt. Was dabei herausspringt, hängt ganz davon ab, wie ungleich die Häufigkeiten sind. Vollkommen gleich, und es gibt nichts auszunutzen; sehr ungleich, und der Gewinn ist groß — bis zu dem Punkt, an dem nicht mehr die Häufigkeiten die Grenze setzen, sondern die ganzzahligen Bits.

Schiefe Häufigkeiten — genau wofür das Verfahren da ist p_i ↑ ⇒ ℓ_i ↓

Alle Zeichen gleich häufig — nichts auszunutzen p_i = 1/n ⇒ ℓ = log₂n

Gewöhnlicher Text — auf ein Bit an die theoretische Grenze heran H ≤ ℓ < H + 1

Nur ein Zeichen — die Grenze, die Huffman nicht unterschreiten kann n = 1 ⇒ ℓ = 1

Schiefe Häufigkeiten — genau wofür das Verfahren da ist

Was du weißt: Wenige Zeichen beherrschen den Text. Sie bekommen die kürzesten Codes, und die Gesamtlänge fällt deutlich unter eine feste Codelänge.

Kosten: p_i ↑ ⇒ ℓ_i ↓

Rechenbeispiel: „mississippi": 11 Zeichen, 4 verschiedene Symbole, codiert in 21 Bit gegenüber 88 bei 8-Bit-Zeichen — eine Ersparnis von 76,1 %

Diesen Fall öffnen: mississippi

Schiefe Häufigkeiten — genau wofür das Verfahren da ist. Die zwei häufigsten Zeichen bekommen die kürzesten Codes, und die Gesamtlänge sinkt entsprechend. Wenige Zeichen beherrschen den Text. Sie bekommen die kürzesten Codes, und die Gesamtlänge fällt deutlich unter eine feste Codelänge. — Die zwei häufigsten Zeichen bekommen die kürzesten Codes, und die Gesamtlänge sinkt entsprechend.

Alle Zeichen gleich häufig — nichts auszunutzen

Was du weißt: Bei flacher Verteilung gibt es keine häufigen Zeichen zu belohnen. Huffman entartet zu etwas, das einem Code fester Länge sehr nahe kommt.

Kosten: p_i = 1/n ⇒ ℓ = log₂n

Rechenbeispiel: „abcdef": 6 verschiedene Zeichen, jedes einmal, codiert in 16 Bit. Ein schlichter 3-Bit-Code für sechs Zeichen bräuchte 18.

Diesen Fall öffnen: gleichverteilt

Alle Zeichen gleich häufig — nichts auszunutzen. Eine flache Verteilung ergibt einen nahezu gleichmäßigen Baum, und alle Codes sind etwa gleich lang. Bei flacher Verteilung gibt es keine häufigen Zeichen zu belohnen. Huffman entartet zu etwas, das einem Code fester Länge sehr nahe kommt. — Eine flache Verteilung ergibt einen nahezu gleichmäßigen Baum, und alle Codes sind etwa gleich lang.

Gewöhnlicher Text — auf ein Bit an die theoretische Grenze heran

Was du weißt: Eine realistische Mischung aus wiederholten und einmaligen Zeichen. Das ist der Alltagsfall, und das Ergebnis liegt knapp über der Entropiegrenze.

Kosten: H ≤ ℓ < H + 1

Rechenbeispiel: „hello world": 11 Zeichen über 8 verschiedene Symbole, codiert in 32 Bit gegenüber 88 — 63,6 % gespart, bei einer Entropiegrenze von 31,3 Bit

Diesen Fall öffnen: hello world

Gewöhnlicher Text — auf ein Bit an die theoretische Grenze heran. Eine gemischte Verteilung ergibt einen schiefen Baum, und die Summe landet knapp über der Entropiegrenze. Eine realistische Mischung aus wiederholten und einmaligen Zeichen. Das ist der Alltagsfall, und das Ergebnis liegt knapp über der Entropiegrenze. — Eine gemischte Verteilung ergibt einen schiefen Baum, und die Summe landet knapp über der Entropiegrenze.

Nur ein Zeichen — die Grenze, die Huffman nicht unterschreiten kann

Was du weißt: Ein Text ganz ohne Abwechslung. Seine Entropie ist null, doch Huffman muss weiterhin mindestens ein Bit je Zeichen ausgeben, denn kürzer als ein Bit geht kein Code.

Kosten: n = 1 ⇒ ℓ = 1

Rechenbeispiel: „aaaaaaaaaa": 10 Zeichen, ein einziges Symbol, codiert in 10 Bit. Die Entropie des Textes beträgt 0 Bit.

Diesen Fall öffnen: einzelnes Zeichen

Nur ein Zeichen — die Grenze, die Huffman nicht unterschreiten kann. Ein Zeichen, ein Bit pro Stück: keine Verteilung zum Ausnutzen und kein kürzerer Code verfügbar. Ein Text ganz ohne Abwechslung. Seine Entropie ist null, doch Huffman muss weiterhin mindestens ein Bit je Zeichen ausgeben, denn kürzer als ein Bit geht kein Code. — Ein Zeichen, ein Bit pro Stück: keine Verteilung zum Ausnutzen und kein kürzerer Code verfügbar.

Quellen (1)

Insight block 3 — the term paper itself: D. A. Huffman, "A Method for the Construction of Minimum-Redundancy Codes." Proceedings of the IRE 40(9), 1098–1101, 1952.

Aufgabe vollständig gelöst

Die Einsparung bei der Kodierung von "hello world" mit Huffman-Kodierung 5 Schritte
Kodiere "hello world" mit Huffman-Kodierung. Finde die Ersparnis — finde dann die Grenze, die angibt, wie viel besser ein Code überhaupt sein könnte.
1. ASCII mit fester Breite verbraucht für jedes Zeichen dieselben acht Bits, egal wie oft es vorkommt. Das ist die Verschwendung, die Huffman beseitigt: Häufige Symbole erhalten kurze Codes, seltene lange Codes.
  
  $"hello world" : 11 chars \times 8 bits = 88 bits$
2. Zähle zuerst die Symbole, da der Code aus den Häufigkeiten aufgebaut wird. Nur 'l' und 'o' wiederholen sich; die anderen sechs Zeichen kommen jeweils einmal vor.
  
  $ℓ = 3, o = 2, others = 1 each (8 distinct symbols)$
3. Die Shannon-Entropie ist der mittlere Informationsgehalt pro Symbol. Sie bildet eine feste Untergrenze: Kein eindeutig decodierbarer Code kann im Mittel darunterliegen. Entscheidend sind drei verschiedene Wahrscheinlichkeiten: 3/11 für „l“, 2/11 für „o“ und 1/11 für jedes der übrigen sechs Symbole. Damit lautet die Summe (3/11)(1,8745) + (2/11)(2,4594) + (6/11)(3,4594).
  
  $H = - i \sum p_{i} lo g_{2} p_{i} = 2.845 bits/symbol$
4. Multipliziere mit der String-Länge für die Untergrenze in Bits. Huffman muss bei diesem Wert oder darüber liegen und kann ihn im Allgemeinen nicht erreichen, da Codelängen ganze Bit-Zahlen sind, die Entropie hingegen nicht.
  
  $11 \times 2.845 = 31.3 bits (entropy floor) \leq 32 (Huffman)$
5. Konstruiere den Baum, um die tatsächliche Länge zu bestimmen. Beim Huffman-Verfahren werden jeweils die beiden kleinsten Gewichte zusammengefasst: 1+1, 1+1, 1+1, dann 2+2, danach 2+2, 3+4 und schließlich 4+7. Jede Zusammenfassung verlängert den Code aller darunterliegenden Symbole um ein Bit. Die Länge der Codierung ist daher die Summe der zusammengefassten Gewichte: 2+2+2+4+4+7+11 = 32. Genau diesen Wert zeigt die Visualisierung an.
  
  $Huffman = 32 bits ⟹ saving = 1 - \frac{32}{88} = 63.6%$
Antwort

88 Bits runter auf 32 — eine Ersparnis von 63.6%. Die Entropie-Untergrenze für diese Häufigkeiten liegt bei 31.3 Bits, und Huffman ergab 32 — 0.7 Bits über dem Optimum, verbraucht durch das Aufrunden von acht Codelängen auf ganze Bits. Die Garantie ist die Schranke H ≤ mittlere Länge < H + 1: Huffman liegt nie mehr als ein Bit pro Symbol über dem Optimum. Genau diese Ein-Bit-Lücke ist der Grund, warum es arithmetische Kodierung gibt.

$88 \to 32 bits (63.6%) H \leq \overset{ˉ}{ℓ} < H + 1$

Lernpfad

Kompression von Hand

Führt zu LZ77 Codes ungleicher Länge, wobei die kurzen für häufige Symbole genutzt werden.

Vom 42Math-Team · Aktualisiert 2026-07-27

Anhand veröffentlichter Quellen geprüft. Korrekturen willkommen. Redaktionsrichtlinie · Korrekturen

Alle Lektionen: Informatik →

Beispielaufgaben

hello world - Von 88 Bit im ASCII-Code auf 32: Das spart 63,6 % und liegt nur 0,7 Bit über der Entropiegrenze von 31,3.
mississippi - Vier verschiedene Zeichen in einem Wort aus elf Zeichen: Statt 88 Bit genügen 21, wobei s einen Ein-Bit-Code erhält. Mit 0,95 Bit ist hier auch der Abstand zur Entropiegrenze am größten.
gleichverteilt - Sechs Symbole, jedes genau einmal. Hier gibt es nichts auszunutzen. Trotzdem sind es nur 16 Bit gegenüber 18 bei einem Code fester Länge, denn sechs Symbole schöpfen drei Bit nicht aus.
einzelnes Zeichen - Zehn gleiche Zeichen enthalten genau 0 Bit Information. Huffman benötigt dennoch 10 Bit: eines pro Symbol, denn weniger als ein Bit kann der Code nicht verwenden.