1. Das Schubfachprinzip: Warum es keinen universellen Kompressor geben kann, der jede Datei verkleinert

Wenn wir täglich Werkzeuge wie zip, gzip, zstd, 7z oder PNG nutzen, um Dokumente, Quellcode oder Bilder auf einen Bruchteil ihrer ursprünglichen Größe zu schrumpfen und anschließend Bit für Bit exakt wiederherzustellen (verlustfreie / reversible Kompression), drängt sich eine scheinbar naheliegende Frage auf: Wenn ein Kompressionsprogramm eine Datei verkleinert, warum komprimieren wir die erzeugte .zip-Datei nicht einfach zehnmal hintereinander, bis selbst ein riesiger Film nur noch ein einziges Byte groß ist?

Die Antwort lautet: Es ist mathematisch unmöglich. Der Beweis erfordert nicht einmal komplexe Informationstheorie, sondern folgt unmittelbar aus dem Schubfachprinzip (Pigeonhole Principle) der elementaren Kombinatorik.

Sei $E: \{0,1\}^* \to \{0,1\}^*$ ein verlustfreier Encoder und $D: \{0,1\}^* \to \{0,1\}^*$ der zugehörige Decoder. Damit jede beliebige Eingabedatei $x$ ohne Informationsverlust rekonstruiert werden kann ($D(E(x)) = x$), muss die Abbildung $E$ zwingend injektiv (eineindeutig) sein – denn würden zwei verschiedene Dateien $x_1 \ne x_2$ auf denselben komprimierten Bitstring $y = E(x_1) = E(x_2)$ abgebildet, könnte der Decoder niemals entscheiden, ob er $x_1$ oder $x_2$ ausgeben soll!

Betrachten wir nun alle möglichen Binärdateien der exakten Länge $N$ Bits: Es gibt genau $2^N$ solche Dateien. Wie viele Binärstrings gibt es insgesamt, die echt kürzer als $N$ Bits sind (also Länge $0$ bis $N-1$ besitzen)? Die geometrische Summe liefert:

Da es $2^N$ Eingabedateien („Tauben“), aber nur $2^N - 1$ kürzere Bitstrings („Schubfächer“) gibt, erzwingt das Schubfachprinzip ein unerbittliches Gesetz: Jeder verlustfreie Kompressionsalgorithmus, der mindestens eine Datei verkleinert, MUSS zwingend andere Dateien vergrößern (expandieren)! Mehr noch: Die Gesamtzahl aller Bitstrings mit einer Länge $\le N - c$ beträgt lediglich $2^{N-c+1} - 1$. Damit gilt für den Anteil der Dateien der Länge $N$, die sich um mindestens $c$ Bits verkleinern lassen:

Im Universum aller möglichen 1-MB-Dateien lassen sich weniger als $2^{-99} \approx 1{,}57 \times 10^{-30}$ aller Dateien um auch nur 100 Bits (12,5 Byte) komprimieren! Fast alle zufälligen Bitstrings sind algorithmisch inkompressibel. Dass unsere Alltagsdateien dennoch drastisch schrumpfen, liegt daran, dass menschliche Texte, Programmcode und Sensordaten keine gleichverteilten Zufallsfolgen sind, sondern eine verschwindend kleine, hochgradig strukturierte Niedrig-Entropie-Teilmenge von $\{0,1\}^N$ bewohnen.

2. Shannons Quellencodierungstheorem und die Entropie: Die physikalische Grenze der Kompression

Im Jahr 1948 beantwortete Claude E. Shannon in „A Mathematical Theory of Communication“ die fundamentale Frage, wie stark eine Informationsquelle im Mittel komprimiert werden kann. Sei $\mathcal{A} = \{s_1, \dots, s_m\}$ ein Alphabet mit den Auftrittswahrscheinlichkeiten $P = (p_1, \dots, p_m)$. Shannon definierte den Informationsgehalt (Eigeninformation / Surprisal) eines einzelnen Symbols $s_i$ sowie dessen Erwartungswert, die Shannon-Entropie $H(X)$, als:

Ordnet man jedem Symbol $s_i$ ein binäres präfixfreies Codewort der Länge $\ell_i$ zu (sodass kein Codewort Präfix eines anderen ist), müssen die Wortlängen genau die Kraft-McMillan-Ungleichung erfüllen:

Mithilfe der Nichtnegativität der Kullback-Leibler-Divergenz $D_{\text{KL}}(P \,\|\, Q) \ge 0$ für $q_i = 2^{-\ell_i}/Z$ ($Z = \sum 2^{-\ell_i} \le 1$) lässt sich für die mittlere Codewortlänge $L = \sum_{i=1}^m p_i \ell_i$ unmittelbar Shannons Quellencodierungstheorem (Noiseless Coding Theorem) beweisen:

Die Shannon-Entropie $H(X)$ bildet die unüberwindbare untere Schranke jeder symbolweisen verlustfreien Codierung.

  flowchart TD
    A["Rohdatenstrom (Text / Bild / Binärcode)"] --> B["Stufe 1: Transformation & Wörterbuch-Modellierung (BWT / LZ77)"]
    B --> C["Wahrscheinlichkeitsverteilung P(s) von Symbolen & (Distanz, Länge)-Paaren"]
    C --> D["Stufe 2: Statistische Entropiecodierung (Huffman / Arithmetisch / ANS)"]
    D --> E["Kompakter Bitstrom nahe der Shannon-Grenze N·H(X)"]

3. Drei Generationen der Entropiecodierung: Huffman, Arithmetische Codierung und ANS

3.1 Huffman-Codierung (1952): Optimale ganzzahlige Präfixbäume

David A. Huffman entwickelte 1952 einen Greedy-Algorithmus, der in $O(m \log m)$ Zeit durch sukzessives Verschmelzen der beiden unwahrscheinlichsten Knoten den optimalen Präfixbaum konstruiert. Das strukturelle Manko der Huffman-Codierung besteht jedoch darin, dass jedes Codewort eine ganzzahlige Bitlänge $\ell_i \ge 1$ besitzen muss. Tritt ein Symbol mit $p_1 = 0{,}99$ auf, beträgt sein wahrer Informationsgehalt nur $-\log_2(0{,}99) \approx 0{,}0145\,\text{Bits}$, doch ein Huffman-Code muss dafür mindestens $1\,\text{volles Bit}$ ausgeben – ein fast 69-facher Overhead!

3.2 Arithmetische Codierung (Arithmetic / Range Coding): Gebrochene Bits

Die Arithmetische Codierung (Rissanen, Pasco, Witten et al.) überwindet die Ganzzahligkeitsschranke, indem sie die gesamte Nachrichtenfolge $x_1 x_2 \dots x_N$ auf ein einziges Teilintervall $[L_{\text{low}}, H_{\text{high}}) \subset [0, 1)$ abbildet. Mit jedem Symbol $x_t$ schrumpft die Intervallbreite um den Faktor $P(x_t)$, sodass das finale Intervall die Breite $\Delta = \prod_{t=1}^N P(x_t)$ besitzt und durch $\lceil -\log_2 \Delta \rceil + 1 \approx N \cdot H(X)$ Bits kodiert werden kann. Dies erreicht gebrochene Bitraten beliebig nahe an der Shannon-Entropie, erfordert jedoch rechenintensive Multiplikationen und Renormierungen pro Symbol.

3.3 Asymmetric Numeral Systems (ANS, Jarek Duda 2009–2014)

Zwischen 2009 und 2014 revolutionierte der polnische Physiker und Informatiker Jarek Duda die Datenkompression mit den Asymmetric Numeral Systems (tANS und rANS). Während das klassische Binärsystem beim Anhängen eines gleichverteilten Bits $b \in \{0,1\}$ den Zustand $x \in \mathbb{N}$ gemäß $x' = 2x + b$ verdoppelt ($2 = 1/P(b)$), skaliert ANS den Zustand $x$ beim Codieren eines Symbols $s$ der Wahrscheinlichkeit $p_s$ gemäß:

Durch vorberechnete Zustandsübergangstabellen (tANS / Finite State Entropy) vereint ANS die exakte Kompressionsrate der Arithmetischen Codierung (gebrochene Bits) mit der extremen Tabellengeschwindigkeit der Huffman-Codierung! Heute bildet ANS das Herzstück von Facebook/Meta Zstandard (zstd), Apple LZFSE und Google JPEG XL.

4. Wörterbuch-Kompression und Transformationen: LZ77, DEFLATE, BWT und „Kompression als Vorhersage“

Da natürliche Sprache und Quellcode starke Kontextabhängigkeiten und wiederkehrende Teilstrings aufweisen, kombiniert man Entropiecodierer mit Wörterbuch- und Transformationsverfahren:

• LZ77 (Lempel & Ziv, 1977): Durchsucht ein gleitendes Fenster (Sliding Window) der bereits verarbeiteten Daten nach wiederholten Teilstrings und ersetzt diese durch kompakte Rückwärtsverweise (distance, length). Zusammen mit Huffman-Codierung ergibt dies DEFLATE (gzip, zip, PNG), zusammen mit ANS ergibt es Zstandard (zstd).
• Burrows-Wheeler-Transformation (BWT, 1994, bzip2): Sortiert alle zyklischen Verschiebungen eines Datenblocks lexikographisch. Die letzte Spalte $L$ dieser Matrix ist bemerkenswerterweise umkehrbar und gruppiert Zeichen mit identischem nachfolgendem Kontext direkt nebeneinander, sodass Move-To-Front (MTF) und Lauflängencodierung (RLE) enorme Kompressionsgewinne erzielen.

  flowchart TD
    A["Eingabe-Bytestrom"] --> B["Suche nach längster Übereinstimmung im Sliding Window (Hash-Kette / Suffixbaum)"]
    B --> C{"Match-Länge >= 3 gefunden?"}
    C -- "Ja" --> D["Ausgabe eines Rückwärtszeigers (distance, length)"]
    C -- "Nein" --> E["Ausgabe des Roh-Zeichens (Literal)"]
    D --> F["Entropiecodierung via Huffman (DEFLATE) oder ANS (Zstandard)"]
    E --> F

Auf fundamentaler Ebene gilt die Äquivalenz „Kompression ist Vorhersage“: Ein Modell (wie ein modernes Large Language Model), das die bedingte Wahrscheinlichkeit $P_\theta(x_t \mid x_{