Institut für Rechnerentwurf
und Fehlertoleranz
Lehrstuhl Prof. Görke
Proseminar SS95
REDUNDANZ
Fehlerkorrigierende und datenkomprimierende Kodierungen
Bearbeitet von: Marek Tomczyk (E-Mail: Marek.Tomczyk@stud.uni-karlsruhe.de)
Betreuer: Malte Borcherding
Gerade in der heutigen Zeit, in der durch weltweite Vernetzung von Rechnern immer mehr Daten übertragen werden müssen, sind Kompressionsverfahren ein unerläßliches Werkzeug zur optimalen Ausnutzung der immer knappen Leitungskapazitäten. Es existieren mittlerweile unzählige Implementierungen von diversen Kompressionsalgorithmen, die grob in zwei Gruppen unterteilt werden können: Zum einen sind es Verfahren die verlustbehaftet arbeiten, d.h. ein Teil der Information beim Komprimiervorgang unwiderruflich verlorengeht. Die andere Gruppe sind verlustfreie Methoden, d.h. der Originalzustand der gepackten Daten kann 1 zu 1 wiederhergestellt werden.
Die hier beschriebene Lempel-Ziv-Kodierung gehört zur Gruppe der verlustfreien Kompressionsmethoden. Als weitere Vertreter dieser Gruppe seien beispielsweise auch der Huffmanncode oder die Lauflängenkodierung erwähnt.
1.1
Begriffserklärung - Redundanz
Das grundsätzliche Ziel aller Komprimierungsverfahren, und insbesondere des LZ-Verfahrens, ist es, redundante Daten im Eingabestrom durch kürzere Zeichenfolgen zu ersetzen. Da Redundanz an sich ein sehr weitgefaßter Begriff ist, soll in den folgenden Abschnitten 1.1.1 - 1.1.4. ein kurzer Überblick über vier wichtige Redundanzarten gegeben werden.
Um es gleich vorwegzunehmen: es gibt kein universelles Kompressionsverfahren das für alle Arten von Redundanz optimal wäre. Vielmehr gibt es eine Reihe Spezialverfahren, die auf eine bestimmte Redundanzart hin optimiert werden können.
Die Verteilung der Redundanz bezogen auf das Alphabet kann von Datensatz zu Datensatz sehr variieren. In sprachlichen Texten kommt z.B. das 'e' sehr häufig vor; im Gegensatz dazu sind in Tabellenkalkulationsdateien mehr Zahlen anzutreffen. Bei Dateien mit Felddefinitionen in numerischen Anwendungen kann man bei vielen Systemen davon ausgehen, daß BCD-Zahlen sehr wahrscheinlich sind. Die Einzelzeichenverteilung über dem Eingabealphabet ist daher meistens nicht zufällig, sondern hängt sehr stark vom Ursprung der Daten ab.
1.1.2
Wiederholung von Einzelzeichen
Zeichenketten mit gleichen, aufeinanderfolgenden Zeichen ist eine weitere Art von Redundanz (z.B. aa...a). Solche Zeichenketten kommen bei Bildern aus CAD-Anwendungen relativ häufig vor. Die Lauflängenkodierung ist hierfür ein sehr geeignetes Kompressionsverfahren.
In Textdateien sind Musterwiederholungen vielfach anzutreffen. Die Zeichenfolge 'ie' kommt im vorigen Satz beispielsweise gleich dreimal vor. Die Häufigkeit von Mustern ist stark von der Textart abhängig; so ist die Zeichenfolge 'die' in deutschen Texten viel häufiger anzutreffen als in englischen. In Firmendaten kann u.U. der Firmenname ein anderes häufig wiederkehrendes Muster sein. Diese Art von Redundanz ist mit der Zeichenverteilung verwandt und ist eine Erweiterung davon.
Die Häufigkeit des Vorkommens eines bestimmten Wertes oder einer Zeichenkette kann auch von der relativen Lage in einer Datei abhängen. Bei einer Grafikdatei, die nur waagrechte Linien enthält, sind Wiederholungen von Zeichen (Farbwerten) auf ganz bestimmte Bildbereiche beschränkt und somit von darauf optimierten Spezialverfahren gut erfaßbar. Ortsredundanz kann sowohl positive wie auch negative Auswirkungen auf die Effizienz der Kompressionsverfahren haben. Bei schlecht angepaßten Algorithmen kann bei dieser Art von Redundanz die Kompressionsleistung beträchtlich unter dem Optimum bleiben.
Mittlerweile gibt es weit mehr als nur einen Lempel-Ziv Algorithmus. Seit der Veröffentlichung der Originalarbeiten von Abraham Lempel und Jacob Ziv 1977 und 1978 ([LZ77] und [LZ78]) sind darauf basierend unzählige Abwandlungen jenes Kompressionsverfahrens entstanden. Die bekannteste ist sicherlich die LZW-Kodierung, die 1984 von Terry A. Welch vorgestellt wurde. Sie ist sogar so populär, daß man sie oft fälschlicherweise als DIE "Lempel-Ziv-Kodierung" bezeichnet. Aufgrund der starken Verbreitung von LZW soll dieses Verfahren in der vorliegenden Ausarbeitung auch den größten Rahmen bekommen. Erwähnt werden aber auch seine wichtigsten Abwandlungen sowie andere Verfahren aus der Lempel-Ziv-Familie die nicht im LZW-Verfahren ihren Ursprung fanden sondern auf den Originalverfahren von Lempel und Ziv basieren.
Allen LZ Verfahren gemeinsam ist die oben schon angedeutete Verlustfreiheit bei der Kodierung. Der Hauptunterschied zu anderen verlustfrei arbeitenden Verfahren ist die Tatsache, daß der LZ-Algorithmus keine Informationen über die zu komprimierende Nachrichtenquelle zu besitzen braucht. Als Konsequenz davon, brauchen auch kein Wörterbuch oder keine sonstigen Daten über die Nachricht an den Kompressor übertragen zu werden. Das zum Dekomprimieren nötige Wörterbuch wird bei fast allen LZ-Verfahren (bei LZ77 kann man nicht unbedingt von einem Wörterbuch sprechen) implizit im Laufe der Dekodierung aus dem Datenstrom gewonnen. Die LZ-Verfahren können aufgrund ihrer Eigenschaften so implementiert werden, daß sie für den Benutzer transparent sind. Datenkompression wird bei LZ-Verfahren durch Ersetzung von redundanten Zeichenketten durch kürzere Codes erreicht. Die Art und Weise wie Reundanz vom Kompressor erkannt wird, und wie das Wörterbuch im einzelnen erzeugt und verwaltet wird, ist der Hauptunterscheidungsmerkmal der einzelnen LZ-Derivate.
Dieses Verfahren wurde in [LZ77] vorgestellt. LZ77 führt ein "Fenster" über die Eingabedaten und sucht im Eingabestrom nach Mustern, die in diesem "Fenster" schon gesehen worden sind. In diesem Fall wird anstatt der Eingabe nur der Index und die Länge des Musters im "Fenster" ausgegeben. Eine bekannte Implementierung von LZ77 ist der von James Storer und Thomas Szymanski 1982 entwickelte LZSS-Algorithmus. Eine weitere Verbesserung von LZSS erreicht man, indem seine Ausgabe mit Hilfe anderer Kompressionsverfahren nochmals verdichtet wird. Dazu kann einfache Kodierung mit variabler Codelänge benutzt werden (LZB), dynamische Huffman Kodierung (LZH) oder auch Shannon-Fano Kodierung (ZIP 1.x). Dies ist vor allem dann nützlich, wenn die Daten sehr zufällig sind und deshalb der LZSS Algorithmus nur wenig komprimiert. Bekannte Implementierungen des LZ77-Verfahrens sind die folgenden Packprogramme: arj, lha, zip, zoo [COMP.FAQ]
Hier wird außer dem "Fenster" noch ein Vorschaubuffer benutzt. Der Kompressor versucht, den Inhalt des Vorschaubuffers im "Fenster" wiederzufinden und entsprechend die Indizes auszugeben. Die Dekompression geht schnell und einfach vor sich: wann immer das Tupel (Position, Länge) im Datenstrom entdeckt wird, werden (Länge) Bytes von der (Position) im Fenster zur Ausgabe kopiert. [COMP.FAQ]
LZ78 liest zeichenweise Eingabedaten und versucht, eine möglichst lange Zeichenkette in einem Wörterbuch zu finden. Dieses Wörterbuch ist anfangs leer und wird im Laufe des Kodierungsvorgangs aufgebaut. Kann eine Zeichenfolge noch nicht im Wörterbuch gefunden werden, so wird sie an die nächstfolgende freie Stelle eingetragen. Gleichzeitig wird sie zur Ausgabe kopiert. Ist die Zeichenkette im Wörterbuch verzeichnet wird hingegen ihre Indexnummer ausgegeben. LZ78 wurde 1987 von Lempel und Ziv vorgestellt [LZ78].
Wie schon weiter oben angedeutet ist LZW das bekannteste Lempel-Ziv-Verfahren schlechthin. Es ist sehr weit verbreitet und hat wahrscheinlich im Felde der LZ-Verfahren die meisten Varianten und Verbesserungen erfahren. Auch heutzutage ist LZW immer noch interessant genug um Entwicklungen auf seiner Basis zu führen.
Terry A. Welch hat LZW mit dem Hintergedanken einer Hardwareimplementierung entwickelt. Für diesen Zweck muß der zugehörige Algorithmus einigen Voraussetzungen genügen. Zum einen muß er für den Benutzer und das Computersystem transparent sein. Zum anderen muß die Kompression und Dekompression sehr schnell sein. Für eine universelle Nutzung der Hardware soll die Komprimierung außerdem ungeachtet der im Datenstrom auftretenden Redundanzarten (siehe 1.1.1-1.1.4) möglichst optimal sein. LZW erfüllt diese Voraussetzungen aufgrund seiner Struktur weitestgehend. Die Funktionsweise des Verfahrens soll nachfolgend anhand von Beispielen vorgestellt werden.
LZW basiert sehr stark auf dem LZ78-Verfahren von Lempel und Ziv [LZ78]. Die Standardimplementierung ist ein "Wörterbuchverfahren" mit einem Wörterbuch von bis zu 4096 möglichen Einträgen und einer festen Codelänge von 12 bit. Das Wörterbuch wird wie bei allen LZ-Verfahren während des Kompressions- bzw. Dekompressionsvorgangs aufgebaut. Eine Ausnahme bilden die ersten 256 Einträge, die von vornherein mit den Abbildungen der einzelnen Bytes vorbelegt sind. Zur Laufzeit werden aus den Eingabedaten Muster gewonnen, die, sofern sie noch nicht bekannt sind, ins Wörterbuch eingetragen werden. Im anderen Fall wird nicht das Muster sondern sein Index im Wörterbuch ausgegeben.
Doch hier zunächst ein Beispiel:
Kodierung:
Eingabe Erkanntes Muster Neuer Wörterbucheintrag
------- ---------------- -----------------------
LZWLZ78LZ77LZCLZMWLZAP L LZ (=256)
ZWLZ78LZ77LZCLZMWLZAP Z ZW (=257)
WLZ78LZ77LZCLZMWLZAP W WL (=258)
LZ78LZ77LZCLZMWLZAP LZ LZ7 (=259)
78LZ77LZCLZMWLZAP 7 78 (=260)
8LZ77LZCLZMWLZAP 8 8L (=261)
LZ77LZCLZMWLZAP LZ7 LZ77 (=262)
7LZCLZMWLZAP 7 7L (=263)
LZCLZMWLZAP LZ LZC (=264)
CLZMWLZAP C CL (=265)
LZMWLZAP LZ LZM (=266)
MWLZAP M MW (=267)
WLZAP WL WLZ (=268)
ZAP Z ZA (=269)
AP A AP (=270)
P P
Ausgabe: L Z W <256> 78 <259> 7 <256> C <256> M <258> Z A P
Erklärung:
Jede Zeile im oberen Beispiel zeigt jeweils den Inhalt des Eingabestrings in jedem Schritt der Kodierung, das in diesem Schritt längste im Wörterbuch gefundene Zeichenmuster und neu hinzugekommene Wörterbucheinträge mit ihren Indexnummern.
Im ersten Schritt wird das längste gefundene Muster zwangsläufig nur ein einziger Buchstabe sein, da beim LZW-Verfahren das Wörterbuch mit allen Einzelzeichen mit den Codewerten von 0 bis 255 vorbelegt ist, aber keine längeren Zeichenketten enthält. In unserem Beispiel findet der Algorithmus also das 'L'. Im gleichen Schritt wird noch ein weiteres Zeichen der Eingabe betrachtet ('Z') und an das 'L' angehängt. Die so erzeugte Zeichenkette ist garantiert noch nicht im Wörterbuch enthalten, wird also unter dem Index 256 neu eingetragen. Im nächsten Schritt wird vom Eingabestrom die im letzen Schritt längste gefundene Zeichenkette (also das 'L') entfernt und ausgegeben. Das 'Z' wird nun zum ersten Zeichen des neuen Eingabestrings. Hier beginnt das gleiche Spiel von vorne. 'Z' ist das längste bekannte Muster. 'ZW' wird unter dem Index 257 ins Wörterbuch aufgenommen. 'Z' wird von der Eingabe entfernt, ausgegeben und ein neuer Durchlauf begonnen. 'W' ist nun längste im Wörterbuch eingetragene Zeichenkette, 'WL' wird mit Indexnummer 258 neu aufgenommen und das 'W' aus der Eingabe gestrichen und zur Ausgabe umgeleitet. Im nächsten Schritt passiert endlich etwas interessanteres; das längste bekannte Muster ist nun eine Zeichenfolge, die wir selbst ins Wörterbuch eingetragen haben ('LZ' mit Indexnummer 256). Jetzt werden im nachfolgenden Schritt nicht zwei Einzelzeichen ausgegeben, sondern der Index des Musters aus dem Wörterbuch (256).
Dekodierung:
Eingabezeichen C Neuer Wörterbucheintrag p
-------------- - ----------------------- -
L L
Z Z LZ (=256) Z
W W ZW (=257) W
<256> L WL (=258) LZ
7 7 LZ7 (=259) 7
8 8 78 (=260) 8
<259> L 8L (=261) LZ7
7 7 LZ77 (=262) 7
<256> L 7L (=263) LZ
C C LZC (=264) C
<256> L CL (=265) LZ
M M LZM (=266) M
<258> W MW (=267) WL
Z Z WLZ (=268) Z
A A ZA (=269) A
P P AP (=270) P
Ausgabestring: L Z W LZ 7 8 LZ7 7 LZ C LZ M WL W A P
Erklärung:
Bei der Dekodierung fangen wir ebenfalls mit einem schon vorinitialisierten Wörterbuch an. Wieder sind Einträge von 0 bis 255 vorhanden. In unserem Beispiel ist 'L' die längste bekannte Zeichenkette. Sie wird deshalb auch ausgegeben und in der Variablen P (wie "Präfix") festgehalten. Die nächste Eingabe ist ebenfalls ein bekanntes Zeichen. Dieses wird zunächst in der Variablen C gespeichert. Nachfolgend wird P mit C konkateniert und das Ergebnis ins Wörterbuch unter der Indexnummer 256 aufgenommen. Man beachte, daß 'LZ' sowohl im Dekompressor als auch im Kompressor an der gleichen Stelle im Wörterbuch vorkommt (256). Nachfolgend wird die letzte Eingabe in die Variable P kopiert und P ausgegeben. Der nachfolgende Schritt (mit 'W') funktioniert genauso. Im nächsten Schritt wird nur das erste Zeichen des Wörterbucheintrags nach C übernommen ('L'). Dann wird wieder P und C konkateniert und ein neuer Wörterbucheintrag erzeugt ('WL' mit Index 258). Jetzt wird P der Index 256 zugewiesen und der dazugehörige Wörterbucheintrag ausgegeben.
Problemfall K[omega]K
Bei dieser Eingabekombination kann es bei der Implementierung des Dekoders Probleme geben. Hierbei ist K ein beliebiges Zeichen, gefolgt von einer Zeichenkette [omega], wiederum gefolgt von K. Entscheidend ist hierbei, daß sich K[omega] bereits im Wörterbuch befindet. Die Kodierung selbst bereitet keine Probleme; diese ergeben sich erst im Dekoder. In diesem Fall hinkt sozusagen der Dekoder dem Enkoder hinterher. Der Enkoder schickt hier den Code für seinen letzten Wörterbucheintrag. Dieser Eintrag ist dem Dekoder jedoch zu dieser Zeit noch unbekannt.
Beispiel:
APAPAPAPAP
Kodierung:
Eingabe Erkanntes Muster Neuer Wörterbucheintrag ------- ---------------- -----------------------Ausgabe: A P <256> <258> <257> <260>APAPAPAPAPAP A AP (=256) PAPAPAPAPAP P PA (=257) APAPAPAPAP AP APA (=258) APAPAPAP APA APAP (=259) PAPAP PA PAP (=260) PAP PAP
Dekodierung:
Eingabezeichen C Neuer Wörterbucheintrag p
-------------- - ----------------------- -
A A
P P AP (=256) P
<256> A PA (=257) AP
<258> ???
Trick: K[omega]K Fall ist aufgetreten, C ist erstes Zeichen der letzten
Ausgabe (also 'A')
A APA (=258) APA
<257> P APAP (=259) PA
<260> ???
gleiches Problem wie oben, d.h. C muß 'P' sein.
P PAP (=260) PAP
Ausgabe: A P AP APA PA PAPÜber viele Jahre hinweg war LZC - in seiner Implementierung als das bekannte "compress" - defakto der Standard bei Kompressionsprogrammen unter dem Betriebssystem Unix. LZC ist eigentlich nichts anderes als ein leicht abgewandelter LZW-Algorithmus. Der Unterschied besteht darin, daß das Wörterbuch und die Codelänge bei LZC keine feste Größe haben und bei Bedarf bis zu einer durch den Benutzer bestimmbaren Grenze wachsen können. Die Anfangscodelänge bei LZC beträgt 9-bit, was vor allem am Anfang sehr sinnvoll ist, da das Wörterbuch sowieso noch recht leer ist und somit auch keine großen Indizes benötigt. Genaugenommen ist LZC eigentlich nur die Implementierung einiger Vorschläge von Terry A. Welch in [LZW, Seite 18]. Man kann davon ausgehen, daß bei Verwendung variabler Codelänge (wie bei LZC) zumindest in einigen für die Praxis relevanten Fällen eine Verbesserung des Kompressionsverhältnisses von ca. 7% gegenüber LZW mit fester Codelänge erreicht wird [LZW, Seite 18].
Darüber hinaus unterscheidet sich die Wörterbuchverwaltung bei beiden Verfahren. Ist bei LZW das Wörterbuch einmal gefüllt, muß der Algorithmus mit den vorhandenen 4096 Einträgen auskommen und hat nicht einmal die Chance, veraltete Muster durch aktuellere zu ersetzen. Bei LZC wird hingegen die "Leistungsfähigkeit" des Wörterbuchs laufend überprüft. Bei Bedarf wird dann der gesamte Inhalt weggeworfen und von Anfang an neu aufgebaut [COMP.FAQ]. Durch diese Vorgehensweise ist gewährleistet, daß die Ortsredundanz (siehe 1.1.4) ausgenutzt wird, oder sich zumindest bezüglich der Kompressionsraten nicht allzu störend bemerkbar macht.
Ein Nachteil des LZW- (und auch des LZC-) Verfahrens ist die doch recht langsame Anpassung an die Eingabebeschaffenheit. In jedem Schritt kann ein Wörterbucheintrag um höchstens ein Zeichen wachsen. Es mag auf den ersten Blick vielleicht nicht unbedingt einleuchten, warum das ein Nachteil sein sollte. Bei längeren Sequenzen merkt man aber, daß noch günstigere Ergebnisse erzielbar wären, könnte die Anpassung von LZW an die Eingabedaten schneller erfolgen. Dazu betrachtet man das folgende Beispiel. Es sei ein String mit einer Million aufeinanderfolgender gleicher Zeichen gegeben (also z.B. aa..a). Dieser String soll mit Hilfe des LZW-Verfahrens kodiert werden. Am Schluß erreicht man ein Kompressionsverhältnis von etwa 1000:1. In diesem Fall erreicht die Länge der längsten Zeichenkette im Wörterbuch etwa 1400 Zeichen. Man mache es sich klar, daß das Kompressionsverhältnis noch weiter gesteigert werden könnte, wenn im Laufe des Kompressionsvorgangs frühzeitig längere Wörterbucheinträge zur Verfügung hätte. [YABBA]
Genau in diesem Punkt setzt das LZMW-Verfahren an. Anstatt nur jeweils ein Zeichen an eine Zeichenkette im Wörterbuch anzuhängen, verbinden wir jede Zeichenkette mit dem längsten bekannten String, den wir in der nachfolgenden Eingabe unmittelbar im Anschluß finden können. [YABBA]
Beispiel:
aaaaaaaaaaaaaa..a
Eingabe Erkanntes Muster Neuer Wörterbucheintrag ------- ---------------- -----------------------Man merkt wie schnell jetzt die Länge der Wörterbucheinträge zunimmt. Im fünften Schritt haben wir bereits eine Stringlänge von 16 Zeichen erreicht; bei LZW wären es in diesem Fall gerade mal 6. Im nächsten Schritt könnte man den Unterschied noch deutlicher sehen.aaaaaaaaaaaaaaaaaa..a a aaaaaaaaaaaaaaaaa..a a aa aaaaaaaaaaaaaaaa..a aa aaaa aaaaaaaaaaaaaa..a aaaa aaaaaaaa aaaaaaaaaa..a aaaaaaaa aaaaaaaaaaaaaaaa aa..a usw. usw.
In unserem Beispiel mit einer Million a's zeigt LZMW seine Stärke. Als Ergebnis bekommt man eine kodierte Zeichenkette von nur 30 Bytes. [YABBA]
Was ein Nachteil ist, kann anderswo aber auch ein Vorteil sein. Obwohl LZW bei langen Mustern versagt, kommt es mit kurzen Mustern viel besser zurecht als LZMW. Deshalb sind i.A. die Kompressionsraten von LZW in der Praxis nur unwesentlich schlechter als bei LZMW.
Außerdem hat LZMW noch eine ungünstige Eigenschaft: im Gegensatz zu LZW befinden sich im Wörterbuch nicht alle Präfixe der eingetragenen Strings. Das macht die Wörterbuchverwaltung komplizierter und langsamer. Ein anderes Problem ist, daß bei LZMW eine Zeichenkette eventuell doppelt ins Wörterbuch aufgenommen werden kann. [YABBA]
Zusammenfassend läßt sich sagen, daß LZMW große Vorteile bei Einzelzeichenwiederholung (siehe 1.1.2) gegenüber von LZW aufweist und bei fehlen dieser Redundanzart keine Verbesserung des Kompressionsverhältnisses mit sich bringt.
Eine Verbesserung des LZMW-Verfahrens in Bezug auf die Wörterbuchverwaltung ist LZAP. Hier werden nicht nur zwei Strings aneinandergehängt und ins Wörterbuch aufgenommen. Alle Präfixe der zusammengesetzten Zeichenkette werden ebenfalls ins Wörterbuch eingetragen. Damit bietet das Wörterbuch mehr Zeichenketten, auf die im Laufe der Kodierung zugegriffen werden kann. In der Praxis erreicht man mit LZAP bessere Ergebnisse als bei LZMW sowohl in Bezug auf die Kompressionsraten als auch bei der Geschwindigkeit. [YABBA]
3.
Praxistest diverser LZ Packer
In der nachfolgenden Tabelle findet man Ergebnisse aus praktischer Anwendung des LZC-Verfahrens mit verschiedenen Obergrenzen für die maximal zulässige Codelänge. In der letzten Spalte ist außerdem noch das Ergebnis des LHA-Packers als Vertreter der LZ77-Familie angegeben.
Für den Test wurden folgende Dateien benutzt:
c.txt: enthält nichts als 10000000 c's
zufall.dat: Datei mit 10000000 Zufallszahlen
News.txt: zufällig herausgesuchte Artikel aus
der USENET-Newsgroup comp.sys.atari.8bit (mit Header)
man.txt: Manpage des Unix-Befehls 'man'
win95c.jpg: Ein mit dem JPEG-Verfahren komprimiertes Bild
Tabelle
| Original | LZC | LZC | LZC | LZC | LHA (LZ77) | LZ77 |
| | 9bit | 10bit | 12bit | 16bit | mit | Blocksize |
| | | | | | Huffman | 16384 |
-------------------------------------------------------------------------------------------
c.txt | 10000000 | 52394 | 20718 | 8497 | 6438 | 1063 | 1809702 |
zufall.dat | 10000000 | 12415903 | 12280228 | 13788348 | 12608793 | 9853421 | 11181051 |
News.txt | 35552 | 35038 | 26067 | 21908 | 19533 | 13576 | 20233 |
man.txt | 24750 | 18742 | 12683 | 8752 | 8533 | 5237 | 9310 |
win95c.jpg | 41940 | 51934 | 51406 | 58037 | 58917 | 41997 | 46785 |
--------------------------------------------------------------------------------------------
Alle Dateilängen sind in Bytes angegeben.Die LZ-Familie ist seit ihrem Anfang stetig gewachsen. Ständig werden auf ihrer Basis neue Verfahren entwickelt. Einige von Ihnen streben eine Spezialisierung auf ganz bestimmte Redundanzarten an (z.B. LZMW); andere versuchen so weit wie möglich für beliebige Eingabedaten annehmbare Ergebnisse zu liefern (z.B. LZW). Eine bemerkenswerte Eigenschaft aller EZ-Verfahren ist die Tatsache, daß sie (bis auf wenige Ausnahmen) über die Eingabedaten nichts im Voraus wissen müssen und trotzdem im Laufe des Kodier- und Dekodiervorgangs viel "Wissen" über die A Eigenschaften der Daten ansammeln und dieses "Wissen" auch gewinnbringend gebrauchen können.
Die Leistung der beschriebenen Verfahren ist zwar nicht in jedem Fall optimal; ihre Struktur läßt ihnen aber in der Praxis viele Anwendungsgebiete offen. Auch in Zukunft ist noch mit weiteren Verbesserungen dieser Verfahren zu rechnen.
Kay_94 David C. Kay, John R. Levine: "Graphics File Formats", 2-te Ausgabe,
Windcrest/McGraw-Hill 1994
S. 25-26
LZW Terry A. Welch: "A Technique for High Performance Data Compression",
IEEE Computer vol. 17 no. 6, Juni 1984
S. 8-19
LZ77 J. Ziv, A. Lempel: "A Universal Algorithm for Sequential Data
Compression", IEEE Transactions
S. 337-343
LZ78 J. Ziv, A. Lempel: "Compression of Individual Sequences Via
Variable-Rate Coding", IEEE Transactions on I
S. 530-536
COMP.FAQ "Frequently Asked Questions" aus der Newsgroup comp.compression
YABBA Daniel J. Bernstein, "Y Coding", Draft 4b, March 19, 1991 from the
Yabba compression package.