Datenkomprimierung mit LZSS

Kurzbeschreibung  

Genauer erklärt: wir haben den String "aaaaaaaabbbaaaa". Die ersten 4 Zeichen (rot markiert) werden immer unkomprimiert gespeichert werden (wie wir uns das merken, erkläre ich später). Unser komprimierter String beinhaltet jetzt also "aaaa" und wir sind auf Position 5 im Eingabestring. Die nächstgrößte Zeichenkette, die im den letzten 65535 Zeichen auftaucht, ist jetzt "aaaa" (blau markiert). Anstatt an unsere komprimierten Daten jetzt diesen String anzuhängen, erstellen wir einen Zeiger aus 3 Bytes auf das vorherige Vorkommen dieser Zeichenkette, dadurch sparen wir ein Byte.

Die ersten beiden Bytes geben die relative Position des Zeigers zur vorherigen Kette an. In unserem Fall müssen wir 4 übergeben, weil "aaaa" (rot) 4 Zeichen vor dem ersten blauen "a" beginnt. Im dritten Byte speichern wir nun die Länge dieser Fundstelle, hier auch 4 ("aaaa"). So gehen wir den gesamten Eingabestring durch. Auf Grund technischer Gegebenheiten suchen wir aber doppelte Strings nur in den letzten 65535 Zeichen, und eine gefundene Zeichenkette darf maximal 255 Zeichen lang sein.

Nun weiter. Der Datenzeiger steht jetzt auf 9 (das erste "b"). Da wir kein "b" im Buffer finden, schreiben wir das "b" unkomprimiert in den Speicher. Und weil wir die minimale Länge eines Suchstrings auf 3 begrenzt haben (alles drunter würde schließlich zu einer Vergrößerung führen), werden die restlichen 2 "b"s direkt dahinter geschrieben. Jetzt haben wir noch 8 "a"s zu komprimieren. Da wir aber nur 4 unkomprimiert am Anfang gespeichert haben, werden aus diesen "a"s jetzt zwei Zeiger. Das Resultat: wir haben den String "aaaaaaabbbaaaaaaaa" um 3 Zeichen gekürzt.

Der Header  

Nun wollen wir das ganze etwas genauer spezifizieren und dabei wesentlich technischer werden. Im Ausgabestring müssen wir nämlich noch Information zum Dekomprimieren angeben. Dafür muss ich aber kurz erklären, wie genau diese Werte zu Stande kommen.
Zuerst haben wir da die Anzahl der Durchläufe. Jedes Mal wenn wir entweder einen Zeiger in die Ausgabe schreiben oder ein einzelnes unkomprimiertes Zeichen, zählen wir dies als einzelnen Durchlauf.
Dann speichern wir in einem Bitfeld, ob wir im entsprechenden Durchlauf einen Zeiger oder ein einzelnes Zeichen gespeichert haben. Wenn wir also 10 Durchläufe haben, sind in unserem Bitfeld 10 Bits. Jedes Bit entspricht einem Durchlauf. So können wir nachher beim Dekomprimieren feststellen, ob wir das aktuelle Zeichen als Zeiger oder Wert interpretieren sollen.

Am Anfang der Ausgabe, im Header, speichern wir nun diese Informationen. Die ersten 8 Byte sind für die Anzahl der Durchläufe und für die Größe des Bitfeldes reserviert (jeweils 4 Byte, wir machen dabei durch Bitshifts und Chr$() aus dem Long eine Zeichenkette). Dann kommt das Bitfeld, auch wieder in Bytes umgewandelt. Und zuletzt die komprimierten Daten.

Genauere Funktionsweise  

Jetzt wollen wir diese Suche doch mal etwas genauer unter die Lupe nehmen. Uns stehen als Werte die Position im Eingabestring und die maximale Länge für die zu suchende Zeichenkette zur Verfügung (entweder 255 oder, wenn der Rest des Eingabestrings kleiner ist, entsprechend begrenzt). Wir gucken uns die darauffolgenden Zeichen in 3er Packs an. Sollten wir die ersten 3 Zeichen nicht im Buffer finden (der Buffer sind die letzten 65535 Zeichen), so schreiben wie in die Ausgabe einfach ein einzelnes unkomprimiertes Byte und speichern den Vorgang im Bitfeld mit einer Null.

Sollten wir diese Zeichenkette jedoch wiederfinden, nehmen wir noch 3 dazu und suchen wieder. Wir nehmen dann in einer Schleife so lange 3 Zeichen hinzu bis wir die Zeichenkette nicht mehr im Buffer finden. Dann gehen wir langsam in Einer-Schritten zurück und entfernen immer ein Zeichen, bis wir den String im Buffer finden. Jetzt haben wir die Position im Buffer und die Länge. Die relative Position (Anzahl der Zeichen zwischen Ende des Buffers und Position -> BufferOffset) sowie die Länge der Zeichenkette werden als Zeiger gespeichert. BufferOffset wandeln wir durch Bitshifts in zwei Bytes um, die Länge in ein einzelnes Byte, und speichern das Ganze in der Ausgabe. Nun müssen wir dem Bitfeld nur noch eine Eins hinzufügen, damit wir beim Dekomprimieren den Zeiger erkennen.

Dekomprimieren  

Dieser Vorgang läuft dann relativ einfach ab. Wir durchlaufen lediglich das gespeicherte Bitfeld und setzen in den Ausgabestring entweder ein umkomprimiertes Zeichen (bei Null im Bitfeld) oder fügen die Zeichenkette X Zeichen (siehe Zeiger) vor unserer Position mit der vorgegebenen Länge nochmals ans Ende an.

Projekt als Download [2100 Bytes]

Ihre Meinung  

Falls Sie Fragen zu diesem Tutorial haben oder Ihre Erfahrung mit anderen Nutzern austauschen möchten, dann teilen Sie uns diese bitte in einem der unten vorhandenen Themen oder über einen neuen Beitrag mit. Hierzu können sie einfach einen Beitrag in einem zum Thema passenden Forum anlegen, welcher automatisch mit dieser Seite verknüpft wird.