Datenkompression


Kriterien

Übersicht Formate

Grundlagen

Kompressionsverfahren

Shannon-Fano

Huffman

Lempel-Ziv (LZ)

LZ77

LZSS

LZ78

LZW

arithmetische Kodierung

Run Length Encoding

Burrows-Wheeler (BWT)

Implementationen

Datenformate


Glossar

Stichwortverzeichnis


Download


www.BinaryEssence.de

Lempel-Ziv-77 (LZ77)


Entwicklung:


Jacob Ziv und Abraham Lempel haben 1977 in der Publikation "A Universal Algorithm for Sequential Data Compression" ein einfaches, aber effizientes Verfahren zur Kompression von beliebigen Inhalten vorgestellt. Nach seinen Erfindern und dem Veröffentlichungsdatum ist dieser Algorithmus unter dem Kürzel LZ77 bekannt.


Prinzip:


LZ77 ist ein wörterbuchbasiertes Verfahren, dass anstelle der Originaldaten, Rückgriffe auf Sequenzen aus dem bisherigen Inhalt kodiert. Im Prinzip existiert nur eine einfache Kodierungsvorschrift. Alle Daten werden in der Form


  • Adresse der bereits enthaltenen Sequenz,
  • deren Sequenzlänge und
  • das erstes abweichende Zeichen

kodiert. Sind die zu kodierenden Daten noch nicht in den vorangegangenen Daten enthalten, tritt also ein neues Zeichen auf, so wird die Adresse 0, die Sequenzlänge 0 und das betroffene Zeichen kodiert.


Beispiel "abrakadabra":


               Adr.  Länge  abw. Zeichen
 abrakadabra    0      0      'a'
a brakadabra    0      0      'b'
ab rakadabra    0      0      'r'
abr akadabra    3      1      'k'
abrak adabra    2      1      'd'	
abrakad abra    7      4      ''

Bedingt durch die Ergänzung jeder Sequenz mit dem ersten abweichenden Zeichen erhöht sich der Werteumfang der kodierbaren Zeichen, ohne von dem standardisierten Format abzuweichen. Das ermöglicht eine einfache Umsetzung des Algorithmus mit minimalen Anforderungen an die Resourcen von Enkoder und Dekoder.


Rahmenbedingungen:


Damit Rechenzeit und Speicherbedarf für Enkoder und Dekoder in einem überschaubaren Rahmen gehalten werden können, ist die Adresse durch einen Maximalwert begrenzt. Über diesen Bereich hinausgehende Übereinstimmungen fließen nicht in die Kodierung ein und finden bei der Dimensionierung der Adressgrößen keine Berücksichtigung.


Kodierungseffizienz:


Die erzielbare Kompressionsrate ist ausschließlich von sich wiederholenden Sequenzen gleichen Inhalts abhängig. Redundanz, die aus der unterschiedlicher Wahrscheinlichkeit für das Auftreten einzelnen Zeichen resultiert, läßt sich mit LZ77 nicht reduzieren. Deshalb ist die Leistungsfähigkeit von LZ77 für sich alleine betrachtet als gering einzuschätzen.


Signifikant bessere Kompressionsraten lassen sich durch die Kombination von LZ77 mit zusätzlicher Entropiekodierung erreichen. Dafür bietet sich beispielsweise die Huffman-Kodierung an. Dieser Weg wird bei dem weit verbreiteten Deflate-Verfahren beschritten (u.a. in GZIP oder ZIP).


 <   ^   > 

Deflate [Deflate]

Deflate64™ [Deflate64™]

Huffman-Kodierung [Huffman-Kodierung]

GZIP [GZIP]

ZIP [ZIP]

Lempel-Ziv-Kodierung (LZ) Lempel-Ziv-Kodierung (LZ) Lempel-Ziv-Storer-Szymanski (LZSS)



Anzeigen:

Informations- und Kodierungstheorie