Datenkompression: Verlustfreie Verfahren: Wörterbuchbasierte Verfahren: LZP LZCB

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

LZP-Series - Bloom (1996)

Charles Bloom stellte 1996 seine Arbeit mit dem Titel "LZP: a new data compression algorithm" vor. Er entwickelte verschiedene Varianten des LZ77-Algorithmus, die eine Verbesserung der Codiereffizienz darstellen. Diese Verbesserungen leiten sich meist durch eine verbesserte Wörterbuchcodierung ab, oder durch eine verbesserte Kontextmodellierung.

Der Name LZP entstammt der Kombination die einen LZ77 Algorithmus mit einer Prädiktion verbindet, um eine Zeichenkette zu codieren: LZ + Prädiktion(Prediction) = LZP.

Lassen sie uns hier auf die Schwächen des LZ77 Verfahrens näher eingehen. Wie kann man die LZ77 Codierung verbessern? Die Anzahl der Treffer und Nicht-Treffer bleiben für einen ausgewählten Text bei gleicher Suchpuffergröße konstant. Das bedeutet, man kann in Bezug auf die Anzahl keine Veränderung oder Verbesserung erreichen, außer man vergrößert den Suchpuffer und verlängert damit auch die Offset und Längenbeschreibung. Die einzige Verbesserungsmöglichkeit besteht darin, die Treffer viel besser zu codieren bspw. statt 16 Bit für einen vollen Treffer nur noch fünf oder sechs Bit.

Die These lautet, dass ein LZ77 Codierer viel zu viele Bits für einen "Treffer an Position X" verschwendet. Stellen sie Sich vor man hat einen 64K Suchpuffer zur Verfügung. Dieser 64 K Puffer lässt sich durch einen 16 Bit-Wert (2Byte) indexieren. Geht man bspw. von einer mittleren Trefferlänge von 7 Zeichen aus, so werden pro codiertem Ausgabebyte 3,5 (7Byte / 2Byte) Datenbytes an Information übertragen. Wenn man vorhersagen könnte wo in diesem 64 K Suchpuffer der nächste Treffer ist, dann könnte man diesen Treffer vielleicht in 8 Bit (1 byte) codieren. Wenn sich dadurch die Trefferlänge erheblich reduzieren sollte, bspw. auf 4 Zeichen Länge. So wäre die Bilanz pro codiertem Ausgabezeichen, mit 4 Datenbytes pro Ausgabezeichen besser als die Variante mit 3,5 Datenbytes pro Ausgabezeichen. Dadurch würde sich die Güte der Kompression erheblich verbessern.

Außerdem wird bei der Originalimplementation (LZ77) ein Offset immer nur dann Codiert, wenn die Einsparung größer ist als der zu speichernde Offset. Das ist ebenfalls ein Problem. Jedoch erst dann, wenn der zu speichernde Offset größer als 8 Bit ist. Das LZP-Kompressionsverfahren verwendet für die Offset-Selektion ein Markov-Modell mit endlicher Ordnung. Wie ist das zu verstehen? Der aktuelle Kontext (Ordnung n) wird verwendet, um ein vorheriges Auftreten eines nachfolgenden Zeichens im gleichen Kontext zu schätzen. Beispielsweise soll die Zeichenkette Wiki-Buch codiert werden und man ist gerade dabei das Wort Buch zu codieren. Dann steht es im Kontext Wiki-. Wenn es diesen Kontext bereits gibt, so kann es sein, dass das Wort Buch nach diesem Auftreten von Wiki-. Insbesondere verbessert sich die Kompressionsleistung, wenn das Kontextmodell eine hohe Ordnung besitzt. Durch die Bestimmung des Kontextes kann man auf die Offset-Angabe verzichten.

LZP Algorithmus

1. für jedes Eingabesymbol
2. Für das nächste zu codierende Eingabesymbol wird der n-Zeichen lange vorangehende Kontext bestimmt.
3. Für den Kontext wird ein Hashwert ermittelt. Man schaut in der Hashtabelle nach, um herauszufinden, wo sich im vorangegangenen Datenstrom dieser String befunden hat.
4. Man vergleicht die zu codierenden Eingabesymbole mit dem String, der auf dem berechneten Kontext folgt und bestimmt so die Matchlänge 'L'
   1. ist $L=0$, so wird mit einem Bit angegeben, dass kein Treffer erzielt wurde. Anschließend wird das Literal ausgegeben.
   2. ist $L\geq 1$, so wird mit einem Bit angegeben, dass ein Treffer erzielt wurde. Anschließend wird die Länge des Treffers ausgegeben. Es werden auch Treffer der Länge 1 akzeptiert.
5. Wenn das Ende des Eingabestroms nicht erreicht ist, dann mit Schritt 2 fortfahren.

Das Interessante ist, dass nur noch die Angabe übertragen wird, ob es sich um einen Treffer handelt, die Länge des Treffers oder ob ein Literal ausgegeben werden muss. Die Angabe, wo sich die codierte Zeichenkette im vorangegangenen Datenpuffer (Offset) befindet, ist unerheblich und wird überhaupt nicht mehr übertragen. Dafür verkürzt sich die mittlere Trefferlänge, die jedoch durch ein Markov-Modell höherer Ordnung sehr gut kompensiert wird.

Alles in allem hat Charles Bloom Vier Varianten seines LZP-Algorithmus implementiert. LZP1 ist die schnellste und LZP4 die langsamste. LZP1 hat die schlechteste Kompression und LZP4 dagegen die beste. Praktisch gesehen vereint LZP die Vorteile eines LZ77-Verfahrens mit denen der PPM-Codierung.

LZP1

Es gibt zwei Varianten des LZP1-Codierers, eine, die mit einem 12-Bit Hash arbeitet und eine, die mit einem 16-Bit Hash arbeitet. Es wird ein Kontext von 3 Zeichen für die Prädiktion des Folgezeichens herangezogen. Man spricht von einem Markov-Modell der Ordnung 3.

12bit-Variante Die 12-Bit-Variante ist die aus dem Original-Paper von Charles Bloom "LZP: a new data compression algorithm". Sie erzeugte aus drei Zeichen (24 Bit) einen Hashwert der Länge 12. Ein jeder dieser Hashwerte verweist auf eine Startposition innerhalb eines 16-K Fensters (14 Bit). Die Größe der Indextabelle liegt bei 8 K. Das Verfahren hat einen Speicherbedarf von 24 K (16 K (Puffer) + 8 K (Indextabelle))

16bit-Variante Die 16-Bit-Variante wurde 1997 neu geschrieben und ist auf der Webseite des Charles Bloom zu finden. Der Unterschied ist, dass sie einen 16Bit-Hash (65536 verschiedene Hashwerte) verwendet. Jeder Hash verweist auf eine Startposition (Index) innerhalb eines 64-K Fensters. Damit Beträgt die Größe der Indextabelle 128 K. Es werden die drei vorangehenden Zeichen 24Bit auf eine Größe von 16Bit mit der folgenden Funktion abgebildet.

$H=((x\wedge (y<<7)\wedge (z<<11))\vee 0xFFFF)$

Die Werte x, y und z sind die ASCII-Werte der drei Zeichen, die dem zu codierenden Zeichen vorangestellt sind. Das Verfahren hat einen Speicherverbrauch von 192 K (128 K (Indextabelle) + 64 K (Puffer)). Durch den vergrößerten Index, ist die Wahrscheinlichkeit für Kollisionen verringert worden, außerdem sorgt der größere Puffer dafür, dass weitaus mehr Kombinationen von Zeichen vorhanden sind. Dadurch dass sich an der Kompression und der Codierung nichts geändert hat, führt allein diese Erweiterung zu einer besseren Codiererrizienz. Auch die Kompressionsgeschwindigkeit wird durch diese neue Parametrierung nicht beeinträchtigt.

LZP2

• Schneller als LZS und kann für online Kompression verwendet werden. Vergleichbare Ergebnisse zu LZSS.
• LZP1 + statischer Huffman Baum für die Literale

LZP3

• Effizienz wie LZ77 plus die besten Huffmanmethoden, mit der Geschwindigkeit von PKZip

LZP4

• Effizienz vergleichbar mit PPMD+ und arbeitet schneller und verbraucht weniger Speicher.

LZCB-Series - Charles Bloom

LZCB24

Die Variante v4 ist mit dem Verfahren LZP1 identisch.