Datenkompression: Verlustfreie Verfahren: Wörterbuchbasierte Verfahren: LZT

zurück

5 Verlustfreie_Verfahren

5.2 Wörterbuchbasierte Verfahren

5.2.1 LZ77 - Lempel, Ziv (1977)

5.2.2 LZ78 - Lempel, Ziv (1978)

5.2.3 LZSS - Storer, Szymanski (1982)

5.2.4 LZW - Welch (1984)

5.2.5 LZPP - Pylak (2003)

5.2.6 LZFG - Fiala, Green

5.2.7 LZRW - Williams (1989-1991)

5.2.8 LZV - Vogt (1994)

5.2.9 LZMW - Miller, Wegman (1985)

5.2.10 LZC - ?

5.2.11 LZT - Tischer (1987)

5.2.12 LZJ - Jakobsson

5.2.13 LZR - Rodeh, Pratt, Even

5.2.14 LZB - Bell

5.2.15 LZH - Herd

5.2.16 LZO - Oberhumer

5.2.17 LZP/LZCB - Bloom (1996)

5.2.18 LZAP - Storer (1988)

5.2.19 LZY - Yabba

5.2.20

LZT - Tischer (1987)

Im Jahr 1987 stellte P. Tischer eine weitere Variante des LZW-Algorithmus unter dem Titel "A modified Lempel-Ziv-Welch Data compression scheme" vor. Diese Modifikation betrifft ebenfalls die Verwaltung des aufgebauten Wörterbuchs. Anstatt viele lange und neue Kombinationen von Wörterbucheinträgen zu erzeugen (schnelle Adaption) setzt dieses Verfahren auf eine gewisse Beständigkeit.

Codierung

Wenn man sich das LZW-Verfahren genauer ansieht, so kann man feststellen, dass das Wörterbuch relativ schnell auf die maximale Größe anwachsen und schnell voll werden kann. Entfernt man jedoch alle bereits gefundenen Einträge, wie es in einigen anderen Varianten vorgeschlagen wurde, so verliert man die Möglichkeit bereits bekannte Zeichenketten zur Codierung heranzuziehen. Damit verschlechtert sich wegen des Neuaufbaus des Wörterbuchs die Codiereffizienz. Wenn man nur die Einträge entfernt, die entweder nicht benutzt wurden, oder schon lange nicht mehr benutzt worden sind, so kann man den Inhalt des Wörterbuches optimieren. Der Gedanke ist, dass ein sehr lange nicht mehr benutzter Eintrag im Wörterbuch, auch weiterhin nicht zur Kompression der folgenden Zeichen und Zeichenketten beiträgt, weil er es in der 'Vergangenheit' auch nicht getan hat.

Die Modifikation betrifft demnach nicht das Codierverfahren selbst, sondern kann durch die Verwaltung zusätzlicher Information, die im Wörterbuch zu jeder Zeichenkette abgelegt werden, implementiert werden. Man implementiert einen Zähler, der bei einem Zugriff auf eine bestimmte Tabellenposition diesen Zähler auf 0 setzt. In jedem Schritt, bei dem kein Verweis (HIT) auf diese Tabellenposition erfolgt, wird dieser Zähler um den Wert 1 erhöht. Ist jede verfügbare Tabellenposition durch einen Wörterbucheintrag gefüllt bzw. blockiert, so muss der älteste Wörterbucheintrag ersetzt werden. Der älteste Wörterbucheintrag ist der, der den höchsten Zählerstand erreicht hat. So wird sichergestellt, dass die gebräuchlichsten Muster, also jenen die zur Kompression beitragen diejenigen überleben, die nicht zur Kompression beitragen.

LZT Algorithmus

Erzeuge ein Wörterbucheintrag/Codiersymbol nach LZW bzw. nach einer LZW Variante
Prüfe, ob dieses Codiersymbol auf einen anderen Wörterbucheintrag verweist
1. JA setze den Zähler des referenzierten Wörterbucheintrages auf 0
Erhöhe alle Zähler der Wörterbucheinträge um den Wert 1
Prüfe, ob es einen freien Platz im Wörterbuch gibt
1. NEIN, entferne den Wörterbucheintrag der den größten Zähler besitzt.
Nehme den neuen Wörterbucheintrag in das Wörterbuch auf und setze den Zähler auf einen definierten Initialwert.

Decodierung

Der Decodierer muss ebenfalls diesen Algorithmus implementieren, um bei der Decodierung ein zum Codierprozess synchronisiertes Wörterbuch zu haben. Der Decoder muss wissen wann er einen Eintrag löschen und durch einen anderen ersetzen kann.

Dieses Verfahren lässt sich problemlos auf andere LZW-Algorithmus-Varianten erweitern.

Aufgaben

Aufgabe(n) - LZT

[A20] Erweitern Sie den LZW-Algorithmus um eine LRU-Logik und bestimmen Sie einen guten Zeitpunkt, um die Tabelle zu optimieren.
[A15] Mit Welchem Zählerwert sollte ein neu in die Tabelle aufgenommener Datensatz initialisiert werden ? Erläutern Sie die Vor und Nachteile der gewählten Strategie.
[A15] Ist dieses Verfahren auch auf andere LZW-Varianten verallgemeinerbar ?