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üllt.

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-codierung-beispiel.png	130.2 KiB	14.01.2025 09:15
lzw-decodierung-beispiel.png	94.9 KiB	14.01.2025 09:06
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