Datenkompression: Von Huffman-Codes zur Shannon-Grenze

simulation intermediate ~12 min
Simulation wird geladen...

Formel

\text{Compressed size} \geq N \cdot H \text{ bits}
\text{Compression ratio} = \frac{\text{Original size}}{\text{Compressed size}}
H \leq \bar{L} < H + 1 \quad \text{(single-symbol Huffman)}
\frac{H}{k} \leq \bar{L}_k < \frac{H}{k} + \frac{1}{k} \quad \text{(block-}k\text{ Huffman)}
Jedes Mal, wenn Sie ein Foto senden, ein Video streamen oder eine Datei herunterladen, arbeiten Kompressionsalgorithmen im Hintergrund — sie reduzieren Daten auf ihren wesentlichen Informationsgehalt. Die theoretische Grundlage für all dies ist Shannons Quellencodierungstheorem. Das Theorem besagt eine bemerkenswerte Tatsache: Für jede Quelle, die Symbole mit Entropie H Bit pro Symbol erzeugt, ist es unmöglich, die Daten verlustfrei unter N·H Gesamtbits zu komprimieren (wobei N die Nachrichtenlänge ist), und es ist möglich, beliebig nahe an diese Grenze zu kommen. Die Entropie ist daher der ultimative Kompressionsmaßstab. Huffman-Codierung, 1952 von David Huffman als Doktorand am MIT erfunden, bietet einen praktischen Algorithmus, der sich dieser Grenze annähert. Die Schlüsselidee ist die Codierung variabler Länge: Häufigen Symbolen werden kurze binäre Codewörter zugewiesen, seltenen Symbolen lange. Der Algorithmus konstruiert einen optimalen präfixfreien Code, indem er von unten einen Binärbaum aufbaut und bei jedem Schritt die zwei unwahrscheinlichsten Symbole zusammenführt. Dieser Simulator erzeugt Nachrichten aus vier verschiedenen Quelltypen mit sehr unterschiedlichen Entropieprofilen. Englisch-ähnlicher Text hat schiefe Buchstabenhäufigkeiten (E ist 13 %, Z ist 0,07 %), was eine Entropie von etwa 4,0 Bit ergibt — deutlich unter dem 4,7-Bit-Maximum für 26 Buchstaben. Zufälliger Text ist nahezu inkompressibel. Repetitiver Text hat sehr niedrige Entropie und komprimiert dramatisch. DNA-Sequenzen mit vier annähernd gleich häufigen Basen liegen bei etwa 2 Bit pro Base. Blockcodierung erweitert das Prinzip, indem sie Symbolgruppen als Einheiten behandelt. Da reale Quellen Abhängigkeiten zwischen Symbolen aufweisen (im Englischen folgt auf «q» fast immer «u»), erfasst die gemeinsame Codierung von Symbolblöcken diese Korrelationen und bringt die Kompression näher an die wahre Entropierate.

Häufige Fragen

Wie funktioniert Huffman-Codierung?

Huffman-Codierung weist häufigeren Symbolen kürzere Binärcodes und seltenen Symbolen längere Codes zu. Der Algorithmus baut einen Binärbaum von unten auf: Die beiden Knoten mit der geringsten Häufigkeit werden wiederholt zusammengeführt, bis ein einziger Baum entsteht. Symbole an flachen Blättern erhalten kurze Codes, tiefe Blätter lange Codes. Das Ergebnis ist ein präfixfreier Code — kein Codewort ist Präfix eines anderen — der die erwartete Codelänge für die gegebene Häufigkeitsverteilung minimiert.

Was ist Shannons Quellencodierungstheorem?

Shannons Quellencodierungstheorem (rauschfreies Codierungstheorem) besagt, dass eine Quelle mit Entropie H Bit pro Symbol nicht verlustfrei unter H Bit pro Symbol im Durchschnitt komprimiert werden kann. Umgekehrt kann sie mit ausreichend langen Blockcodes beliebig nahe an H komprimiert werden. Damit wird die Entropie als fundamentale Grenze der verlustfreien Kompression etabliert.

Warum kann man zufällige Daten nicht komprimieren?

Wahrhaft zufällige Daten haben maximale Entropie — jedes Symbol ist gleich wahrscheinlich und es gibt keine Muster. Da die Entropie log₂(N) für N gleich wahrscheinliche Symbole beträgt, entspricht die komprimierte Größe der Originalgröße. Nach dem Schubfachprinzip muss jedes Kompressionsverfahren, das manche Eingaben verkürzt, andere verlängern. Bei gleichverteilten Zufallsdaten ist keine Eingabe wahrscheinlicher als eine andere, sodass keine systematische Kompression möglich ist.

Was ist der Unterschied zwischen verlustfreier und verlustbehafteter Kompression?

Verlustfreie Kompression (Huffman, LZ77, DEFLATE) bewahrt jedes Bit der Originaldaten — die dekomprimierte Ausgabe ist identisch mit der Eingabe. Verlustbehaftete Kompression (JPEG, MP3, H.264) verwirft als wahrnehmungsunwichtig erachtete Informationen und erreicht deutlich höhere Kompressionsraten auf Kosten der Wiedergabetreue. Shannons Quellencodierungstheorem regelt die verlustfreie Kompression; die Rate-Distortion-Theorie die verlustbehaftete.

Quellen

Weitere Simulationen: Informationstheorie

simulation

Kanalkapazität-Explorer
simulation

Fehlerkorrektur-Simulator
simulation

Shannon-Entropie-Rechner
View source on GitHub