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 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 |
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 |