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 212 = 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 00016 bis 0FF16 mit den ASCII-Zeichen befüllt1). Zum besseren Verständnis des weiteren Ablaufs sollte man im Hinterkopf haben, dass der ASCII Code des großen A 6510=4116 ist, der des großen B 6610=4216
| Noch zu bearbeitende Zeichenkette | Gefundener Eintrag | Ausgabe (12Bit) | Neuer Wörterbucheintrag |
|---|---|---|---|
| BABAABBAA | B ← 04216 | 04216 | BA → 10016 |
| ABAABBAA | A ← 04116 | 04116 | AB → 10116 |
| BAABBAA | BA ← 10016 | 10016 | BAA → 10216 |
| ABBAA | AB ← 10116 | 10116 | ABB → 10316 |
| BAA | BAA ←10216 | 10216 |
Die Zeichenfolge wird also folgendermaßen codiert: 04204110010110216. Das sind 7,5 Bytes 2). 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: 04204110010110216.
| Aktueller 12Bit-Block (Hexadezimal) | Gefundener Eintrag (erster Buchstabe) | Neuer Wörterbucheintrag | Ausgabe |
|---|---|---|---|
| 042 | B (B) | B | |
| 041 | A (A) | BA = 10016 | A |
| 100 | BA (B) | AB = 10116 | BA |
| 101 | AB (A) | BAA = 10216 | AB |
| 102 | BAA (B) | ABB = 10316 | 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.
(A2)
(A3)
(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.
Material
| Filename | Filesize | Last modified |
|---|---|---|
| 01_lzw-vorlage-codierung.odt | 479.1 KiB | 03.10.2022 18:53 |
| 01_lzw-vorlage-codierung.pdf | 74.6 KiB | 03.10.2022 18:53 |
| 01_lzw-vorlage-decodierung.odt | 478.4 KiB | 03.10.2022 18:53 |
| 01_lzw-vorlage-decodierung.pdf | 73.4 KiB | 03.10.2022 18:53 |
| 06-kompression-lzw.odp | 43.0 KiB | 29.09.2022 09:20 |
| 06-kompression-lzw.pdf | 157.1 KiB | 29.09.2022 09:20 |
| ab.png | 9.9 KiB | 03.10.2022 17:58 |
| lzw_a2_cod_dec.odp | 78.4 KiB | 05.12.2023 15:01 |
| lzw_a2_cod_dec.pdf | 81.5 KiB | 05.12.2023 15:01 |
| pixel.png | 2.0 KiB | 03.10.2022 19:01 |