Dies ist eine alte Version des Dokuments!
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
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
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 |