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-78 (LZ78)


Ein Jahr nach der Veröffentlichung von LZ77 haben Jacob Ziv und Abraham Lempel ein weiteres Kodierungsverfahren vorgestellt ("Compression of Individual Sequences via Variable-Rate Coding"). Dementsprechend bezeichnet man das Verfahren als LZ78.


Prinzip:


Basis für LZ78 ist ein explizit geführtes Wörterbuch, das zur Laufzeit, sowohl während der Enkodierung als auch während der Dekodierung, aufgebaut wird. In dieses Wörterbuch werden alle bereits kodierten Zeichenketten eingetragen. Kodiert wird der Inhalt in der Form:


  • Index auf den Eintrag im Wörterbuch
  • erstes abweichendes Zeichen

Im Gegensatz zu LZ77 wird hier keine Kombination aus Adresse und Länge der Zeichenkette, sondern lediglich der Index auf eine Tabelle gespeichert. Die Architektur mit dem ersten Zeichen, für das keine Übereinstimmung im Wörterbuch gefunden wurde, bleibt erhalten.


Beispiel "abrakadabra":


                   abweichendes  neuer Eintrag
              Index  Zeichen      Wörterbuch
 abrakadabra    0      'a'        1  "a"
a brakadabra    0      'b'        2  "b"
ab rakadabra    0      'r'        3  "r"
abr akadabra    1      'k'        4  "ak"
abrak adabra    1      'd'        5  "ad"
abrakad abra    1      'b'        6  "ab"
abrakadab ra    3      'a'        7  "ra"

Der Aufbau des Wörterbuchs vollzieht sich verhältnismäßig langsam, relevante Kompressionsleistungen werden erst bei größeren Datenmengen erreicht. Daüber hinaus ist die Kompressionsleistung unmittelbar von der Größe des Wörterbuchs abhängig. Allerdings steigt damit der Aufwand für die Administration, die zur Laufzeit ausgeführt werden muss.


Für die praktische Implementation wird das Wörterbuch in einer Baumstruktur ausgeführt, um den Aufwand für das Durchsuchen der Einträge zu minimieren. Beginnend mit dem aktuellen Zeichen durchläuft der Algorithmus den Baum bis zum Erreichen eines Endknotens. Der Index, der dem betroffenen Knoten zugeordnet ist, wird dann ausgegeben. Weil dekoderseitig keine Suchfunktion erforderlich ist, läßt sich der Dekoder mit einer indizierten Tabelle realisieren.


Im Zuge der Kodierung wächst das Wörterbuch immer weiter an, so dass die Adresslänge für die Indizierung, der Speicherplatz- und der Laufzeitbedarf permanent zunimmt. Deshalb muss eine Begrenzung des Wörterbuch erfolgen. Ist dieses gefüllt, so sind Mechanismen zur Aktualisierung erforderlich.


Auf LZ78 setzen verschiedene Verfahren auf, u.a. auch das weit verbreitete LZW-Verfahren, dass z.B. im Rahmen von GIF eingesetzt wird.


 <   ^   > 

GIF: Datenkompression []

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



Anzeigen:

Informations- und Kodierungstheorie