LZW-Kompression: Codieren, decodieren und Platzbedarf prüfen

LZW ist ein verlustfreies Komprimierungsverfahren. Aus den komprimierten Daten bekommst du also die ursprünglichen Daten wieder. Das Verfahren arbeitet mit einem dynamischen Wörterbuch. Darin sammeln sich häufig vorkommende Zeichenketten. Sie werden dann nur noch unter einer Abkürzung angesprochen. Diese Abkürzung ist eine Nummer, der Index.

Am Anfang stehen im Wörterbuch nur einzelne Bytes (ein Byte ist hier ein Zeichen aus 8 Bit). Die Einträge mit dem Index 0 bis 255 sind damit gefüllt. Das Wörterbuch beginnt also nicht leer. Neue Einträge beginnen deshalb mit dem Index 256. Ein neuer Eintrag entsteht so: Der Kompressor sucht an der Eingabe das längste Muster, das schon im Wörterbuch steht, und gibt dessen Wert aus. Dann speichert er den gefundenen Eintrag plus das nächste Zeichen als neuen Eintrag.

Das Wörterbuch wird erst zur Laufzeit erzeugt, also während das Verfahren arbeitet. Deshalb ist es unabhängig vom Format der Daten. Der Kompressor führt es intern mit, speichert es aber nicht. Der Decoder (das Programm, das wieder entpackt) baut es aus den Codes selbst auf. Es muss also nicht übertragen werden.

Hinweis: In den Beispielen schreiben wir einzelne Zeichen als sie selbst. Codes ab 256 schreiben wir als Zahl.

Beim Codieren liest du Zeichen für Zeichen und hältst ein Muster fest. Du schaust auf das nächste Zeichen. Steht Muster plus nächstes Zeichen schon im Wörterbuch, wird das Muster verlängert. Sonst trägst du Muster plus Zeichen als neuen Eintrag ein, gibst das Muster aus und beginnst mit dem Zeichen neu. Am Ende wird das übrige Muster noch ausgegeben.

Beim Decodieren gibst du den ersten Code unverändert aus. Bei jedem weiteren Code trägst du das vorherige Muster plus das erste Zeichen des aktuellen Musters als neuen Eintrag ein. Danach gibst du das aktuelle Muster aus. Das klappt, weil der Kompressor immer nur das alte Muster und nicht das neue Muster mit dem nächsten Zeichen ausgegeben hat. So entsteht beim Decodieren genau das gleiche Wörterbuch.

Beim Decodieren brauchst du das erste Zeichen des aktuellen Musters. Problematisch wird es, wenn das auszugebende Muster noch nicht in der Tabelle eingetragen ist. Der Code gehört dann zu dem Eintrag, den der Decoder gerade erst anlegen will. Dann kann man auch nicht in der Tabelle nach dem ersten Zeichen dieses Musters suchen.

Das passiert nur, falls ein Muster mehrmals direkt hintereinander auftritt. Der Decoder kennt das Muster dann noch nicht, kann den Wert aber rekonstruieren. Dann gilt: Das neue Muster ist das vorherige Muster plus das erste Zeichen des vorherigen Musters.

Verlustfrei heißt nicht, dass die Ausgabe kürzer ist. Du musst nachrechnen. Einträge im Wörterbuch werden üblicherweise über einen 12 Bit langen Index angesprochen. Beim Standardverfahren besteht der Datenstrom ausschließlich aus Tabellenindexen. Deshalb sind die Symbole selbst immer genauso groß wie der Tabellenindex. Bei einem 10 Bit langen Index braucht auch ein einzelnes Zeichen 10 Bit, obwohl es ursprünglich 8 Bit waren. Bei dem üblichen 12-Bit-Index sind es entsprechend 12 Bit pro Code.

So prüfst du es: Eingabe = Zahl der Zeichen mal 8 Bit. Ausgabe = Zahl der Codes mal Bits pro Code. Wir rechnen hier mit 12 Bit pro Code, auch für einzelne Zeichen. Das Wikipedia-Beispiel macht es genauso: 16 Codes zu 12 Bit entsprechen 24 Zeichen zu 8 Bit. Die Eingabe hatte dort 22 Zeichen zu 8 Bit. Die codierte Form ist hier also länger.

Es gibt Varianten. Eine speichert ein einzelnes Zeichen meistens direkt mit 8 Bit statt als Verweis mit 12 Bit. Beides unterscheidet sie im Bitstrom per Flag (ein Markierungsbit). Eine andere Verfeinerung beginnt mit 9-Bit-Codes, die später bis zu 12 Bit breit werden.