Rechnernetze

Datenkompression durch LZSS

Das Verfahren LZSS verwendet ähnlich wie LZ77 den Anfang eines Textes des Texts als Wörterbuch bzw. die von der aktuellen Stelle k zurückliegenden Zeichen. Ebenso wird statt des Textes die relative Distanz zu einer Folge von Zeichen angegeben, sowie die Anzahl der von dort zu kopierenden Zeichen; statt des ersten nicht passende Zeichens, welches eigentlich den Fall, dass das Zeichen nicht im Wörterbuch vorkommt, abdecken sollte, wird jedoch nichts ausgegeben. Außerdem wird nur dann das Paar (Pointer, Länge) statt des Textes ausgegeben, wenn dieses einen Gewinn darstellt, also die Anzahl der Zeichen größer ist als der Platz für Zeiger und Längenangabe.

Beispiel

Position

1

2

3

4

5

6

7

8
9 10
11

Zeichen

A

A

B

B

C

B

B

A
A B
C

Kompression

Mindestlänge zu komprimierender Zeichenfolge sei 2

Nr.

Pos

Treffer

Ausgabe

1.

1

-

A

2.

2

A
A

3.

3

-
B

4.

4

B
B

5.

5

-
C

6. 6 BB 3,2

7. 8 AAB 7,3

8. 11 C 5

Bei der Dekomprimierung verfährt man analog: Wird ein Zeiger gefunden, so wird die jeweilige Adresse berechnet und die Anzahl von Zeichen ausgegeben; wird ein Zeichen gefunden, so wird dieses ausgegeben. Durch ein Extrabit wird zwischen Zeichen und Pointer mit Längenangabe unterschieden.

Die Kompressionsrate dieses Verfahrens wird als besser als LZ77 angegeben, wobei sie natürlich von den verwendeten Daten abhängt. Typischerweise wird ein "Fenster" von k=4 bis k=64 kBytes verwendet. Der wesentliche Nachteil dieses Verfahrens ist die relativ aufwendige Kompression, da sehr viele Vergleiche durchzuführen sind; es sollte ja stets die längste Zeichenkette, die mit einer Zeichenkette in den letzten k Zeichen übereinstimmt, gefunden werden. Die Dekomprimierung ist hingegen sehr viel effizienter durchführbar, da keine Zeichenketten gesucht werden müssen, sondern über eine einfache Adressrechnung mit konstantem Aufwand ein Wort leicht gefunden werden kann.

LZSS wird in den meisten populären Archivierungsprogrammen eingesetzt, in welchen außer einer Kompression einer Datei mehrere Dateien und deren Directory-Struktur in einer Ausgabedatei gespeichert und komprimiert werden, um diese Daten einfacher verteilen zu können. Es wird daher in PKZip, ARJ, LHArc, ZOO usw. verwendet. Jeder Archivierer benutzt allerdings eine etwas andere Implementierung, also unterschiedliche Zeigerlängen, die teilweise variabel sind, verschiedene Fenstergrößen, andere Schrittweiten, die größer als eins sein können, usw.

Da häufig mehrere Zeichen unverändert übernommen werden, lässt sich auch Entropie-Kodierung verwenden, wobei meistens die Huffman-Kodierung benutzt wird.