📚

LZW-Komprimierung

Wiederkehrende Zeichenfolgen landen in einem Wörterbuch – danach reicht ein kurzer Verweis. Codiere und decodiere Texte und Pixelbilder mit dem Verfahren von Lempel, Ziv und Welch, Schritt für Schritt von Hand oder automatisch.

Daten & Codierung – Kursstufe

🎯 Worum geht's? Klasse 11–13 · 2 Unterrichtsstunden

Nach dieser Seite kannst du …

einen Text oder ein Pixelbild mit dem LZW-Verfahren codieren und dabei das Wörterbuch aufbauen
eine LZW-Codefolge decodieren und erklären, warum der Empfänger dasselbe Wörterbuch selbst erzeugt
den Sonderfall beim Decodieren erkennen (Code steht noch nicht im Wörterbuch) und lösen
die Kompression berechnen und begründen, wann LZW Daten sogar länger macht

Vorwissen: ASCII-Codierung, Hexadezimalzahlen, Bits und Bytes; hilfreich: Huffman-Codierung

📚 Die Idee: ein Wörterbuch, das mitwächst

Das LZW-Verfahren ist nach Abraham Lempel, Jakob Ziv und Terry Welch benannt (1984). Es ist ein Wörterbuchverfahren: Zeichenfolgen, die sich wiederholen, werden in einem Wörterbuch hinterlegt. Taucht eine solche Folge wieder auf, reicht ein Verweis auf ihren Eintrag – ein einziger Code für mehrere Zeichen.

Der Clou: Das Wörterbuch wird während des Codierens aufgebaut – und beim Decodieren genauso wieder. Es muss deshalb nicht mitgeschickt werden (anders als der Baum bei der Huffman-Codierung). Sender und Empfänger müssen sich nur auf das Startwörterbuch einigen.

Startwörterbuch beim Text

Üblich sind 12 Bit je Code: Das Wörterbuch hat 2¹² = 4096 Plätze. Die ersten 256 (000–0FF, hexadezimal) sind fest mit den 8-Bit-Zeichen belegt, z. B. 041 = A, 042 = B. Neue Einträge bekommen die Nummern ab 100.

Bei Aufgaben von Hand nimmt man oft ein kleines Startwörterbuch nur mit den vorkommenden Buchstaben, z. B. a = 1, b = 2, c = 3 – neue Einträge ab 4.

Startwörterbuch beim Pixelbild

Das Bild wird Zeile für Zeile gelesen und jede Farbe durch ihre Nummer ersetzt. Bei 4 Farben stehen 0–3 im Startwörterbuch, neue Einträge ab 4. Wiederkehrende Farbmuster werden so zu einzelnen Codes.

Beispielbild (Idee: Uni Köln): 16 Pixel, gelesen als 0120 1201 2012 0123.

🔐 Codieren

Lies eine möglichst lange Zeichenkette ein, die schon im Wörterbuch steht. Zu Beginn ist das immer nur ein einzelnes Zeichen.
Schreibe den Code dieses Eintrags in die Ausgabe.
Lege aus der gefundenen Zeichenkette und dem nächsten Zeichen einen neuen Wörterbucheintrag an (nächste freie Nummer).
Mach beim nächsten Zeichen weiter, bis alles gelesen ist.

Beispiel: „BABAABBAA“ mit ASCII-Startwörterbuch (Codes hexadezimal):

Noch zu bearbeiten	Gefundener Eintrag	Ausgabe (12 Bit)	Neuer Eintrag
BABAABBAA	B ← 042	042	BA → 100
ABAABBAA	A ← 041	041	AB → 101
BAABBAA	BA ← 100	100	BAA → 102
ABBAA	AB ← 101	101	ABB → 103
BAA	BAA ← 102	102	– (Ende)

Ergebnis: 042 041 100 101 102 – 5 Codes zu 12 Bit = 60 Bit = 7,5 Byte, aufgefüllt auf 8 Byte. Das Original hatte 9 Zeichen zu 8 Bit = 9 Byte.

Algorithmus als Pseudocode

// Eingabe: Text T = t1 … tn über dem Alphabet Σ
// Ausgabe: LZW-Codierung von T
Initialisiere Wörterbuch D mit den Zeichen aus Σ
s = t1
solange noch nicht alle Zeichen von T gelesen sind:
    lies nächstes Zeichen c
    falls s + c in D steht:
        s = s + c          // weiterlesen, noch keine Ausgabe
    sonst:
        gib Code(s) aus
        trage s + c in D ein
        s = c
gib Code(s) aus

🔓 Decodieren

Der Empfänger liest die Codes nacheinander, schlägt sie im Wörterbuch nach und gibt die Zeichenkette aus. Dabei baut er dasselbe Wörterbuch auf – allerdings einen Schritt später: Ein neuer Eintrag besteht aus dem vorherigen Eintrag + dem ersten Zeichen des aktuellen Eintrags.

Code	Gefundener Eintrag (erstes Zeichen)	Neuer Eintrag	Ausgabe
042	B (B)	– (noch kein vorheriger)	B
041	A (A)	B + A = BA → 100	A
100	BA (B)	A + B = AB → 101	BA
101	AB (A)	BA + A = BAA → 102	AB
102	BAA (B)	AB + B = ABB → 103	BAA

Ergebnis: „BABAABBAA“ – mit genau den Wörterbucheinträgen, die auch der Codierer hatte.

Algorithmus als Pseudocode (mit Sonderfall)

// Eingabe: Folge von Codes;  Ausgabe: Zeichenfolge über Σ
// lc: letzter Code, ac: aktueller Code, string(x): Zeichen zu Code x
Initialisiere Wörterbuch D mit den Zeichen aus Σ
lies lc und gib string(lc) aus
solange noch nicht alle Codes gelesen sind:
    lies nächsten Code ac
    falls ac nicht in D steht:                       // Sonderfall
        trage string(lc) + erstesZeichen(string(lc)) in D ein
        gib string(lc) + erstesZeichen(string(lc)) aus
    sonst:
        trage string(lc) + erstesZeichen(string(ac)) in D ein
        gib string(ac) aus
    lc = ac

⚠️ Die Sonderfälle

1. Der Code steht beim Decodieren noch nicht im Wörterbuch

Das ist der Sonderfall des LZW-Verfahrens. Beispiel „bababab“ mit a = 1, b = 2:

Codieren

b → Ausgabe 2, neu: ba = 3
a → Ausgabe 1, neu: ab = 4
ba → Ausgabe 3, neu: bab = 5
bab → Ausgabe 5 – gerade erst angelegt!

Codefolge: 2 1 3 5

Decodieren

2 → b
1 → a, neu: ba = 3
3 → ba, neu: ab = 4
5 → steht noch nicht im Wörterbuch!

Warum passiert das? Der Codierer legt einen Eintrag an und benutzt ihn sofort im nächsten Schritt. Der Decodierer ist aber immer einen Schritt hinterher: Er kann Eintrag 5 erst vervollständigen, wenn er den Code danach kennt – und das ist hier Code 5 selbst.

Die Lösung: Eintrag 5 entsteht aus dem vorherigen Eintrag „ba“ und einem noch unbekannten Zeichen: 5 = „ba?“. Dieses „?“ ist das erste Zeichen von Eintrag 5 – und Eintrag 5 beginnt ja mit „ba“, also mit „b“. Damit ist 5 = „bab“.

Merke: Steht ein Code noch nicht im Wörterbuch, dann ist er immer genau der Eintrag, der gerade entsteht: vorheriger Eintrag + dessen erstes Zeichen. Jeder andere unbekannte Code wäre ein Übertragungsfehler.

Der Sonderfall tritt auf, wenn sich ein Muster der Form Zeichen–Folge–Zeichen–Folge–Zeichen direkt wiederholt, besonders oft bei langen gleichen Stücken (aaaa…, einfarbige Bildflächen). Aufgabe vom Arbeitsblatt: 042 041 100 101 041 104 – hier ist 104 der Sonderfall:

Code	Gefundener Eintrag	Neuer Eintrag	Ausgabe
042	B	–	B
041	A	BA → 100	A
100	BA	AB → 101	BA
101	AB	BAA → 102	AB
041	A	ABA → 103	A
104	fehlt! A + A = AA	AA → 104	AA

Ergebnis: „BABAABAAA“. Probiere es im Reiter Decodieren mit den Beispielen „Sonderfall“ aus.

2. Der erste Code bringt keinen neuen Eintrag

Beim Decodieren fehlt am Anfang ein „vorheriger Eintrag“. Der erste Code wird nur ausgegeben; der erste neue Eintrag entsteht erst mit dem zweiten Code. Deshalb ist der Decodierer bis zum Schluss einen Schritt hinter dem Codierer – und genau daraus entsteht Sonderfall 1.

3. Das Ende der Daten

Beim Codieren gibt es für die letzte gefundene Zeichenkette keinen neuen Eintrag mehr – es folgt ja kein Zeichen.
Die Codes werden lückenlos hintereinander geschrieben. 12-Bit-Codes ergeben anderthalb Byte; bei einer ungeraden Anzahl Codes wird das letzte Byte mit 4 Nullbits aufgefüllt (7,5 Byte → 8 Byte).

4. Das Wörterbuch ist voll

Mit 12 Bit gibt es nur 4096 Einträge. Bei langen Dateien ist das Wörterbuch irgendwann voll. Übliche Lösungen:

Einfrieren: keine neuen Einträge mehr, nur noch die vorhandenen nutzen.
Zurücksetzen: Ein besonderer Clear-Code sagt dem Empfänger „Wörterbuch neu beginnen“ (so bei GIF).
Variable Codelänge: Mit 9 Bit beginnen und erst wachsen, wenn das Wörterbuch größer wird (GIF, TIFF) – das spart am Anfang Platz.

Sender und Empfänger müssen dieselbe Regel verwenden, sonst laufen ihre Wörterbücher auseinander.

5. LZW kann Daten länger machen

Jeder Code braucht 12 Bit, ein Zeichen nur 8 Bit. Gibt es kaum Wiederholungen, wird die Ausgabe länger: „ABC“ hat 3 Byte, als LZW 3 × 12 Bit = 4,5 → 5 Byte. LZW lohnt sich erst bei längeren Daten mit vielen Wiederholungen. In der Praxis wurden 16-Bit-TIFF-Bilder mit LZW sogar größer als ohne Komprimierung (Tabelle unten).

6. Zeichen außerhalb des Startwörterbuchs

Was nicht im Startwörterbuch steht, kann nicht codiert werden – z. B. „€“ oder Emojis, die nicht zu den 256 8-Bit-Zeichen gehören. Echte Programme arbeiten deshalb mit Bytes statt Zeichen.
„a“ und „A“ sind verschiedene Zeichen mit verschiedenen Codes.
Beide Seiten brauchen dasselbe Startwörterbuch: 2 1 3 bedeutet mit a = 1, b = 2 etwas völlig anderes als mit ASCII-Codes.

🖼️ Pixelgrafiken

Das Beispielbild oben hat 4 Farben (0 = hellblau, 1 = rot, 2 = grün, 3 = gelb). Zeile für Zeile gelesen ergibt sich 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 3. LZW macht daraus 0 1 2 4 6 5 7 7 3 – 9 Codes statt 16 Pixel – mit diesen Einträgen:

Code	Eintrag	Code	Eintrag

Grafikformate wie GIF und TIFF nutzen genau dieses Verfahren. Bilder mit großen einfarbigen Flächen und wiederkehrenden Mustern (Grafiken, Logos, Screenshots) werden stark verkleinert, Fotos mit Rauschen kaum.

🌍 Blick in die reale Welt

GIF (1987) und TIFF komprimieren Bilder mit LZW, früher auch das Unix-Programm compress und PDF.
LZW war patentiert (Unisys). Weil Lizenzgebühren für GIF verlangt wurden, entstand das Format PNG, das stattdessen Deflate nutzt (LZ77 + Huffman) – wie auch ZIP.

Dateigrößen von vier Fotos als TIFF (Quelle: havecamerawilltravel.com, „TIFF Image Compression“):

TIFF	Bild 1	Bild 2	Bild 3	Bild 4
8 Bit, ohne	35,3 MB	35,3 MB	35,3 MB	35,3 MB
8 Bit, LZW	12,9 MB	11,5 MB	22,5 MB	12,3 MB
8 Bit, ZIP	12,6 MB	11,6 MB	20,2 MB	12,0 MB
16 Bit, ohne	70,6 MB	70,6 MB	70,6 MB	70,6 MB
16 Bit, LZW	87,0 MB	76,2 MB	87,5 MB	70,9 MB
16 Bit, ZIP	54,3 MB	53,6 MB	61,9 MB	55,3 MB

Bei 16 Bit je Farbkanal wiederholen sich kaum Byte-Folgen (feines Rauschen) – LZW macht die Dateien größer (Sonderfall 5).