LZW-Kompression
LZW (Lempel-Ziv-Welch) ist ein verlustfreies Wörterbuch-Kompressionsverfahren, das 1984 von Terry Welch aus den Verfahren LZ78 von Abraham Lempel und Jacob Ziv weiterentwickelt wurde. Es ist das Kompressionsverfahren hinter GIF (und optional TIFF/PDF).
Die Grundidee: Wiederkehrende Folgen von Zeichen werden durch kurze Zahlencodes ersetzt. Das Besondere an LZW ist, dass das Wörterbuch nicht mitgespeichert werden muss — Encoder und Decoder bauen es während des Lesens nach exakt denselben Regeln Schritt für Schritt selbst auf.
Gestartet wird mit einem Wörterbuch, das bereits alle einzelnen Symbole enthält (bei GIF die Paletten-Indizes). Während der Verarbeitung kommen immer längere Zeichenketten hinzu — je öfter sich Muster wiederholen, desto stärker die Kompression.
⚙️ So funktioniert der Algorithmus
Der Encoder verlängert ein Muster w so lange, wie es im Wörterbuch existiert. Sobald w + k unbekannt ist, wird der Code für w ausgegeben und w + k neu aufgenommen.
ENCODER (Kodierung):
┌──────────────────────────────────────────────────────────┐
│ w = leer │
│ für jedes Zeichen k im Eingabestrom: │
│ wenn (w + k) im Wörterbuch: │
│ w = w + k ← Muster verlängern │
│ sonst: │
│ gib code(w) aus ← bekannten Teil ausgeben │
│ füge (w + k) neu ins Wörterbuch ein │
│ w = k │
│ gib code(w) aus │
└──────────────────────────────────────────────────────────┘
Eingabe "ABABABA"
│
▼
┌─────────────────┐ Codes ┌─────────────────┐
│ Wörterbuch baut │ ───────────────▶│ kompakter │
│ sich dynamisch │ 65,66,256,258 │ Code-Strom │
│ auf (256, 257…) │ │ │
└─────────────────┘ └─────────────────┘🔢 Schritt-für-Schritt-Beispiel
Eingabe "ABABABA": Beobachte, wie das Wörterbuch wächst und die Ausgabe kürzer wird als die Eingabe.
Beispiel: Kodierung von „ABABABA“ (Start-Wörterbuch: A=65, B=66)
| Schritt | w | k | w+k bekannt? | Ausgabe | neuer Eintrag |
|---|---|---|---|---|---|
| 1 | A | B | nein | 65 (A) | AB = 256 |
| 2 | B | A | nein | 66 (B) | BA = 257 |
| 3 | A | B | ja | — | — |
| 4 | AB | A | nein | 256 (AB) | ABA = 258 |
| 5 | A | B | ja | — | — |
| 6 | AB | A | ja | — | — |
| 7 | ABA | ⓔ | Ende | 258 (ABA) | — |
🎬 Visueller Ablauf
Dieselbe Eingabe live durchgespielt: Grün = Muster verlängern, Blau = Code ausgeben & neuen Eintrag anlegen.
Aufgebautes Wörterbuch: AB=256BA=257ABA=258
7 Zeichen Eingabe → 4 Codes Ausgabe.
Ein zweites Beispiel
Bei stärker wiederholten Mustern wächst die Ersparnis deutlich:
Aufgebautes Wörterbuch: TO=256OB=257BE=258EO=259OR=260RT=261TOB=262BEO=263ORT=264TOBE=265
16 Zeichen Eingabe → 11 Codes Ausgabe.
65 · 66 · 256 · 258. Je länger und wiederholter die Eingabe, desto stärker der Effekt.⌨️ Implementierung in C
Bewusst vereinfacht (feste Codebreite, lineares Wörterbuch) — für die Lesbarkeit.
#include <stdint.h>
#include <string.h>
/* Vereinfachtes Wörterbuch: Schlüssel = String, Wert = Code.
In der Praxis nutzt man eine Hash-Tabelle oder einen Trie. */
typedef struct {
char key[64];
int code;
} dict_entry_t;
/* Gibt den Code für die Zeichenkette w aus dem Wörterbuch zurück,
oder -1 falls (noch) nicht vorhanden. */
int dict_lookup(dict_entry_t *dict, int size, const char *w);
/* Kodiert 'input' und schreibt die Codes über emit(). */
void lzw_encode(const char *input, void (*emit)(int code)) {
dict_entry_t dict[4096];
int dict_size = 256; /* 0..255 = alle Bytes */
for (int i = 0; i < 256; i++) { /* Start-Wörterbuch */
dict[i].key[0] = (char)i;
dict[i].key[1] = '\0';
dict[i].code = i;
}
char w[64] = "";
for (const char *p = input; *p; p++) {
char wk[64];
snprintf(wk, sizeof wk, "%s%c", w, *p); /* w + k */
if (dict_lookup(dict, dict_size, wk) != -1) {
strcpy(w, wk); /* Muster verlängern */
} else {
emit(dict_lookup(dict, dict_size, w)); /* code(w) */
strcpy(dict[dict_size].key, wk); /* neuer Eintrag */
dict[dict_size].code = dict_size;
dict_size++;
w[0] = *p; w[1] = '\0'; /* w = k */
}
}
if (w[0]) emit(dict_lookup(dict, dict_size, w)); /* Rest ausgeben */
}ℹ️ Zur Verständlichkeit mit fester Codebreite und ohne Clear-Code. Echte GIF-Encoder nutzen variable Bitbreiten und Sub-Blocks.
/* Pseudocode-nahe C-Skizze des Decoders */
void lzw_decode(const int *codes, int n, void (*emit_str)(const char *)) {
char dict[4096][64];
int dict_size = 256;
for (int i = 0; i < 256; i++) { dict[i][0] = (char)i; dict[i][1] = 0; }
char prev[64];
strcpy(prev, dict[codes[0]]);
emit_str(prev);
for (int i = 1; i < n; i++) {
char entry[64];
if (codes[i] < dict_size) {
strcpy(entry, dict[codes[i]]); /* Code bekannt */
} else {
/* Sonderfall KwKwK: Code = prev + erstes Zeichen von prev */
snprintf(entry, sizeof entry, "%s%c", prev, prev[0]);
}
emit_str(entry);
/* neuer Eintrag = prev + erstes Zeichen von entry */
snprintf(dict[dict_size++], 64, "%s%c", prev, entry[0]);
strcpy(prev, entry);
}
}ℹ️ Der Decoder baut dasselbe Wörterbuch auf — ein Sonderfall (KwKwK) tritt auf, wenn ein Code gelesen wird, der gerade erst entstehen würde.
🖼️ LZW in GIF
GIF erweitert das Grundverfahren um Steuercodes und variable Bitbreiten.
LZW-Besonderheiten in GIF
| Aspekt | Bedeutung |
|---|---|
| LZW Minimum Code Size | 1 Byte vor den Daten — Bittiefe der Palette (min. 2) |
| Clear-Code | Setzt das Wörterbuch zurück (= 2^minCodeSize) |
| End-of-Information | Markiert das Ende des Bildes (= Clear-Code + 1) |
| Variable Codelänge | Startet bei minCodeSize+1 Bit, wächst bis 12 Bit |
| Sub-Blocks | Code-Strom in Blöcke à max. 255 Byte, mit Längen-Präfix |
Mehr zum Dateiaufbau auf der GIF-Seite.