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-Storer-Szymanski (LZSS)


Das LZSS-Kodierungsverfahren ist nach den beiden Autoren James A. Storer und Thomas G. Szymanski, sowie dem LZ77-Verfahren benannt, auf dem LZSS aufsetzt. Veröffentlicht wurden theoretische und praktischen Überlegungen 1982 in dem Artikel "Data Compression via Textual Substitution".


LZSS kodiert die Quelldaten als String, bestehend aus den Originaldaten und Zeigern auf ein Wörterbuch. Das Wörterbuch bilden wie bei der LZ77-Kodierung die bereits kodierten Quelldaten, auf die in der Form [Adresse + Sequenzlänge] zugegriffen wird.


Beispiel:

   abrakadabra
   abrakad(1,4)

Als Zeiger werden nur Sequenzen kodiert, die eine bestimmte Minimallänge überschreiten, d.h. bei der die Substitution sinnvoll ist. Darin besteht der hauptsächliche Unterschied zu LZ77, bei dem immer in der Form (Adresse + Länge + abweichendes Zeichen) kodiert werden muss, auch wenn dies mit Hinblick auf die Kompressionsleistung nicht sinnvoll ist.


Zur Differenzierung zwischen Zeigern und Inhalten ist in der praktischen Umsetzung ein Flag oder Steuerzeichen erforderlich, dass seinerseits die Kompressionsleistung negativ beeinflusst.


In der Original-Publikation werden unterschiedliche Kodierungsschemata ausgeführt, die in der Realisierung variieren, vom Prinzip her aber auf den gleichen Grundlagen beruhen.


 <   ^   > 

Lempel-Ziv-Kodierung (LZ) Lempel-Ziv-77 (LZ77) Lempel-Ziv-78 (LZ78)



Anzeigen:

Informations- und Kodierungstheorie