Proseminar: Redundanz

Vortrag 5: Lempel Ziv

Maximilian Hrabowski

Grundlagen

Einführung in die Datenkompression

Auf der einen Seite wird zwar versucht, die Fehlertoleranz in der Datenfernübertragung durch künstliches Erzeugen von Redundanz zu erhöhen, auf der anderen Seite wollen im Zeitalter der modernen Telekommunikation und globalen Vernetzung aber immer mehr Benutzer immer mehr Daten untereinander austauschen. Ohne eine effiziente Datenkompression wären die Grenzen der Leitungskapazitäten wesentlich schneller erreicht, als dies in der Praxis augenblicklich schon der Fall ist.
Aus diesem Grund haben schon sehr viele Programmierer Versuche unternommen, bestehende Methoden der Datenkompression zu verbessern bzw. neue Methoden zu entwickeln, so daß heute eine Vielzahl verschiedener Algorithmen existiert. Methoden der Datenkompression lassen sich grob in verlustfreie und verlustbehaftete Methoden unterscheiden. Bei den verlustbehafteten Methoden tritt nach vollendeter Dekompression ein Informationsdefizit auf, bei den verlustfreien dagegen nicht. Verlustbehaftete Methoden werden hauptsächlich zur Kompression von Audio- und Videodaten eingesetzt, wogegen verlustfreie Methoden überall dort eingesetzt werden müssen, wo es auf exakte Informationswiedergabe ankommt.
Vertreter der verlustfreien Gattung sind zum Beispiel die Huffman-Kodierung, die arithmetische Kodierung, die häufig eingesetzte Lauflängenkodierung und eben die Gruppe der Lempel-Ziv-Kodierungen. Der Name Lempel-Ziv bezeichnet nämlich nicht nur einen Algorithmus zur Datenkompression, sondern die Basis für eine ganze Gruppe von sich in einigen wenigen Details unterscheidenden Kompressionsmethoden. Der Name geht zurück auf die beiden Entwickler der "Urform" aller zur Lempel-Ziv-Familie gehörenden Algorithmen, Abraham Lempel und Jacob Ziv.
Abraham LempelJacob Ziv
Alle heute gebräuchlichen (und existenten) Varianten basieren auf diesen Ende der 70er Jahre entwickelten und erstveröffentlichten Grundformen, die im folgenden als LZ-Algorithmen bezeichnet werden sollen.

Eigenschaften der Redundanz

Die LZ-Algorithmen sind substituierende Kompressoren. Die Funktionsweise substituierender Kompressoren ist, schon einmal im Eingabedatenstrom vorgekommene Zeichenketten durch eine Referenz auf ihr vorheriges Auftreten zu ersetzen. In der Theorie unterscheiden sich die unterschiedlichen Varianten der LZ-Algorithmen in der Methode, wie sie im Eingabedatenstrom enthaltene Redundanz erfassen und substituieren. So gibt es verschiedene Arten von Redundanz, die, je nach Art der Daten, mehr oder weniger häufig auftreten.
Eine häufig in Bilddateien vorkommende Art der Redundanz, ist eine Zeichenkette gleicher aufeinanderfolgender Zeichen z.B. ( AAAAAAAAAAAA......). Ein sehr gutes Beispiel für diese Form der Redundanz findet man auch bei Faxen. Eine Faxvorlage wird nur zweifarbig abgetastet. Dadurch entsteht eine Bildrasterdatei die nur aus Folgen von Nullen und Einsen besteht. Wiederauftretende Muster dagegen sind eine Form der Redundanz, wie man sie häufig in Textdateien vorfindet. So kommt im vorherigen Satz z.B. 4mal das Muster "de" und 4mal das Muster "en" vor. Als Beispiel überlege man sich ferner, wie oft das Wort "Herr" oder "und" in der Bibel zu finden ist.
Das Problem der örtlichen Redundanz
Redundanz muß nicht immer gleichmäßig über einen gesamten Datensatz verteilt sein. Vielmehr gibt es z.B. in einem Bild einen Bereich, in dem völlig andere Farben vorkommen, wie in einem anderen Bereich. Ist nun ein Algorithmus nicht in der Lage sich während der Kodierung an auftretende Daten anzupassen, kann die Effizienz beträchtlich darunter leiden. Dies ist auch der Grund, warum es bis zum heutigen Zeitpunkt so viele verschiedene LZ-Varianten gibt. Jede Variante wurde auf bestimmte Arten von Daten (und so auch Redundanz) hin optimiert. Denn allgemein gilt:
Es gibt kein Verfahren, daß jede Art von Daten beliebigen Ursprungs gut komprimieren kann.

Der Lempel Ziv Algorithmus

Trotz der großen Vielfalt haben alle LZ-Algorithmen einige gemeinsame Eigenschaften: Grundsätzlich muß man die LZ-Algorithmen in zwei Hauptgruppen einteilen:
  1. Die erste Gruppe versucht die zu komprimierende Zeichenfolge in der schon verarbeiteten Datenmenge zu finden. Anstatt einer Wiederholung wird dann lediglich ein Zeiger auf das letzte Auftreten derselben abgespeichert. Das Wörterbuch wird also durch die bereits verarbeitete (d.h.erzeugte) Datenfolge repräsentiert (implicit dictionary). Alle Varianten des LZ77-Verfahrens gehören in diese Gruppe.
  2. Die zweite Gruppe erzeugt bei der Kompression ein Wörterbuch aus Zeichenfolgen, die in den Quelldaten auftreten. Wird dann eine auftretende Zeichenfolge im Wörterbuch gefunden, gibt der Kompressor nur den Index der Zeichenfolge aus. Dieses Wörterbuch, und das ist das Besondere an LZ, kann während des Dekompressionsvorganges wieder reproduziert werden.
    Alle Varianten des LZ78-Verfahrens gehören in diese Gruppe.
Im Folgenden werden die fundamentalen LZ-Algorithmen zusammen mit ihren wichtigsten Varianten erläutert. Dabei soll für folgende Begriffe gelten:


Der LZ77 Algorithmus

Der LZ77-Algorithmus wurde 1977 (daher der Name) publiziert, und war der erste von A. Lempel und J. Ziv entwickelte LZ-Algorithmus.
Da es zuviel Rechenzeit in Anspruch nehmen würde, immer die gesamten verarbeiteten Daten nach einem Muster zu durchsuchen, legt dieses Verfahren ein Datenfenster auf den Eingabedatenstrom, und durchsucht nur dieses nach Übereinstimmungen. Dieses Datenfenster wird analog zur Abarbeitung der Eingabedaten verschoben, so daß immer die n zuletzt gelesenen Zeichen der Mustererkennung zu Verfügung stehen.

Der Kompressor durchsucht also das Datenfenster nach der längsten Zeichenkette, die mit der an der Kodierungsposition beginnenden Zeichenkette, übereinstimmt. Da jedoch die Möglichkeit besteht, daß überhaupt keine Übereinstimmung im Datenfenster gefunden wird, reicht es nicht aus, lediglich den Zeiger (gemeint ist das Tupel (Position,Länge)) auszugeben. Also gibt der Kompressor nach dem Zeiger noch das erste Zeichen im Vorausschaupuffer nach der übereinstimmenden Zeichenkette aus. Hat der Kompressor in der Tat überhaupt keine Übereinstimmung gefunden, so gibt er einen Null-Zeiger (0,0) gefolgt vom Zeichen an der Kodierungsposition aus.
Der Algorithmus in Einzelschritten:
  1. Setze die Kodierungsposition auf den Anfang des Eingabedatenstrom
  2. Finde die längste Übereinstimmung im Datenfenster mit der an der Kodierungsposition beginnenden Zeichenkette im Vorausschaupuffer.
  3. Gebe den Zeiger auf die Übereinstimmung im Datenfenster und das erste nicht passende Zeichen im Vorausschaupuffer aus.
  4. Ist das Ende des Eingabedatenstroms noch nicht erreicht, dann bewege die Kodierungsposition (und somit auch das Datenfenster) um l+1 Zeichen weiter (l bezeichnet die Länge der zuletzt gefundenen Zeichenkette), und fahre bei 2. fort.

Beispiel
Kleinbuchstaben: Inhalt des Datenfensters
Großbuchstaben: Inhalt des Vorausschaupuffers
Ausgabe: (Position,Länge)Zeichen
Position 012345678
EingabedatenstromAABCAAABC

Kodierungsvorgang
KodierungspositionDatenfenster:VorausschaupufferPosition:ÜbereinstimmungAusgabe
0:AABCAAABC-(0,0)A
1a:ABCAAABC0:A(0,1)B
3aab:CAAABC-(0,0)C
4aabc:AAABC0:AA(0,2)A
7aabcaaa:BC3:BC(2,1)C(*)
(*) Hier wird anstatt der gefundenen Zeichenkette "BC" nur der Kode für "B" und das Zeichen "C" ausgegeben, da der Dekodierer immer einen Kode und ein Zeichen in Folge erwartet. Wäre hier nicht das Ende des Eingabedatenstromes erreicht, würde natürlich der Kode für "BC" ausgegeben werden.

Dekompression

Der Dekompressionsvorgang ist trivial: Das Datenfenster wird auf dieselbe Weise gehandhabt, wie bei der Kodierung. Der Dekodierer gibt zuerst die durch (Position,Länge) angegebene Zeichenkette aus, anschließend das dem Zeiger nachgestellte Zeichen.
Eingabedatenstrom(0,0)A(0,1)B(0,0)C(0,2)A(2,1)C

Dekodierungsvorgang
EingabeDatenfenster:Ausgabe
(0,0)A-:A
(0,1)Ba:AB
(0,0)Caab:C
(0,2)Aaabc:AAA
(2,1)Caabcaaa:BC

Der LZSS Algorithmus

Der LZSS-Algorithmus ist eine Weiterentwicklung des LZ77-Algorithmus, der letzendlich zur Basis praktisch aller LZ-Varianten der ersten Gruppe wurde. Er benötigt praktisch dieselbe Menge Speicher und Rechenzeit wie der LZ77-Algorithmus, allerdings bei höherer Effizienz. Er ist im Jahre 1982 von Storer und Szymanski publiziert worden.
Unterschiede zu LZ77
Der LZ77-Algorithmus löst das Problem keine Übereinstimmung im Datenfenster zu finden, indem er jedem Zeiger noch explizit ein Zeichen nachstellt. Findet er keine Übereinstimmung, so erzeugt er eine neue Redundanz: Entweder der Null-Zeiger ist redundant, oder das nachgestellte Zeichen, daß ja in der nächsten Übereinstimmung enthalten sein könnte.

Der LZSS-Algorithmus löst dieses Problem auf eine andere Art und Weise: Es wird nur ein Zeiger ausgegeben, wenn die Übereinstimmung länger ist als der Zeiger, ansonsten werden die Zeichen explizit angegeben. Da der Ausgabestrom nun in ungeordneter Form Zeiger und Zeichen enthält, benötigt man zur Unterscheidung ein weiteres sog. Identifikations-Bit (Id-Bit).

Der Algorithmus in Einzelschritten:
  1. Setze die Kodierungsposition auf den Anfang des Eingabedatenstrom
  2. Finde die längste Übereinstimmung im Datenfenster mit der an der Kodierungsposition beginnenden Zeichenkette im Vorausschaupuffer.
  3. Ist l >= Länge eines Zeigers ?
  4. Ist das Ende des Eingabedatenstroms noch nicht erreicht, dann gehe zurück zu 2.
Dekodierung
Der Dekodierer stellt zuerst anhand des Id-Bits fest, ob ein Zeiger oder ein Zeichen folgt; Zeichen werden einfach ausgegeben, ein Zeiger wird analog zum LZ77-Algorithmus behandelt.

Der LZ78 Algorithmus

Der LZ78-Algorithmus ist die zweite von A. Lempel und J. Ziv entwickelte substituierende Kompressionsmethode, der die Basis für alle Algorithmen der zweiten Gruppe wurde. Im Gegensatz zum LZ77-Algorithmus, referenziert der LZ78-Algorithmus keine Zeichenketten über Zeiger im Datenfenster, sondern er benutzt eindeutige Kodes, die einen Index auf ein Wörterbuch darstellen, das während des Kodier- und Dekodiervorganges aufgebaut wird.
Kompression
Zu Beginn der Kompression ist das Wörterbuch und die Präfix-Zeichenkette leer. Der Kompressor liest nun ein Zeichen "z" aus dem Eingabedatenstrom. Ist die Zeichenkette "Präfix+z" im Wörterbuch enthalten, so wird der Präfix um z erweitert. Dieses Einlesen und Erweitern wird solange fortgesetzt, bis "Präfix+z" nicht im Wörterbuch enthalten ist. In diesem Fall werden dann der den Präfix repräsentierende Kode und das momentante Zeichen z ausgegeben. Schließlich wird "Präfix+z" noch im Wörterbuch eingetragen und der Kompressor beginnt mit einem neuen Präfix. Ein Spezialfall liegt vor, wenn der Präfix leer ist und z nicht im Wörterbuch vorkommt. Dann wird ein spezieller Kode, der einen leeren String repräsentiert, und z ausgeben. Schließlich wird z in das Wörterbuch eingetragen.
Der Algorithmus in Einzelschritten
  1. Zu Beginn sind Präfix und das Wörterbuch leer.
  2. z := nächstes Zeichen aus dem Eingabedatenstrom
  3. Ist "Präfix+z" im Wörterbuch ?
  4. Ist das Ende des Eingabedatenstroms erreicht ?
Beispiel
Kleinbuchstaben: Schon verarbeitete Zeichen
Großbuchstaben: Noch zu verarbeitende Zeichen
Ausgabe: Kode, Zeichen
Position 012345678
EingabedatenstromAABCAAABC

Kodierungsvorgang
Positionverarbeitet:nicht verarbeitetKode:WörterbucheintragAusgabe
0:AABCAAABC1:A0,A
1a:ABCAAABC2:AB1,B
3aab:CAAABC3:C0,C
4aabc:AAABC4:AA1,A
6aabcaa:ABC5:ABC2,C

Dekodierung
Bei der Dekodierung wird das Wörterbuch genau auf dieselbe Weise aufgebaut wie bei der Kompression. Nach der Dekompression ist das Wörterbuch identisch mit dem nach der Kodierung. Im folgenden bezeichne "K" die zu K gehörige Zeichenkette.
  1. Zu Beginn ist das Wörterbuch leer.
  2. K := der nächste Kode aus dem Eingabedatenstrom
  3. z := das darauffolgende Zeichen
  4. Gib die durch K im Wörterbuch repräsentierte Zeichenfolge (kann leer sein) und anschließend z aus.
  5. Trage "K"+z im Wörterbuch ein.
  6. Wenn das Ende des Eingabedatenstroms noch nicht erreicht ist, gehe zu Schritt 2.
Eingabedatenstrom0,A1,B0,C1,A2,C

Dekodierungsvorgang
EingabeWöterbucheintragAusgabe
0,A1:AA
1,B2:ABaAB
0,C3:CaabC
1,A4:AAaabcAA
2,C5:ABCaabcaaABC

Der LZW Algorithmus

Der LZW-Algorithmus ist eine Weiterentwicklung des LZ78-Algorithmus, die im Jahre 1984 von Terry Welch publiziert wurde. Welch entwickelte dieses Verfahren zur Hardwareimplementierung. Daher mußte es sowohl bei der Kompression als auch bei der Dekompression eine hohe Arbeitsgeschwindigkeit erreichen. Außerdem sollte es möglichst unabhängig von der Art der auftretenden Redundanz annehmbare Kompressionsraten erreichen. Der Lempel-Ziv-Welch-Algorithmus ist die bekannteste LZ-Variante und wird deshalb fälschlicherweise oft als der Lempel-Ziv Algorithmus bezeichnet.
Der wesentliche Unterschied zum LZ78-Algorithmus besteht darin, daß nur noch Kodes und keine Zeichen mehr ausgegeben werden. Dies setzt allerdings voraus, daß zu Beginn der Kodierung/Dekodierung für jedes im Eingabealphabet vorkommende Zeichen ein entsprechender Eintrag im Wörterbuch existiert. Da deshalb jede Kodierung mit einem Präfix der Länge "1" beginnt, sucht der Kodierer im Wörterbuch immer zuerst nach Zeichenketten der Länge "2". Außerdem muß das erste Zeichen des neuen Präfix mit dem letzten Zeichen der zuvor eingetragenen Zeichenkette identisch sein, da dem Dekodierer sonst dieses Zeichen, das beim LZ78-Algorithmus explizit ausgegeben wurde, fehlt, und er so das Wörterbuch nicht korrekt aufbauen könnte.
Der Algorithmus in Einzelschritten
  1. Zu Beginn ist der Präfix leer, das Wörterbuch enthält für jedes im Dateneingabestrom vorkommendes Zeichen einen Eintrag.
  2. z := nächstes Zeichen aus dem Eingabedatenstrom
  3. Ist "Präfix+z" im Wörterbuch ?
  4. Ist das Ende des Eingabedatenstroms erreicht ?
Dekodierung
Bei der Dekodierung eines LZ78-Kodes, wurde der nächste Wörterbucheintrag aus dem zuletzt übersetzten Kode und dem angehängten Zeichen gebildet. Da bei der LZW-Kodierung keine Zeichen mehr explizit ausgegeben werden durften, mußte der LZW-Kode so konzipiert werden, das der Dekodierer immer noch die Möglichkeit hat, das Wörterbuch korrekt aufzubauen. Dieses Problem wurde mit der Vereinbarung gelöst, daß das erste Zeichen eines neuen Wörterbucheintrages identisch sein muß mit dem letzten Zeichen des Vorhergehenden. Dadurch hinkt der Dekodierer dem Kodierer bei der Erstellung des Wörterbuches allerdings einen Eintrag hinterher, da er einen neuen Eintrag erst dann vornehmen kann,wenn er den nächsten Kode übersetzt hat, weil er ja dessen erstes Zeichen benötigt. Deshalb kann es vorkommen, das der Dekodierer einen Kode einliest, der noch nicht im Wörterbuch eingetragen worden ist.
Dieser Fall tritt nur dann auf, wenn im Eingabedatenstrom des Kodierers eine Zeichenfolge der Form ZwZ aufgetreten ist.Dabei sei Z ein beliebiges Zeichen und w eine beliebige Zeichenfolge.
Voraussetzung ist allerdings, daß die Zeichenkette "Zw" bereits einen Eintrag  im Wörterbuch hat. Also weiß der Dekodierer wie der fehlende Eintrag zusammengesetzt werden muß:
Die zuletzt ausgegebene Zeichenkette konkateniert  mit ihrem ersten Zeichen (eben ZwZ!).
  1. Das Wörterbuch enthält zu Beginn für jedes im Eingabedatenstrom vorkommende Zeichen einen Eintrag.
  2. K := erster Kode aus dem Eingabedatenstrom (bez. immer ein Zeichen)
  3. Gib "K" aus.
  4. merke K in aK.
  5. K := nächster Kode im Eingabedatenstrom
  6. Ist "K" im Wörterbuch ?
  7. Ist das Ende des Eingabedatenstroms noch nicht erreicht, dann gehe zu Schritt 4.
Beispiel für die Dekodierung
Nachricht:ABBABABAC
Kodierte Nachricht:122473
Wörterbuch:(1)=A (2)=B (3)=C (4)=AB (5)=BB (6)=BA (7)=ABA (8)=ABAC

Das Wörterbuchenthält zu Beginn: (1)=A (2)=B (3)=C
KodeAusgabeNeuer Eintrag
1A-
2B(4)=AB
2B(5)=BB
4AB(6)=BA
3ABA(7)=ABA (hier sind Ausgabe und neuer Eintrag indentisch!)
7C(8)=ABAC

Varianten

Im folgenden werden die wichtigsten Varianten der Lempel-Ziv Familie erläutert. Sie entstanden entweder aus der Absicht heraus Redundanz im erzeugten Kode noch weiter zu reduzieren, oder den Algorithmus auf eine spezielle Art der Redundanz innerhalb des Eingabedatenstroms hin zu optimieren.

LZSS mit adaptiver arithmetischer Kodierung

Im Ausgabekode eines LZSS-Kompressors verhält es sich meist so, daß z.B. das Zeichen "e" häufiger vorkommt als das Zeichen "j". Ebenso wird ein Zeiger (Position,Länge) mit der Länge 3 meistens häufiger vorkommen als ein Zeiger (Position,Länge) mit der Länge 18. Diesen Umstand nutzt die arithmetische Kodierung, indem sie häufig vorkommende Kodes/Zeichen mit einer geringen Anzahl von Bits darstellt, selten vorkommende Kodes mit einer großen Anzahl Bits.

LZSS mit adaptiver Huffman Kodierung

Hierbei wird lediglich die arithmetische Kodierung durch eine adaptive Huffman Kodierung ersetzt. Die Kompressionsrate ist fast gleich, diese Variante arbeitet jedoch wesentlich schneller. Das bekannte Archivierugnsprogramm LHArc benutzt diese Variante.

LZC

Der LZC-Algorithmus ist eine Weiterentwicklung des LZW-Algorithmus. Eine Standard-LZW Implementierung benutzt ein Wörterbuch mit 4096 Einträgen, was einer notwendigen Kodegröße von 12 Bit entspricht, um die gesamte Tabelle adressieren zu können. Der LZC-Algorithmus beginnt nun mit einer Kodegröße von 9 Bit und erweitert diese mit dem Wachsen des Wörterbuches dynamisch auf 12 Bit. In der Praxis erreicht der LZC-Algorithmus damit eine um ca. 6% bessere Kompressionsrate.
Ein Nachteil des Standard-LZW Verfahrens ist ferner, daß wenn das Wörterbuch einmal voll ist, der Kompressor damit auskommen muß. LZC dagegen ist in der Lage ein unbrauchbares bzw. uneffektives Wörterbuch zu löschen und ein neues aufzubauen (Berücksichtigung örtlicher Redundanz).
Das GIF-Format bedient sich im wesentlichen dieser Kodierung, und auch das Unix-Kompressionstool compress verwendet dieses Verfahren.

LZMW

Der LZMW-Algorithmus versucht die Anpassung des Wörterbuches an die Eingabedaten schneller abzuwickeln als der LZW- und LZC-Algorithmus. Während bei LZW jede Zeichenkette um maximal ein Zeichen verlängert werden kann, sucht LZMW die längste bekannte Zeichenkette die mit der nachfolgenden Eingabe übereinstimmt und hängt diese an den letzten Präfix an. In der Praxis erreicht der LZMW-Algorithmus damit lediglich eine bessere Einstellung auf gleiche aufeinanderfolgende Zeichen (siehe Eigenschaften von Redundanz).

Beispiel
Eingabedatenstrom: AAAAAAAAAAAAAAAAAAA
LZW erzeugtes WörterbuchLZMW erzeugtes Wörterbuch
(0)=A(0)=A
(1)=AA(1)=AA
(2)=AAA(2)=AAAA
(3)=AAAA(3)=AAAAAAAA
(4)=AAAAA-
Ausgabe LZWAusgabe LZMW
0,1,2,3,4,30,1,2,3,2

Ein Praxisvergleich

Abschließend folgt nun hier ein praktischer Vergleich der Kompressionsraten verschiedener LZ-Varianten. In der ersten Spalte der Tabelle ist die Art der Roh-Datei vermerkt:
In der ersten Zeile sind die verwendeten Kompressionsverfahren angegeben. Die einzelnen Felder der Tabelle geben schließlich die Größe der Datei in Bytes und eine Prozentangabe bezüglich der unkomprimierten Größe an.

Der Unterschied der Kompressionsraten zwischen LZSS mit 4KB-Fenster und der LZC-Implementierung ist dabei besonders signifikant. Bei gleicher Kode- bzw. Zeiger-Länge von 12 Bit, erkennt man deutlich die Vor- und Nachteile der LZ78-Gruppe gegenüber der LZ77-Gruppe:
Hat der LZSS-Algorithmus bei normalen Text- und Programmdateien mit häufig wiederkehrenden Mustern noch die Nase vorne, schlägt ihn die Variante des LZ78-Algorithmus bei Bilddaten mit häufigen Zeichenwiederholungen.

Datenursprung Größe
der
Rohdatei		 LZSS
mit
4KB Fenster 		LZSS mit
adaptivem Huffman
(LHArc)		 LZSS mit
arithmetischer
Kodierung		 LZC 12-bit
Wörterbuch
4096 Einträge
Text Englisch 878.279
100%		 303.321
34.54%		 258.873
29.48%		 257.607
29.33%		 377.505
42.98%
EXE-Datei 186.368
100%		 101.183
54.29%		 90.300
48.45%		 90.036
48.31%		 116.710
62.62%
20MB Nullen 20.971.520
100%		 2.475.807
11.81%		 436.986
2.08%		 402.307
1.92%		 15.763
0.08%
bild.jpg 924.094
100%		 1.038.078
112.33%		 923.353
99.92%		 921.307
99.70%		 1.252.606
135.55%
Bild interleaved 10.591.560
100%		 10.121.634
95.56%		 8.120.250
76.67%		 8.088.479
76.37%		 10.383.648
98.04%
Bild non-interleaved 10.591.560
100%		 7.901.611
74.60%		 7.033.430
66.41%		 6.987.937
65.98%		 7.506.043
70.87%

Abschließend läßt sich sagen, daß die Familie der LZ-Algorithmen ein mächtiges Werkzeug zur Datenkompression darstellt. Zahlreiche auf spezielle Redundanzarten optimierte Varianten lassen erwarten, daß auch in Zukunft noch neue Verfahren entwickelt bzw. bestehende weiter verbessert werden. Außerdem erschließt die Kombination mit anderen Verfahren (z.B. Huffman, arithmetische Kodierung) neue Möglichkeiten deutlicher Kompressionssteigerung (siehe auch Newsgroup comp.compression.research).

Literatur

Maximilian Hrabowski

19.01.1999