LZW-Kopression

Die LZW-Kopressione 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: 1. Lies eine möglichst lange Zeichenkette ein, die bereits im Wörterbuch steht • Zu Beginn ist das jeweils nur ein einzelnes Zeichen! 2. Schreibe den 12-Bit-Code des gefundenen Eintrags in die Ausgabe. 3. Lege aus der eben gefundenen Zeichenkette und dem nachfolgenden Zeichen einen neuen Wörterbucheintrag mit der nächst möglichen Codierung an. 4. Ggf. Wird das letzte Byte der Ausgabe mit 0 aufgefüllt