LZSS (Lempel, Ziv, Storer, Szymanski)

Das LZSS-Verfahren (Lempel, Ziv, Storer, Szymanski) ist eine verlustfreie Kompression für Zeichenfolgen in einem Textdokument. Bei diesem Verfahren werden sich wiederholende Zeichenfolgen erkannt, und zwar unabhängig von deren Länge. Die gespeicherten Zeichenfolgen werden mit den Texten des Textdokuments verglichen. Wird keine Zeichenfolge erkannt, dann wird der entsprechende Buchstabe als einzelnes Byte gespeichert. Dem Verfahren nach wird ein variables Fenster aus Buchstabenkombinationen über den Text geschoben.


Ein Beispiel für eine Codierung macht die Verfahrensweise verständlich. Das Wort "Sendesensorik" wird nach diesem Verfahren folgendermaßen codiert: Von dem Wort Sendesensorik wird, da noch kein Byte ausgegeben wurde, zuerst das "S" ausgegeben. Die Überprüfung hinsichtlich des Buchstaben "S" ergibt zwar einen Treffer, es ist allerdings wenig sinnvoll einen Treffer von einem einzelnen Buchstaben zu als Wiederholung zu registrieren. Es folgt also das "e", das in Verbundung mit dem gespeicherten "S" zu " Se" wird und in dieser Kombination ein weiteres mal auftritt. Wird der dritte Buchstabe, das "n", an das "Se" angefügt, ergibt sich für das "Sen" eine Wiederholung. Diese drei Bytes der Wiederholung werden in einem Wertepaar ausgegeben und stellen die Kompression dar.

Die Vorteile des LZSS-Verfahrens sind bei längeren Textpassagen besser zu erkennen.

Informationen zum Artikel
Deutsch: LZSS-Verfahren
Englisch: Lempel, Ziv, Storer, Szymanski - LZSS
Veröffentlicht: 31.03.2008
Wörter: 200
Tags: #Textkompression
Links: Byte, Codierung, iteration, LZ (Lempel, Ziv), Se (selenium)