Rechnernetze
Home Nach oben

Datenkompression durch LZ77

1977 wurde von Lempel und Ziv ein Verfahren zur Datenkompression vorgeschlagen, welches als Wörterbuch den Anfang eines Textes verwendet bzw. die von der aktuellen Stelle k zurückliegenden Zeichen. Statt des Textes wird die relative Distanz zu einer Folge von Zeichen angegeben, sowie die Anzahl der von dort zu kopierenden Zeichen; zusätzlich wird noch das erste nicht passende Zeichen ausgegeben.

Beispiel

Position

1

2

3

4

5

6

7

8

9

Zeichen

A

A

B

C

B

B

A

B

C

Kompression

Nr.

Pos

Treffer

Zeichen

Ausgabe

1.

1

-

A

(0,0) A

2.

2

A

B

(1,1) B

3.

4

-

C

(0,0) C

4.

5

B

B

(2,1) B

5.

7

A B

C

(5,2) C

Die Kompressionsrate dieses Verfahrens wird als sehr gut 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.