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.
|