Lempel–Ziv–Storer–Szymanski - Lempel–Ziv–Storer–Szymanski

Ziv-Lempel-Storer-Szymanski ( LZSS ) ist eine verlustfreie Datenkomprimierungsalgorithmus , ein Derivat von LZ77 , die im Jahr 1982 erstellt wurde James A. Storer und Thomas Szymanski . LZSS wurde im Artikel "Data Compression via textual substituiert" beschrieben, der im Journal of the ACM (1982, S. 928–951) veröffentlicht wurde.

LZSS ist eine Wörterbuchcodierungstechnik . Es versucht, eine Zeichenfolge durch einen Verweis auf eine Wörterbuchposition derselben Zeichenfolge zu ersetzen.

Der Hauptunterschied zwischen LZ77 und LZSS besteht darin, dass in LZ77 die Wörterbuchreferenz tatsächlich länger sein kann als die Zeichenfolge, die sie ersetzt. In LZSS werden solche Verweise weggelassen, wenn die Länge kleiner als der "Break-Even"-Punkt ist. Darüber hinaus verwendet LZSS Ein-Bit-Flags, um anzuzeigen, ob der nächste Datenblock ein Literal (Byte) oder eine Referenz auf ein Offset/Längen-Paar ist.

Beispiel

Hier ist der Anfang von Dr. Seuss's Green Eggs and Ham , mit Zeichennummern am Anfang der Zeilen zur Vereinfachung. Green Eggs and Ham ist ein gutes Beispiel zur Veranschaulichung der LZSS-Komprimierung, da das Buch selbst nur 50 eindeutige Wörter enthält, obwohl es eine Wortzahl von 170 hat. Daher werden Wörter wiederholt, jedoch nicht nacheinander. 

  0: I am Sam
  9:
 10: Sam I am
 19:
 20: That Sam-I-am!
 35: That Sam-I-am!
 50: I do not like
 64: that Sam-I-am!
 79: 
 80: Do you like green eggs and ham?
112:
113: I do not like them, Sam-I-am.
143: I do not like green eggs and ham.

Dieser Text nimmt in unkomprimierter Form 177 Bytes ein. Unter der Annahme eines Break-Even-Points von 2 Byte (und damit 2 Byte Zeiger/Offset-Paaren) und einem Byte Zeilenumbruch wird dieser mit LZSS komprimierte Text 94 Byte lang:

Ein farbcodiertes Beispiel zur Veranschaulichung des Recyclings wiederholter Informationen, um den Speicherbedarf zu minimieren.
Ein farbcodiertes Beispiel für die LZSS-Komprimierung in Aktion.
 0: I am Sam
 9:
10: (5,3) (0,4)
16:
17: That(4,4)-I-am!(19,16)I do not like
45: t(21,14)
49: Do you(58,5) green eggs and ham?
78: (49,14) them,(24,9).(112,15)(92,18).

Hinweis: Dies beinhaltet nicht die 12 Byte Flags, die angeben, ob der nächste Textabschnitt ein Zeiger oder ein Literal ist. Wenn man es hinzufügt, wird der Text 106 Byte lang, was immer noch kürzer ist als die ursprünglichen 177 Byte.

Implementierungen

Viele beliebte Archivierungsprogramme wie PKZip , ARJ , RAR , ZOO , LHarc verwenden LZSS anstelle von LZ77 als primären Komprimierungsalgorithmus; die Kodierung von Literalzeichen und von Längen-Abstands-Paaren variiert, wobei die gebräuchlichste Option die Huffman-Kodierung ist . Die meisten Implementierungen stammen aus einem gemeinfreien Code von 1989 von Haruhiko Okumura . Version 4 der Allegro-Bibliothek kann ein LZSS-Format codieren und decodieren, aber die Funktion wurde aus Version 5 gekürzt. Das Game Boy Advance- BIOS kann ein leicht modifiziertes LZSS-Format decodieren. Apples Mac OS X verwendet LZSS als eine der Komprimierungsmethoden für Kernel-Code.

Siehe auch

Verweise