Komprimieren mit LZW

1. Wiederholungen

Ein Text wiederholt sich ständig: Buchstabenfolgen wie »ch«, »sch«, »ein« und »der« kommen auf jeder Seite dutzendfach vor, ganze Wörter auch. Ein Programm, das komprimiert, sucht solche Wiederholungen und ersetzt sie durch etwas Kürzeres. Beim Entpacken muss genau das Original zurückkommen, Byte für Byte; das heißt verlustfrei.

Das Verfahren auf dieser Seite haben Abraham Lempel und Jacob Ziv 1978 erfunden und Terry Welch 1984 so vereinfacht, wie es seitdem benutzt wird, daher der Name LZW. Es steckt in GIF-Bildern, in TIFF, in alten PDF-Dateien und im Unix-Programm compress. Die Idee ist ein Wörterbuch, in dem jede Folge von Bytes, die schon vorkam, eine Nummer hat, den Code:

• Am Anfang stehen darin die 256 möglichen Bytes, jedes einzeln. Das Byte 65 (»A«) hat den Code 65.
• Jedes Mal, wenn das Programm einen Code ausgibt, kommt ein neuer Eintrag dazu, mit dem nächsten freien Code: 256, 257, 258, …
• Ein Code steht also für eine immer längere Folge, und wo sich etwas wiederholt, ersetzt ein einziger Code mehrere Bytes.

2. Komprimieren

Der Kompressor liest den Text Byte für Byte und merkt sich das Präfix, das er gerade aufbaut: den Anfang des restlichen Texts, der schon im Wörterbuch steht. Für jedes Byte gilt:

1. Steht das Präfix mit dem neuen Byte dahinter schon im Wörterbuch, wird das Präfix um dieses Byte länger.
2. Sonst gibt er den Code des Präfixes aus, trägt das Präfix mit dem neuen Byte als neuen Eintrag ein und beginnt ein neues Präfix, das nur aus dem neuen Byte besteht.
3. Ist der Text zu Ende, gibt er den Code des letzten Präfixes aus.

Probier es aus. Jeder Klick liest ein Byte; das gelbe ist das Präfix, das rot umrandete das nächste Byte. Du kannst auch einen eigenen Text eintippen.

Bei der Rhabarberbarbara stehen nach dem ersten »BAR« für »BA«, »AR« und »RB« eigene Einträge im Wörterbuch, und schon das zweite »BARBARA« braucht weniger Codes als Buchstaben. Ganz am Anfang kann LZW nichts sparen: Das Wörterbuch kennt noch nichts außer den einzelnen Bytes.

3. Einrichten

Lege im Terminal (StrgJ) einen Ordner an und öffne ihn mit StrgK StrgO:

mkdir /workspace/lzw

# LZW: komprimieren und entpacken

# Macht aus den Bytes eines Strings eine Liste von Codes.
def compress(data)
    codes = []
    codes
end

# Macht aus einer Liste von Codes wieder die Bytes, als String.
def decompress(codes)
    ''
end

p compress('ABABABA')

# LZW: komprimieren und entpacken


def compress(data):
    """Macht aus Bytes eine Liste von Codes."""
    codes = []
    return codes


def decompress(codes):
    """Macht aus einer Liste von Codes wieder die Bytes."""
    return b''


print(compress(b'ABABABA'))

4. Der Kompressor

5. Entpacken

Der Entpacker bekommt nur die Codes. Die Codes unter 256 versteht er sofort, sie sind einzelne Bytes. Für alle anderen baut er das Wörterbuch selbst nach, so wie der Kompressor es gebaut hat, nur einen Schritt später:

1. Der erste Code ist immer ein einzelnes Byte. Schreib es hin; es ist der vorige Eintrag für den nächsten Schritt.
2. Für jeden weiteren Code: Schlag den Eintrag nach und schreib ihn hin.
3. Trag dann den vorigen Eintrag mit dem ersten Byte des jetzigen dahinter als neuen Eintrag ein. Genau diesen Eintrag hat der Kompressor angelegt, als er den vorigen Code ausgegeben hat, denn das nächste Byte war das erste Byte des jetzigen Eintrags.

Das Wörterbuch des Entpackers ist also immer einen Eintrag hinter dem des Kompressors. Meistens macht das nichts, aber nicht immer:

Der Kompressor kann einen Eintrag benutzen, den er gerade erst angelegt hat. Das passiert, wenn sich ein Präfix sofort wiederholt und dabei mit seinem eigenen ersten Byte weitergeht, wie bei ABABABA. Der Entpacker kennt diesen Eintrag noch nicht, aber er kann ihn ausrechnen: Es ist der vorige Eintrag mit dessen eigenem ersten Byte dahinter. Das ist die einzige Ausnahme von Regel 2.

Hier entpackt der Schrittmacher die Codes des Texts, der oben im Feld steht; die Ausnahme ist rot markiert. Tipp oben ABABABA oder AAAAAAAA ein und sieh hier zu.

6. Wie gut ist das?

Lade dann zwei Dateien zum Ausprobieren in den Ordner: die Spezifikation von GIF, ein Text von 1990 mit 83.003 Bytes, und ein Foto als JPEG.

wget https://workspace.hackschule.de/lzw/spec-gif89a.txt
wget https://workspace.hackschule.de/jpeg/44-baseline.jpg

Echte Programme komprimieren noch besser. gzip benutzt LZ77, die erste Idee von Lempel und Ziv von 1977, und codiert das Ergebnis danach noch mit Huffman:

gzip -9 -k spec-gif89a.txt
ls -l spec-gif89a.txt*

Und das Foto?

7. Ein volles Wörterbuch

Unser Wörterbuch wächst ohne Grenze: Bei der Spezifikation hat es am Ende über 17.000 Einträge, bei einer großen Datei wären es Millionen. Echte Programme setzen eine Grenze. GIF erlaubt höchstens 4096 Einträge, also Codes mit höchstens 12 Bits; compress geht bis 16 Bits. Ist das Wörterbuch voll, kommen keine Einträge mehr dazu, oder es beginnt von vorn: Der Kompressor schickt dafür einen eigenen Code, den Clear Code, und beide Seiten fangen wieder mit den 256 Bytes an.

Bau das in deine beiden Funktionen ein: Reserviere den Code 256 als Clear Code, die neuen Einträge beginnen dann bei 257. Hat das Wörterbuch 4096 Einträge, gibt compress den Clear Code aus, und beide Seiten beginnen neu. Vergleich mit size_in_bytes, wie viel größer die Spezifikation dadurch wird, und überleg, warum ein frisches Wörterbuch bei einem langen Text sogar helfen kann.

8. Weiter geht's

• GIF: In einem GIF-Bild sind die »Bytes« die Nummern der Farben, und die Codes stehen Bit für Bit in der Datei. Wie das genau aussieht, steht in Eine GIF-Datei decodieren, mit einem Decoder in C.
• Das Patent: Auf LZW hatte die Firma Unisys ein Patent, und ab 1994 verlangte sie Lizenzgebühren von Programmen, die GIF-Dateien schrieben. Als Antwort entstand 1995 das Format PNG, das ohne LZW auskommt. Das Patent lief 2003 in den USA und 2004 in Europa aus.
• Andere Texte: Komprimiere Texte in anderen Sprachen, eine Datei aus lauter gleichen Bytes, eine mit Zufallszahlen (head -c 100000 /dev/urandom > zufall.bin). Wann lohnt sich LZW, wann nicht?