Rechnernetze

Datenkompression durch LZ78

Eine Abwandlung von LZ77 verwendet ein eigenes "Wörterbuch", in welchem eine Folge von Zeichen unter einem Index abgelegt wird. Dieses Wörterbuch wird während der Erstellung der komprimierten Daten aufgenommen und in einigen Varianten bei zu großen Datenmengen laufend angepasst.

Wird ein (möglichst langes) Wort im Wörterbuch gefunden, dann wird der Index dieses Worts im Wörterbuch sowie das folgende Zeichen ausgegeben; das Wort mit dem neuen Zeichen wird in das Wörterbuch als neues Wort aufgenommen.

Beispiel

Position

1

2

3

4

5

6

7

8

9

Zeichen

A

B

B

C

B

C

A

B

A

Kompression

Nr.

Pos.

Wörterbuch

Ausgabe

1.

1

1: A

(0,A)

2.

2

2: B

(0,B)

3.

3

3: B C

(2,C)

4.

5

4: B C A

(3,A)

5.

8

5: B A

(2,A)

Zu Anfang ist das Wörterbuch leer, so dass ein leerer Eintrag im Wörterbuch gekennzeichnet werden muss (im Beispiel durch (0,X)). Bei der Dekompression wird bei der Eingabe (0,X) das Zeichen X mit dem jeweils nächsten Index ins Wörterbuch übernommen und das Zeichen X ausgegeben; ansonsten wird bei der Eingabe (i,Y) die Zeichenkette W[i] unter dem jeweiligen Index i zusammen mit dem Zeichen Y ausgegeben, und die Zeichenkette W[i]+Y in das Wörterbuch unter dem nächsten Index j übernommen: W[j]:=W[i]+Y; j:=j+1.

Die Kompressionsrate dieses Verfahrens soll ähnlich der von LZ77 sein, jedoch ist die Kompression deutlich schneller, da in der Regel weniger Zeichenketten untersucht werden. Allerdings muss während der Kompression bzw. Dekompression ein zusätzlicher Speicher für das Wörterbuch vorhanden sein, welches darüber hinaus effizient organisiert werden sollte.