Index

5. Komprimierung von Daten (4)

LZW-Verfahren


Übung  

Moderne Komprimier-Programme verwenden die Algorithmen von Abraham Lempel, Jacob Ziv und Terry A. Welch (LZW-Verfahren).

Die Vorteile dieses Verfahrens sind:

Die bekanntesten Verfahren sind:
LZ77 Lempel, Ziv 1977,
realisiert in den Pack-Programmen arj, lha, zip, zoo
LZ78 Lempel, Ziv 1978
LZW basiert auf LZ78 mit Erweiterungen von Welch 1984,
Bestandteil des GIF-Formats.

Die Idee besteht darin, Zeichenfolgen in zunehmender Länge durch neue Codes zu kodieren. Der ASCII-Code umfasst den Dezimalbereich von 0 bis 255. Die neuen Codes schließen sich an, wir notieren sie im folgenden Beispiel in Klammern. Das zugehörige Wörterbuch wird parallel aufgebaut und im Rechner hinterlegt. Es muss der Datei nicht hinzugefügt werden, da es bei der Dekodierung wieder restauriert werden kann.

Ablauf:

Komprimierung

Zunächst werden auftretende Zweiergruppierungen neu kodiert. Ist eine Zweiergruppe als Präfix einer Dreiergruppe bereits kodiert, wird die Dreiergruppe neu kodiert. So werden die Codes für immer längere Zeichenfolgen entwickelt und nur solche, die auch nötig sind. Beim Kodieren muss immer das nächste Zeichen (im Beispiel als Fettdruck) nach dem bereits erkannten Muster in die Betrachtung einbezogen werden, da sich damit die nächste Zeichengruppenkodierung ergibt.

[Beispiel zur Komprimierung]

Entkomprimierung

Wie bereits erwähnt, liegt nun der Vorteil darin, dass das Wörterbuch nicht mitgeteilt werden muss. Beim Entkomprimieren wird aus der eingegebenen komprimierten Zeichenkette ein Zeichen bzw. die entsprechende Folge nach Wörterbucheintrag gelesen und ausgegeben, sowie als Präfix für die folgende Zeichengruppe notiert. Zum Aufbau des Wörterbuchs wird das erste gelesene Zeichen (in der Tabelle des Beispiels "aktuelles Zeichen") an das vorherige Präfix angehängt und als neuer Eintrag mit dem nächsten Code im Wörterbuch festgehalten.

[Beispiel zur Entkomprimierung]

In manchen Situationen kann es vorkommen, dass der Wörterbucheintrag, der in derselben Zeile, also für das aktuelle Zeichen generiert wird, bereits für das aktuelle Zeichen benötigt wird und daher nicht ausgegeben werden kann. Da dieser Wörterbucheintrag aber das festge-haltene Präfix am Anfang enthält, kann das aktuelle Zeichen hieraus ermittelt werden. Es ist das erste Zeichen des Präfixes. Nun wird dieses Zeichen aber für den Wörterbucheintrag an das Präfix angehängt. Damit steht der Wörterbucheintrag für die Ausgabe zur Verfügung. Dies kann daher nur für Zeichenfolgen der Art Z[Zeichenkette]Z vorkommen.
Bei folgender Zeichenkette ergibt sich z.B. das geschilderte Problem: APAPAPAPAPAP

Seitenanfang


Übungen:

Im folgenden bestehe das Alphabet aus den Buchstaben a und b, wobei a mit 0 und b mit 1 kodiert sei. Es sind keine weiteren Buchstaben vorhanden.

  1. Komprimiere die Zeichenkette ababaabaababa mit dem Ziv-Lempel-Verfahren.
    Gib das zugehörige Wörterbuch an.
  2. Dekodiere die Folge 012345678.
    Gib das dabei aufgebaute Wörterbuch an.

Seitenanfang


1. Einführung   2. RLE-Verfahren   3. Huffman-Verfahren  

[Index]


Autor: Matthias Taulien
Überarbeitet: Jürgen Dehmer
Letzte Änderung: 11.10.2004