LZW-Kompression

Die LZW-Kompression ist ein Wörterbuchverfahren nach Lempel-Ziv-Welch.

Wörterbuchverfahren hinterlegen wiederkehrende Zeichenfolgen in einem Wörterbuch. Kommen diese Zeichenfolgen dann im zu komprimierenden Text erneut vor, reicht ein Verweis auf diesen Eintrag. Das LZW-Verfahren arbeitet dabei mit einem dynamischen Wörterbuch, welches direkt während der Kompression selbst erzeugt wird und damit keinen zusätzlichen Speicherplatz benötigt.

Um Platz für das Wörterbuch neben den normalen (ASCII-)Zeichen zu schaffen, reichen 8 Bit nicht aus. Für gewöhnlich werden 12 Bit für jedes Zeichen bzw. jeden Wörterbucheintrag verwendet. Das Wörterbuch kann also maximal 2¹² = 4096 Zeichen und Zeichenkombinationen beinhalten, wovon die ersten 256 Einträge bei Texten fest mit den ASCII-Zeichen vorbelegt sind.

Die Codierung verläuft nach folgendem Algorithmus:

Lies eine möglichst lange Zeichenkette ein, die bereits im Wörterbuch steht. Zu Beginn ist das jeweils nur ein einzelnes Zeichen!
Schreibe den Code des gefundenen Eintrags in die Ausgabe.
Lege aus der eben gefundenen Zeichenkette und dem nachfolgenden Zeichen einen neuen Wörterbucheintrag mit der nächst möglichen Codierung an.
Wenn nötig wird das letzte Byte der Ausgabe mit 0 aufgefüllt

Beispiel

Codierung

Die Zeichenkette BABAABBAA soll mit LZW codiert werden. Das Wörterbuch ist zu Beginn des Vorgangs im Bereich von 000₁₆ bis 0FF₁₆ mit den ASCII-Zeichen befüllt¹⁾. Zum besseren Verständnis des weiteren Ablaufs sollte man im Hinterkopf haben, dass der ASCII Code des großen A 65₁₀=41₁₆ ist, der des großen B 66₁₀=42₁₆

Noch zu bearbeitende Zeichenkette	Gefundener Eintrag	Ausgabe (12Bit)	Neuer Wörterbucheintrag
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₁₆

Die Zeichenfolge wird also folgendermaßen codiert: 042041100101102₁₆. Das sind 7,5 Bytes ²⁾. Die Kompression ist also bei solch kurzen Zeichenketten noch nicht drastisch - wenn man sich jedoch vorstellt, dass das Wörterbuch stets längere Zeichenketten mit einem einzigen 12Bit Code zugreifbar macht, kann die Kompression unter Umständen bei längeren Texten deutlich stärker ins Gewicht fallen.

Decodierung

Bei der Decodierung werden 12-Bit-Blöcke eingelesen. Das Wörterbuch wird während des Vorgangs mit Einträgen befüllt die aus dem ersten Zeichen des aktuellen Eintrag und dem vorangehenden Eintrag bestehen. Wir nehmen den codierten String von oben: 042041100101102₁₆.

Aktueller 12Bit-Block (Hexadezimal)	Gefundener Eintrag (erster Buchstabe)	Neuer Wörterbucheintrag	Ausgabe
042	B (B)		B
041	A (A)	BA = 100₁₆	A
100	BA (B)	AB = 101₁₆	BA
101	AB (A)	BAA = 102₁₆	AB
102	BAA (B)	ABB = 103₁₆	BAA

Decodiert lautet der Text also BABAABBAA.

Anmerkung: Das Wörterbuch musste zur Decodierung hier nicht gesondert übertragen werden - es "ensteht" während des Vorgangs.

Für die Aufgaben kannst du die folgenden Arbeitsblätter verwenden:

(A1)

Codiere den Text ABABCABCDABCD und vergleiche die codierte und die uncodierte Länge miteinander.

Lösung:

(A2)

Decodiere folgenden Code: 058 059 05A 101 100 103. Die ASCII-Tabelle findest du hier

Lösung:

(A3)

Versuche, den Code 042041100101041104 zu decodieren. Welches Problem ergibt sich dabei?

Lösung:

(A4)

Der folgende LZW-Code: 0 1 2 4 6 5 7 7 3 codiert eine Pixelgrafik, die 4 Pixel breit ist. Die einzelnen auftretenden Pixel haben den folgenden "Grundcode":

(A5)

Erläutere in einem kurzen Text das Grundprinzip der Komprimierung beim LZW-Verfahren.

(A6)

Begründe, dass das LZW-Verfahren nicht jede Eingabe komprimieren kann.

Lösung

Material

Filename	Filesize	Last modified
01_lzw-vorlage-codierung.odt	479.1 KiB	03.10.2022 16:53
01_lzw-vorlage-codierung.pdf	74.6 KiB	03.10.2022 16:53
01_lzw-vorlage-decodierung.odt	478.4 KiB	03.10.2022 16:53
01_lzw-vorlage-decodierung.pdf	73.4 KiB	03.10.2022 16:53
06-kompression-lzw.odp	43.0 KiB	29.09.2022 07:20
06-kompression-lzw.pdf	157.1 KiB	29.09.2022 07:20
ab.png	9.9 KiB	03.10.2022 15:58
lzw_a2_cod_dec.odp	78.4 KiB	05.12.2023 14:01
lzw_a2_cod_dec.pdf	81.5 KiB	05.12.2023 14:01
pixel.png	2.0 KiB	03.10.2022 17:01

¹⁾

Die ersten 256 Zeichen des 12 Bit Raums, der für die Codierung zur Verfügung steht

²⁾

wenn man mit ganzen Bytes arbeiten möchte, wird das mit Nullen zu 8 Byte aufgefüllt