Wie Dateikomprimierung wirklich funktioniert: Huffman Coding, LZ77 und DEFLATE erklärt

Jeder Entwickler hat schon mit komprimierten Dateien gearbeitet. Man entpackt ein Paket, liefert eine gzip-kodierte Antwort aus oder exportiert ein PNG — und dabei läuft Komprimierung im Hintergrund ab. Doch die Frage, die die meisten Tutorials überspringen, lautet: Warum funktioniert das? Warum kann man eine 500-KB-Textdatei auf 180 KB reduzieren, ohne ein einziges Byte zu verlieren, aber eine ZIP-Datei lässt sich kaum weiter komprimieren?

Die Antwort liegt in der Informationstheorie und einer Handvoll eleganter Algorithmen. Dieser Artikel durchleuchtet die echten Mechanismen: von der Shannon-Entropie über Huffman-Bäume bis hin zum DEFLATE-Format, das ZIP, gzip und PNG zugrundeliegt.

Warum Dateien komprimierbar sind

Dateien sind komprimierbar, weil sie Redundanz enthalten — Muster, Wiederholungen und vorhersehbare Sequenzen, die weniger Information tragen, als ihre rohe Byteanzahl vermuten lässt.

Betrachte ein einfaches Beispiel. Die Zeichenkette AAAAAAAAAA (zehn A) belegt in ASCII 10 Byte. Der Informationsgehalt ist jedoch trivial: Man könnte sie perfekt als „zehn A" beschreiben. Ein Komprimierungsalgorithmus tut genau das — er ersetzt ausführliche, redundante Daten durch eine kürzere Beschreibung.

Echte Dateien sind voll solcher Redundanz:

• Deutschsprachiger Text verwendet ständig häufige Wörter und Buchstabenkombinationen. „dass", „ung", „keit" kommen weit öfter vor als „xqz".
• Quellcode hat eine tief repetitive Struktur: function, return, const, Einrückungszeilen, Leerzeilen.
• Bitmap-Bilder enthalten lange horizontale Läufe identischer oder nahezu identischer Pixel — besonders in Farbflächen.
• Log-Dateien wiederholen Zeitstempel, Hostnamen und Statuscodes tausende Male.

Je redundanter die Daten, desto besser komprimierbar. Je weniger redundant — je zufälliger — desto schwieriger die Komprimierung.

Entropie: Die harte Grenze der Komprimierung

Claude Shannons Paper von 1948, A Mathematical Theory of Communication, führte eine präzise Methode zur Messung des Informationsgehalts ein: die Entropie, gemessen in Bits.

Die Shannon-Entropie beantwortet die Frage: Wie viele Bits braucht man durchschnittlich, um ein Symbol dieser Datenquelle darzustellen?

Die Formel für eine Quelle mit Symbolen s₁, s₂, ..., sₙ und Wahrscheinlichkeiten p₁, p₂, ..., pₙ lautet:

H = -Σ pᵢ × log₂(pᵢ)

In der Praxis bedeutet das: Angenommen, eine Datei enthält nur zwei Zeichen — A (90 % der Zeit) und B (10 % der Zeit).

H = -(0.9 × log₂(0.9)) - (0.1 × log₂(0.1))
H = -(0.9 × -0.152) - (0.1 × -3.322)
H ≈ 0.137 + 0.332
H ≈ 0.469 Bits pro Symbol

Eine naive Kodierung verwendet 1 Bit pro Symbol (0 für A, 1 für B). Die Entropie sagt jedoch, dass das theoretische Minimum 0,469 Bits pro Symbol beträgt — weniger als die Hälfte. Ein guter Komprimierungsalgorithmus kommt diesem Limit nahe.

Betrachte nun eine wirklich zufällige Datei, in der jeder Bytewert (0–255) mit gleicher Wahrscheinlichkeit (je 1/256) vorkommt:

H = -(256 × (1/256) × log₂(1/256))
H = log₂(256) = 8 Bits pro Byte

Acht Bits pro Byte — maximale Entropie. Es gibt keine Redundanz auszunutzen. Deshalb lässt sich eine ZIP-Datei nicht weiter komprimieren: Sie liegt bereits nahe an der maximalen Entropie. Jedes Bit trägt Information; es bleiben keine Muster übrig, die eliminiert werden könnten.

Lauflängenkodierung: Die einfachste Form

Bevor wir zu den schwereren Algorithmen kommen, illustriert die Lauflängenkodierung (RLE) die Kernidee anschaulich.

RLE ersetzt eine Folge wiederholter Symbole durch einen Zähler und das Symbol:

Original:  AAABBBBBCCDDDDDD
RLE:       3A 5B 2C 6D

Original: 16 Zeichen. Kodiert: 8 Zeichen. 50 % Einsparung.

RLE wird bei der Faxübertragung (CCITT Gruppe 3/4), in BMP-Dateien und als Teilschritt innerhalb komplexerer Formate eingesetzt. Die Schwäche liegt auf der Hand: Bei Daten ohne lange Läufe versagt RLE. Die Zeichenkette ABABABAB hat keine Läufe, weshalb RLE sie durch das Voranstellen von Zählern (je 1) sogar vergrößert.

Genau diese Schwäche treibt die Entwicklung ausgefeilterer Ansätze voran.

Huffman Coding: Kürzere Codes für häufige Symbole

Im Standard-ASCII erhält jedes Zeichen 8 Bits, unabhängig von seiner Häufigkeit. Huffman Coding bricht diese Annahme auf. Häufige Symbole erhalten kürzere Codes; seltene Symbole erhalten längere Codes. Die durchschnittliche Codelänge sinkt, und die Datei schrumpft.

Einen Huffman-Baum aufbauen

Nehmen wir die Zeichenkette AABBBCCCC (9 Zeichen). Häufigkeiten zählen:

Schritt 1. Jedes Symbol in einen Blattknoten mit seinem Gewicht (Häufigkeit) einsetzen.

[A:2]  [B:3]  [C:4]

Schritt 2. Die beiden leichtesten Knoten wiederholt zu einem Elternknoten zusammenfassen, dessen Gewicht deren Summe ist — bis nur noch ein Baum übrig bleibt.

Zusammenfassen von [A:2] und [B:3] → Elternknoten [AB:5]:

      [AB:5]
      /     \
   [A:2]  [B:3]

[C:4]

Zusammenfassen von [C:4] und [AB:5] → Wurzel [ABC:9]:

         [ABC:9]
         /      \
      [C:4]  [AB:5]
              /    \
           [A:2]  [B:3]

Schritt 3. Codes durch Baumtraversierung vergeben: linke Kante = 0, rechte Kante = 1.

Die Biteinsparung berechnen

Mit Huffman-Codes kostet die Kodierung von AABBBCCCC:

A × 2 Vorkommen × 2 Bits = 4 Bits
B × 3 Vorkommen × 2 Bits = 6 Bits
C × 4 Vorkommen × 1 Bit  = 4 Bits
Gesamt = 14 Bits

Mit festem 8-Bit-ASCII:

9 Zeichen × 8 Bits = 72 Bits

14 Bits gegenüber 72 Bits — eine Einsparung von 81 % in diesem Spielzeugbeispiel. Reale Gewinne sind kleiner, das Prinzip bleibt aber dasselbe. Deutschsprachiger Text komprimiert sich mit Huffman allein typischerweise auf 4–5 Bits pro Zeichen, ausgehend von 8.

Der entscheidende Gedanke: Huffman-Codes sind präfixfrei. Kein Code ist Präfix eines anderen, weshalb ein Decoder den ursprünglichen Datenstrom eindeutig ohne Trennzeichen rekonstruieren kann. Die Baumstruktur selbst wird im Datei-Header gespeichert, damit der Decoder sie nachbauen kann.

LZ77 und LZ78: Wiederholte Sequenzen ausnutzen

Huffman Coding arbeitet auf Ebene der Einzelsymbol-Häufigkeiten. Es übersieht jedoch eine größere Klasse von Redundanz: wiederholte Sequenzen. Das Schlüsselwort function im Quellcode umfasst 8 Bytes bei jedem Auftreten. Wenn man das zweite und jedes weitere Vorkommen durch einen Rückwärtsverweis auf das erste ersetzen könnte, wären erhebliche Einsparungen möglich.

Genau das beschrieben Abraham Lempel und Jacob Ziv in ihren Papers von 1977 und 1978 — und schufen damit LZ77 und LZ78.

LZ77: Schiebefensterkomprimierung

LZ77 pflegt ein Schiebefenster — einen Puffer kürzlich gesehener Daten. Beim Verarbeiten neuer Daten sucht der Codierer rückwärts durch das Fenster nach der längsten Übereinstimmung mit dem, was als nächstes kommt. Findet er eine, sendet er einen Rückwärtsverweis (Offset, Länge) anstelle der wörtlichen Bytes.

Betrachten wir die Kodierung der Zeichenkette:

abcabc

Verarbeitung von abc: kein vorheriger Verlauf, Literale a, b, c werden ausgegeben.

Verarbeitung des zweiten abc: Der Codierer schaut zurück und findet abc ab 3 Positionen zuvor, mit Länge 3. Er sendet den Rückwärtsverweis (Offset=3, Länge=3) anstelle von drei wörtlichen Bytes.

Der Decoder sieht (3, 3), geht 3 Positionen in seinem Ausgabepuffer zurück und kopiert 3 Bytes — abc wird perfekt rekonstruiert.

In einer echten Implementierung ist die Suchtiefe durch die Fenstergröße begrenzt (gzip verwendet ein 32-KB-Fenster). Ein größeres Fenster findet mehr Übereinstimmungen, benötigt aber mehr Arbeitsspeicher und Suchzeit.

Der Rückwärtsverweis (Offset, Länge) umfasst typischerweise 2–3 Bytes. Eine wiederholte 10-Byte-Sequenz durch einen 2-Byte-Verweis zu ersetzen spart also 8 Bytes. Je länger die Übereinstimmung, desto besser das Verhältnis.

LZ78 und LZW

LZ78 baut ein explizites Wörterbuch gefundener Muster auf, anstatt ein Schiebefenster zu verwenden. LZW (Lempel-Ziv-Welch), ein Derivat davon, wurde als Algorithmus hinter der GIF-Komprimierung und dem Unix-Dienstprogramm compress bekannt. LZW kodiert Muster als einzelne Wörterbuchindizes und lässt das Wörterbuch während der Kodierung und Dekodierung dynamisch wachsen.

DEFLATE: LZ77 plus Huffman Coding

DEFLATE, definiert in RFC 1951, kombiniert LZ77 und Huffman Coding in Folge:

1. LZ77-Durchlauf: Wiederholte Sequenzen werden durch Rückwärtsverweise (Offset, Länge) ersetzt. Die Ausgabe ist ein Strom aus Literalen und Rückwärtsverweisen.
2. Huffman-Durchlauf: Auf diesen Strom wird Huffman Coding angewendet. Häufige Literale erhalten kurze Codes; seltene Rückwärtsverweis-Werte erhalten längere Codes.

Beide Techniken greifen verschiedene Arten von Redundanz an. LZ77 beseitigt Langstrecken-Wiederholungen. Huffman Coding beseitigt dann die häufigkeitsbasierte Redundanz im Verbleibenden. Zusammen erreichen sie Kompressionsverhältnisse, die keiner der Algorithmen allein erzielen könnte.

DEFLATE-Daten sind in Blöcke aufgeteilt. Jeder Block kann einen von drei Modi nutzen:

• Keine Komprimierung — für Daten, bei denen Komprimierung die Ausgabe vergrößern würde (bereits zufällige Daten)
• Feste Huffman-Codes — eine vorab vereinbarte Codetabelle, die den Overhead des Speicherns eines eigenen Baums einspart
• Dynamische Huffman-Codes — ein eigener, für diesen Block optimierter Baum, der im Block-Header gespeichert wird

Der dynamische Modus wird für die meisten komprimierbaren Daten verwendet. Der Codierer analysiert den Block, baut einen optimalen Huffman-Baum, speichert ihn am Blockanfang und kodiert die Daten dann mit diesem Baum.

Wo DEFLATE in echten Dateiformaten steckt

ZIP

ZIP-Dateien speichern jeden Eintrag unabhängig mit seinem eigenen DEFLATE-komprimierten Datenstrom. Diese Einzeleintrags-Komprimierung ermöglicht es, eine einzelne Datei aus einem ZIP zu extrahieren, ohne das gesamte Archiv zu dekomprimieren. Das ZIP-Format unterstützt außerdem einen „Gespeichert"-Modus (keine Komprimierung) für bereits komprimierte Dateien.

gzip

gzip hüllt einen einzelnen DEFLATE-Datenstrom in einen Header (Magic Number, Betriebssystem, Änderungszeit) und eine CRC32-Prüfsumme. Es ist das Standard-Komprimierungsformat für HTTP Content-Encoding: gzip und für .tar.gz-Archive. Die Erweiterung .gz ist stets ein einzelner DEFLATE-Datenstrom.

PNG

PNG verwendet DEFLATE (über zlib), um seine Pixeldaten zu komprimieren. Vor der Komprimierung wendet PNG einen Filterschritt an: Jede Pixelzeile wird in Differenzen zu einer Vorhersage umgewandelt (Delta-Kodierung). Das steigert die Läufe und Wiederholungen, die LZ77 ausnutzen kann, erheblich und verbessert die Komprimierung merklich. Bei typischen Screenshots und Diagrammen komprimiert PNG auf 20–50 % der rohen Pixeldatengröße. Bildkomprimierungs-tools, die PNG exportieren, verlassen sich auf diese Verarbeitungskette.

zlib

zlib ist ein Hüllformat um DEFLATE — es fügt einen Zwei-Byte-Header und eine Adler-32-Prüfsumme hinzu. PDF-Streams verwenden zlib/DEFLATE beim Komprimieren eingebetteter Inhalte (PDF-Komprimierung reduziert die Dateigröße durch Neukomprimierung oder Entfernung dieser Streams). HTTP, WebSockets und viele Netzwerkprotokolle nutzen ebenfalls zlib.

JPEG: Ein anderer Ansatz

Es lohnt sich, hier innezuhalten, denn JPEG verwendet eine völlig andere Komprimierungsstrategie — eine, die absichtlich Daten verliert.

JPEG wendet eine Diskrete Kosinustransformation (DCT) auf 8×8-Pixel-Blöcke an. Die DCT wandelt Pixelwerte in Frequenzkomponenten um (ähnlich einer Fourier-Transformation). Hochfrequente Komponenten — Feindetails — werden dann aggressiv quantisiert (auf gröbere Werte gerundet oder vollständig verworfen). Die verbleibenden Koeffizienten werden mit Huffman Coding kodiert, aber der verlustbehaftete Quantisierungsschritt macht JPEG so viel kleiner als PNG bei Fotografien.

Der Kompromiss: JPEG kann die ursprünglichen Pixel nicht perfekt rekonstruieren. PNG schon. Dies ist der verlustbehaftete vs. verlustfreie Unterschied, der in unserem Artikel zur verlustbehafteten vs. verlustfreien Dateikonvertierung ausführlich behandelt wird.

Bei einer Fotografie kann JPEG mit Qualitätsstufe 80 nur 10 % der Bytes eines verlustfreien PNG benötigen. Bei einem Screenshot mit flachen Farben und scharfen Kanten gewinnt PNG in der Regel, weil DCT-Artefakte sichtbar sind und DEFLATE flache Bereiche außerordentlich gut komprimiert.

Warum man eine ZIP-Datei nicht weiter komprimieren kann

Das ist eine häufige Quelle der Verwirrung. Wenn Komprimierung durch das Finden von Mustern funktioniert, warum ergibt das Komprimieren einer bereits komprimierten Datei fast nichts?

Weil DEFLATE seinen Job korrekt macht. Ein gut komprimierter DEFLATE-Datenstrom sieht statistisch zufällig aus — by Design. Die Rückwärtsverweise und Huffman-Codes beseitigen die vorhersehbaren Muster. Was übrig bleibt, liegt nahe an der Entropiegrenze der Daten.

Ein zweiter Kompressor findet keine Läufe (LZ77 findet keine langen Übereinstimmungen) und keinen Häufigkeitsbias (Huffman sieht eine nahezu gleichmäßige Symbolverteilung). Die Entropie liegt bereits bei 7,9+ Bits pro Byte. Es bleibt nichts mehr auszunutzen.

Deshalb sollte man niemals bereits komprimierte Mediendateien erneut komprimieren. Ein JPEG in eine ZIP-Datei zu verpacken kostet den ZIP-Overhead ohne Größengewinn. Dasselbe gilt für MP3, MP4, HEIC — alles komprimierte Formate, die bereits nahe an ihrer Entropiedecke liegen.

Algorithmen im Vergleich

Alles zusammenfügen

Die Kette von Rohdaten zu komprimierten Bytes sieht für eine gzip-komprimierte Datei so aus:

1. Eingabe: Roher Byte-Datenstrom (z. B. eine Textdatei)
2. LZ77: Suche nach Rückwärtsverweisen mit einem 32-KB-Schiebefenster, Ausgabe eines Stroms aus Literalen und (Offset, Länge)-Paaren
3. Huffman Coding: Aufbau zweier Bäume — einer für Literale/Längen, einer für Offsets — und Kodierung der LZ77-Ausgabe
4. DEFLATE-Blöcke: Huffman-Bäume und kodierte Daten in einen oder mehrere Blöcke verpacken
5. gzip-Hülle: gzip-Header voranstellen, CRC32 und ursprüngliche Dateigröße anhängen
6. Ausgabe: .gz-Datei, bei komprimierbarer Eingabe typischerweise 30–70 % kleiner

Die Dekomprimierung läuft streng umgekehrt ab: gzip-Header parsen, Huffman-Bäume aus Block-Headern einlesen und rekonstruieren, den Huffman-Datenstrom in LZ77-Token rückdekodieren, Rückwärtsverweise anwenden, um den ursprünglichen Byte-Datenstrom zu rekonstruieren. Die Dekomprimierung ist stets schneller als die Komprimierung, weil die schwere Arbeit (Suche nach optimalen Übereinstimmungen, Aufbau optimaler Bäume) nur einmal stattfindet.

Wichtigste Erkenntnisse

• Dateien sind komprimierbar, weil sie Redundanz enthalten — wiederholte Muster und verzerrte Symbolhäufigkeiten.
• Die Shannon-Entropie setzt den absoluten Boden: Wirklich zufällige Daten lassen sich nicht komprimieren, weil jedes Bit bereits Information trägt.
• RLE behandelt Wiederholungen primitiv. Huffman Coding behandelt Häufigkeitsverzerrungen elegant. LZ77 behandelt Langstrecken-Sequenzwiederholungen.
• DEFLATE kettet LZ77 und Huffman in Folge, weshalb es jeden der Algorithmen einzeln übertrifft. Es ist der Motor in ZIP, gzip, PNG und zlib-komprimierten PDF-Streams.
• JPEG verfolgt einen grundlegend anderen Ansatz: verlustbehaftete DCT-Quantisierung gefolgt von verlustfreiem Huffman, Pixelgenauigkeit gegen dramatische Größenreduktion eintauschen.
• Das Komprimieren einer komprimierten Datei bringt nichts, weil gute Komprimierung eine Ausgabe nahe maximaler Entropie erzeugt.

Diese Algorithmen zu kennen hilft beim Auswählen eines Formats, beim Diagnostizieren unerwarteter Dateigrößen oder beim Debuggen einer Kompressions-Pipeline. Beim nächsten Mal, wenn du PDF-Komprimierung verwendest, eine ZIP-Datei entpackst oder ein PNG für die Bildkomprimierung exportierst, weißt du genau, was die Software mit deinen Bits macht.