Datenkompression: Verlustfreie Verfahren: Wörterbuchbasierte Verfahren: LZPP
- 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
- 5.2.1 LZ77 - Lempel, Ziv (1977)
LZPP - Pylak
Bearbeiten
Der Autor Pawel Pylak stellte im Jahr 2003 eine Modifikation des LZSS Algorithmus vor, den er als LZPP-Algorithmus in seiner Arbeit "Efficient modification of LZSS compression algorithm" vorstellt. Der Autor entfernt Redundanzen innerhalb des LZSS Verfahrens indem er eine spezielle Codierung der Zwei und Drei-Zeichen-Treffer empfiehlt. Daneben existieren eine Reihe weiterer Möglichkeiten, die Redundanzen zu entfernen. Dieser Algorithmus ist eine Abwandlung des LZSS und folglich des LZ77 Algorithmus.
Die Hauptansatzpunkte für die Verbesserungen wurden schon früher skizziert. Es wurden zwar keine neuen Techniken vorgestellt, doch bereits bekannte Techniken konsequent angewendet.
- Er untersuchte u.A. die Verteilung der Tabellenindexe und es zeigt sich, dass besonders weit entferne Treffer besonders selten im Vergleich zu Treffern in der unmittelbaren Nähe zum Codierfenster sind. Treffer mit kleineren Indizies treten häufiger auf, als Treffer mit großen Indizies. Dieses Ungleichgewicht lässt sich durch einen nachgeschalteten arithmetischen Codierer sehr gut ausnutzen.
- Ebenso analysierte er die Längen der Treffer, wobei Treffer mit 3 Zeichen Länge weitaus häufiger sind als Treffer mit 4 oder 5 Zeichen Länge. Das bedeutet, dass für die Trefferlänge eine Entropiecodierung möglich ist.
- Außerdem wurde Verteilung der Informationen gemessen, ob ein längerer Treffer codiert wird, oder ob ein einzelnes Zeichen codiert wird, in Abhängigkeit von der aktuellen Dateiposition. Das bedeutet, dass mit zunehmender Tabellengröße und Dateifortschritt die Wahrscheinlichkeit für einen Treffer steigt. Anfangs müssen fast alle Zeichen direkt codiert werden, später jedoch nur noch 20%. Auch die nicht komprimierten Symbole können durch eine Entropiecodierung (Huffman) zusätzlich codiert werden, da diese Zeichen im LZSS Verfahren überhaupt nicht codiert wurden.
- Wenn man die Treffer analysiert, so stellt man fest, dass Treffer bspw. mit der Länge 3 nicht gleichverteilt sind, sondern einige Silben und Wortgruppen wahrscheinlicher sind, als andere. Auch hier kann die unterschiedliche Auftretenswahrscheinlichkeit direkt zu einer Redundanzvermeidung genutzt werden.
- Zu guterletzt wird ein Verfahren zum Umkehrschluss empfohlen, mit dem die Schätzung für ein nicht codiertes Folgesymbol nach einem Treffer verbessert werden kann. Idee ist der folgende Sachverhalt. Es ist effizienter einen Treffer mit einer Länge N+1 zu codieren, was jedoch nicht immer möglich ist, da sich die Zeichenkette nicht in der Tabelle finden lässt. Statt dessen musste ein kürzerer Treffer mit der Länge N codiert werden, für den ein passender Tabelleneintrag gefunden wurde. Das Folgesymbol kann folglich nur aus der Menge kommen, für die es noch keine Tabelleneinträge gibt. Alle vorhandenen Tabelleneinträge sind unwahrscheinlich. Damit kann die Wahrscheinlichkeit 1 auf weniger Symbole verteilt werden, was zu einer höheren Wahrscheinlichkeit für bestimmte Folgesymbole führt.
Wie man zum Einen sehen kann, kann eine nachgeschaltete Codierung der Treffer und der Nicht-Treffer eine massive Verbesserung der Kompressionsrate bewirken. Wie man jedoch auch sehen kann, ist dieser Codiergewinn nur mit einer Steigerung der Komplexität des Codierers möglich geworden. Aber auch dieses Verfahren kann die Shannonsche Informationsgrenze nicht unterbieten. Sehr wohl ist es möglich, dass man Aufgrund von "Unaufmerksamkeiten" die Shannonsche Informationsgrenze nicht genau berechnet hat.
Codierung
- Hier sollte wohl ein Blockbild des Codierers folgen...
Aufgaben
Aufgabe(n) - LZPP-Codierung
- [M30] Implementieren Sie diesen Codierer und vergleichen Sie die Effizienz mit der des LZSS-Algorithmus und mit der des LZ77-Algorithmus.
- [M39] Überlegen Sie wie dieses Verfahren verbessert werden kann und erläutern Sie die Modifikation.
- [M25] Kann dieses Verfahren mit einem kombiniert werden, welches nach einem LRU-Prinzip Tabellenindexe entfernt?
Decodierung
- Hier ein Blockbild des Decodierers
Aufgaben
Aufgabe(n) - LZPP-Decodierung
- [M20] Vergleichen Sie die Komplexität des Decoders mit der des Codierers. Zu welchen Ergebnissen kommen Sie? Wie wirkt sich die Komplexität des Codierers auf die des Decoders aus ?
Codierergebnisse mit dem Calgary Corpus
| Calgary Corpus - Resultate Quelle: Pawel Pylak - Efficient Modification of LZSS compression algorithm Angaben in Bit pro Zeichen | |||
| LZSS | LZPP | PPMZ 2.0.8 | |
| bib | 2,8517 | 2,3483 | 1,7179 |
| book1 | 3,7044 | 2,8931 | 2,1951 |
| book2 | 3,0408 | 2,4275 | 1,8428 |
| geo | 7,1234 | 4,8293 | 4,5784 |
| news | 3,5360 | 2,6690 | 2,2051 |
| obj1 | 4,7515 | 3,7403 | 3,6667 |
| obj2 | 3,2906 | 2,4553 | 2,2412 |
| paper1 | 3,3354 | 2,7127 | 2,1220 |
| paper2 | 3,3732 | 2,7675 | 2,1846 |
| progc | 3,3051 | 2,6421 | 2,2567 |
| progl | 2,2813 | 1,7786 | 1,4471 |
| progp | 2,3049 | 1,7590 | 1,4489 |
| trans | 2,0737 | 1,5395 | 1,2146 |
| Mittel | |||
Wie sie rechts sehen können, liegt der LZPP-Algorithmus mit seiner Effizienz etwa in der Mitte zwischen LZSS und PPMZ. Daraus kann man schlussfolgern, dass die von Pawel Pylak empfohlenen Modifikationen längst nicht ausreichen, um ein sehr effizientes Verfahren zu implementieren. LZPP verzichtet aber auf Kontextmodelle mit einer höheren Ordnung als 1. PPMZ benutzt Kontextmodelle höherer Ordnung und kann damit gegenüber LZPP etwa das herausholen, was LZPP gegenüber dem LZSS Algorithmus als Codiervorteil gewinnen kann.
Aber es ist doch sehr überraschend, dass ein Algorithmus der sich allein der statistischen Eigenschaften des nicht optimalen LZSS-Algorithmus annimmt, derart hohe Codiervorteile bietet. Es soll jedoch nicht unerwähnt bleiben, dass die Ergebnisse durch die Verwendung eines nachgeschalteten arithmetischen Codierers erreicht wurden. Eine Entropiecodierung bspw. mit dem Huffman Algorithmus hätte einen sehr viel geringeren Effekt gehabt.
Bewertung
Dieser Algorithmus wird in den nächsten Jahren wohl schnell wieder vergessen werden, da eine Kontextmodellierung algorithmisch auf sehr vielfältige Weise implementierbar ist. Allein durch Verwendung der Kontextmodellierung erzielt man ähnlich gute und teilweise bessere Ergebnisse.
Diesen Algorithmus könnte man sicherlich durch Hinzufügen eines Kontextmodells höherer Ordnung verbessern, wobei der Ansatz mit einem solcherart 'optimierten' Algorithmus zu beginnen und ihn anschließend zu verfeinern sicherlich nicht hilfreich ist, um es nicht sofort als Sackgasse zu bezeichnen. Da sind Ansätze, die mit einem unmodifizierten LZ77/LZ78/LZP/AC beginnen, wesentlich aussichtsreicher und motivierender.
Weblink auf den Artikel