Dies ist eine alte Version des Dokuments!
LZW-Kopression
Die LZW-Kopression 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 12-Bit-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