Proseminar Redundanz, Fehlertoleranz und Kompression

Die Ziv-Lempel-Kompression

1. Geschichte

Bis zum Jahre 1977 richtete sich das Hauptaugenmerk der Datenkomprimierungsforschung auf die neuen und verbesserten Methoden zur Steuerung von Huffman-Codierungsprogrammen. Die Veröffentlichung der beiden Artikel hatte einen direkten Einfluß auf das Gebiet der Informationstheorie.

Die Auswirkungen waren für Programmierer aber erst 1984 mit dem erscheinen des Artikels "A Technique for High-Performance Data Compression" von Terry Welch zu spüren. In dieser Veröffentlichung beschrieb er seine Implementation des LZ78-Algorithmus, den er LZW nannte. Kurz darauf erschien das Unix-Komprimierungsprogramm "compress" welches auf diesem Algorithmus basiert und zum Standard für Unix-Systeme wurde. Im MS-DOS-Bereich wurde "ARC" zum Standard, welches ebenfalls auf dem LZ78 Algorithmus beruht. Später allerdings gab "ARC" seine Vorrangstellung im PC-Bereich an Konkurrenten wie "PKZIP" und "ARJ" ab, welche "nur" auf dem LZ77-Algorithmus basieren.

2. Tabellengesteuerte Komprimierung

• Statistische Methode: Vor der tabellengesteuerten Komprimierung wurden fast ausschließlich statistische Modelle verwendet. Bei diesem Modell wird die Komprimierung durch Kodieren der Symbole als Bitstrings erreicht, die weniger Bit als die Orginalsymbole beanspruchen. Damit hängt der Komprimierungsgrad davon ab, wie gut ein Programm ein Modell einrichten kann. Dieses Modell muß vorhersagen, mit welchen Wahrscheinlichkeiten die Symbole auftreten und die Wahrscheinlichkeiten der Symbole, die vom Mittelwert abweichen. Ein großer Nachteil dabei ist, dass diese Methoden nur von einer shannonschen Informationsquelle ausgehen und deshalb Redundanzen, die aus Mustern im Datenstrom entstehen, nicht erkennen und ausnutzen können.
• Tabellengesteuerte Methode: Der tabellengesteuerte Algorithmus codiert Symbolketten variabler Länge als Token, die einen Verweis in ein Phrasenverzeichnis darstellen. Sind diese Token kleiner als die Phrasen, die sie ersetzen, kommt es zur Komprimierung. Damit kann dieser Algorithmus immer auf den Text reagieren und muß keine Wahrscheinlichkeiten vorhersagen.

3. LZ77

3.1. Der Algorithmus

1. Einen Offset auf eine Phrase im Textfenster,
2. die Phrasenlänge und
3. um das erste Symbol im nach vorn gerichteten Puffer, das auf die Phrase folgt.

Der Dekomprimierungsalgorithmus ist noch simpler, da keine Vergleichsoperationen ausgeführt werden müssen. Ein Token wird eingelesen, die entsprechende Phrase und das darauffolgende Zeichen werden ausgegeben, das Textfenster wird weitergeschoben und der ganze Vorgang wird wiederholt.