Entropiecodierungs-Playground

Erforsche, wie unterschiedliche Symbolverteilungen die Shannon-Entropie beeinflussen, vergleiche die Grenzen der Huffman-Codierung und lerne, wie Entropie Verlustfunktionen und die Vokabularunsicherheit moderner KI-Sprachmodelle (LLMs) bestimmt.

Startwerte — Entropiecodierungs-Playground

Verteilungsparameter (λ)	1.5

Ändere oben einen Regler, und die Ergebnisse werden neu berechnet.

Interaktive Simulation wird geladen...

Ganze Bits sind der Preis, den Huffman zahlt 🖖

Entropiecodierung nutzt statistische Redundanz, um Nachrichten mit möglichst wenigen Bits darzustellen. Shannons Quellencodierungssatz besagt, dass die absolute Mindestlänge jedes verlustfreien Codes im Mittel der Shannon-Entropie entspricht: H(X) = −Σ p_i log₂ p_i. Die Huffman-Codierung ist optimal für ein gegebenes Alphabet, wenn Symbole einzeln codiert werden, ist aber auf ganzzahlige Codewortlängen beschränkt. Diese Ganzzahlbeschränkung bedeutet, dass Huffman um bis zu 0,086 Bit/Symbol von der theoretischen Entropie abweichen kann (und deutlich mehr, wenn ein Symbol p_i ≈ 1 hat). Arithmetische Codierung (z. B. ANS) überwindet diese Grenze, indem sie die gesamte Sequenz auf gebrochene Intervalle abbildet.

Bezug zu KI-Sprachmodellen: In modernen Sprachmodellen (LLMs) ist Entropie ein zentrales Konzept sowohl beim Training als auch bei der Generierung. LLMs werden trainiert, indem der Kreuzentropie-Verlust zwischen ihren Vokabularvorhersagen und dem tatsächlichen Text minimiert wird. Bei der Generierung (Inferenz) gibt das LLM eine Wahrscheinlichkeitsverteilung über sein Vokabular für das nächste Token aus. Die Entropie dieser Verteilung misst die Vorhersageunsicherheit des Modells: Eine flache Verteilung (hohe Entropie) erzeugt kreativen oder zufälligen Text, während eine spitze Verteilung (niedrige Entropie) hochgradig vorhersagbaren Text erzeugt. Sampling-Parameter wie die Temperatur skalieren diese Entropie direkt (niedrigere Temperatur verringert die Entropie, höhere Temperatur erhöht sie), während Nucleus-Sampling (Top-p) die kumulative Wahrscheinlichkeit dynamisch begrenzt, um Ausläufer mit hoher Entropie abzuschneiden.

Warum seltene Symbole mehr Bits kosten 🖖

Die eigentliche Lektion dieses Tools: Die ideale Bitzahl für ein Symbol ist sein Überraschungswert, −log₂ p. Ein Symbol, das in der Hälfte der Fälle auftritt, verdient 1 Bit; eines mit Wahrscheinlichkeit 1 zu 1000 rund 10 Bit. Die Entropie ist einfach der durchschnittliche Überraschungswert über alle Symbole. Deshalb lassen sich schiefe Verteilungen (wie die Laplace- oder Exponential-Voreinstellung) gut komprimieren, ein gleichverteiltes Alphabet dagegen nicht — bei Gleichverteilung gibt es keine Redundanz zu entfernen.

Morsecode: Entropiecodierung vor Shannon 🖖

Der Morsecode ordnete das kürzeste Zeichen, einen einzelnen Punkt, dem E zu, dem häufigsten Buchstaben im Englischen, und lange Folgen den seltenen wie Q und Z. Um die Längen festzulegen, zählte Alfred Vail angeblich die Lettern im Setzkasten einer Druckerei, um die Buchstabenhäufigkeiten zu schätzen. Das war funktionierende Codierung mit variabler Länge in den 1840er-Jahren — rund ein Jahrhundert bevor Shannon 1948 formalisierte, warum sie funktioniert.

EINE STUFE EINER KETTE — WAS ANKOMMT, WAS HERAUSGEHT, WAS DANACH BRICHT

Wo diese Stufe in der Encoding-Pipeline sitzt

Ein Video-Encoder ist kein einzelner Algorithmus, sondern acht Stufen in fester Reihenfolge — und die Reihenfolge ist nicht beliebig: Jede Stufe existiert, weil die vorherige ihre Arbeit erst möglich gemacht hat. Dieses Werkzeug modelliert eine davon. Die Kette unten verlinkt die anderen sieben.

Entropiecodierungs-Playground — packt die quantisierten Symbole in so wenige Bits, wie ihre Statistik zulässt

Was ankommt: Ein Strom quantisierter ganzer Zahlen, stark in Richtung null verschoben.
Was herausgeht: Der fertige Bitstrom. Hier wird nichts verworfen.
Was die nächste Stufe voraussetzt: Nichts danach — dies ist die letzte Codierstufe. Ihre Voraussetzung liegt davor: dass die Symbolverteilung für sie schon schief gemacht wurde.
Was hier schiefgeht: Kein Entropiecodierer kann die Shannon-Entropie dessen unterbieten, was man ihm übergibt, also setzen allein die früheren Stufen seine Obergrenze. Läuft er auf unquantisierten Koeffizienten, findet er kaum Redundanz — und genau deshalb kommt der verlustbehaftete Schritt zuerst und nicht zuletzt.

Vorherige Stufe: Quantisierung Nächste Stufe: Ratensteuerung

Aufgabe vollständig gelöst

Der verbleibende Spielraum für einen schlaueren Algorithmus als Huffman bei 16 Symbolen 6 Schritte
16 Symbole, Laplace-Verteilung, Entropie 3,010 Bit. Huffman erreicht 3,012. Berechnen Sie, wie viel Spielraum für einen klügeren Algorithmus bleibt.
1. Die Entropie ist die mittlere Überraschung, in Bit, eines aus dieser Verteilung gezogenen Symbols. Sie ist allein eine Eigenschaft der Wahrscheinlichkeiten und weiß nichts über irgendeinen Code.
  
  $H (X) = - i = 1 \sum N p_{i} lo g_{2} p_{i} = 3.010 bits/symbol (N = 16, Laplacian, λ = 1.5)$
2. Die naive Alternative gibt jedem Symbol die gleiche Anzahl an Bit, und 16 Symbole benötigen 4. Das ist die Referenz, an der die Ersparnis gemessen wird.
  
  $L_{fixed} = ⌈ lo g_{2} N ⌉ = ⌈ lo g_{2} 16 ⌉ = 4.0 bits/symbol$
3. Huffman weist häufigen Symbolen kurze Codes zu und seltenen lange, und der Mittelwert ist die wahrscheinlichkeitsgewichtete Länge.
  
  $\overset{ˉ}{L} = \sum p_{i} L_{i} = 3.012 bits/symbol$
4. Die Ersparnis vergleicht die zwei Codelängen, nicht den Code mit der Entropie – weshalb sie eine Aussage über diese Alternative ist und nicht über die Grenze.
  
  $savings = \frac{4.0 - 3.012}{4.0} = 24.7%$
5. Vergleichen Sie nun mit der Grenze. Shannons Quellencodierungssatz besagt, dass kein Präfixcode unter H liegen kann, und Huffman liegt garantiert unter H + 1.
  
  $H \leq \overset{ˉ}{L} < H + 1 (Shannon); \overset{ˉ}{L} - H = 3.012 - 3.010 = 0.002 bits$
6. Drücken Sie die verbleibende Lücke als Anteil aus, und die Optimierungsfrage beantwortet sich von selbst.
  
  $\frac{0.002}{3.010} = 0.07% above the floor$
Antwort

0,002 Bits pro Symbol oder 0,07 %. Nach dem Satz von Shannon liegt jeder Präfixcode zwischen H und H + 1. Huffman ist darunter erwiesenermaßen optimal. Kein Präfixcode wird für diesen Text also jemals die 3,012 unterbieten. Die Einsparung von 24,7 % gegenüber der Codierung mit fester Länge ist real. Die restlichen 0,07 % sind absolut alles, was noch bessere Technik jemals herausholen könnte. Weitere Kompression erreichst du ab diesem Punkt über das Modell, nicht über den Code: Korrelieren benachbarte Symbole, fällt die Entropie der bedingten Verteilung unter 3,010. Und das ist eine völlig andere Zahl.

$\overset{ˉ}{L} - H = 0.002 bits : Huffman is 0.07% off optimal here$

Quellen (1)

Insight block 2 — entropy as average surprise, and the limit Huffman cannot beat: C. E. Shannon, "A Mathematical Theory of Communication." Bell System Technical Journal 27(3), 379–423, 1948.

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

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

Alle Lektionen: Informatik →

Beispielaufgaben

Gleichverteilung 8 - Gleichverteilte Quelle mit 8 Symbolen: H=3 Bit, kein Codierungsgewinn — Entropie entspricht dem Festlängencode
DCT-ähnlich (Laplace) - DCT-ähnliche Laplace-Verteilung: H≈2.1 Bit, 23% Einsparung — die meisten AC-Koeffizienten im Video häufen sich nahe null
Bewegungsvektor-ähnlich - Exponentialverteilung wie bei Bewegungsvektoren: H≈2.3 Bit, 43% Einsparung gegenüber einem 4-Bit-Festlängencode
Bimodal - Bimodal: zwei dominante Symbole ergeben H≈2.5 Bit, deutlicher Kompressionsgewinn durch Huffman