Lempel-Ziv-Storer-Szymanski

Lempel-Ziv-Storer-Szymanski

Lempel-Ziv-Storer-Szymanski (LZSS) is a lossless data compression algorithm, a derivative of LZ77, that was created in 1982 by James Storer and Thomas Szymanski. LZSS was described in article "Data compression via textual substitution" published in "Journal of the ACM" (pp. 928-951).

LZSS is a dictionary encoding technique. It attempts to replace a string of symbols with a reference to a dictionary location of the same string.

The main difference between LZ77 and LZSS is that in LZ77 the dictionary reference could actually be longer than the string it was replacing. In LZSS, such references are omitted if the length is less than the "break even" point. Furthermore, LZSS uses one-bit flags to indicate whether the next chunk of data is a literal (byte) or a reference to an offset/length pair.

Example

Here is the beginning of Dr. Seuss's Green eggs and ham, with character numbers at the beginning of lines for convenience.

0: I am Sam9:10: Sam I am19:20: That Sam-I-am!35: That Sam-I-am!50: I do not like64: 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.

This text takes 177 bytes in uncompressed form. Assuming a break even point of 2 bytes (and thus 2 byte pointer/offset pairs), and one byte newlines, this text compressed with LZSS becomes 96 bytes long:

0: I am Sam9:10: (6,3) (0,4)16:17: That(5,4)-I-am!30: (20,15)I do not like46: t(21,14)49: Do you(58,5) green eggs and ham?79: (49,14) them,(24,9).(49,14)(93,18).

Note: this does not include a few bytes (3-4) of flags indicating whether the next chunk of text is a pointer or a literal. Adding it, the text becomes just over 100 bytes long, which is much shorter than the original 177 bytes.

Implementations

Many popular archivers like PKZip, ARJ, ZOO, LHarc use LZSS rather than LZ77 as primary compression algorithm; the encoding of literal characters and of length-distance pairs varies, with the most common option being Huffman coding. The Allegro library can encode and decode an LZSS format, [Hargreaves, Shawn, et al. [http://alleg.svn.sourceforge.net/viewvc/alleg/allegro/branches/4.2/src/lzss.c?revision=7522&view=markup Allegro source code: lzss.c, revision 7522] . Accessed on August 3, 2008.] and the Game Boy Advance BIOS can decode a slightly different LZSS format. [Korth, Martin. [http://nocash.emubase.de/gbatek.htm#biosdecompressionfunctions GBATEK: GBA BIOS Decompression Functions] . Accessed on August 3, 2008.]

References

See also

* LZ77
* Lempel-Ziv-Welch (LZW)

External links

* [http://babelfish.altavista.com/babelfish/trurl_pagecontent?lp=es_en&url=http%3A%2F%2Fes.wikipedia.org%2Fwiki%2FLZSS More information] translated from Spanish language Wikipedia


Wikimedia Foundation. 2010.

Игры ⚽ Нужна курсовая?

Look at other dictionaries:

  • Lempel-Ziv-Storer-Szymanski — Der Lempel Ziv Storer Szymanski Algorithmus (LZSS) ist ein Algorithmus zur verlustfreien Datenkompression auf Basis von LZ77. Er wurde 1982 von James A. Storer und Thomas G. Szymanski im Journal of the ACM veröffentlicht, einer Fachzeitschrift… …   Deutsch Wikipedia

  • Lempel-Ziv-Storer-Szymanski-Algorithmus — Der Lempel Ziv Storer Szymanski Algorithmus (LZSS) ist ein Algorithmus zur verlustfreien Datenkompression auf Basis von LZ77. Er wurde 1982 von James A. Storer und Thomas G. Szymanski im Journal of the ACM veröffentlicht, einer Fachzeitschrift… …   Deutsch Wikipedia

  • Lempel-Ziv-Welch — (LZW) is a universal lossless data compression algorithm created by Abraham Lempel, Jacob Ziv, and Terry Welch. It was published by Welch in 1984 as an improved implementation of the LZ78 algorithm published by Lempel and Ziv in 1978. The… …   Wikipedia

  • LZSS — Lempel Ziv Storer Szymanski (LZSS) est une méthode de compression de données sans perte créé en 1982 par James Storer et Thomas Szymanski. LZSS utilise une technique de codage à dictionnaire inspirée de LZ77. v · d · …   Wikipédia en Français

  • LZ 77 — LZ77 ist ein Verfahren zur Datenkompression, das 1977 von Abraham Lempel und Jacob Ziv veröffentlicht wurde. Die Autoren machten sich erstmals zu Nutze, dass ganze Wörter, oder zumindest Teile davon, in einem Text mehrfach vorkommen. Im Gegensatz …   Deutsch Wikipedia

  • Dateiarchivierung — Datenkompression oder Datenkomprimierung ist die Anwendung von Verfahren zur Reduktion des Speicherbedarfs von Daten bzw. zur Vermeidung von Datenaufkommen, bspw. während der Übertragung von Daten. Die Datenmenge wird reduziert, indem eine… …   Deutsch Wikipedia

  • Dateikompression — Datenkompression oder Datenkomprimierung ist die Anwendung von Verfahren zur Reduktion des Speicherbedarfs von Daten bzw. zur Vermeidung von Datenaufkommen, bspw. während der Übertragung von Daten. Die Datenmenge wird reduziert, indem eine… …   Deutsch Wikipedia

  • Datenkomprimierung — Datenkompression oder Datenkomprimierung ist die Anwendung von Verfahren zur Reduktion des Speicherbedarfs von Daten bzw. zur Vermeidung von Datenaufkommen, bspw. während der Übertragung von Daten. Die Datenmenge wird reduziert, indem eine… …   Deutsch Wikipedia

  • Datenreduktion — Datenkompression oder Datenkomprimierung ist die Anwendung von Verfahren zur Reduktion des Speicherbedarfs von Daten bzw. zur Vermeidung von Datenaufkommen, bspw. während der Übertragung von Daten. Die Datenmenge wird reduziert, indem eine… …   Deutsch Wikipedia

  • Datenreduktionsverfahren — Datenkompression oder Datenkomprimierung ist die Anwendung von Verfahren zur Reduktion des Speicherbedarfs von Daten bzw. zur Vermeidung von Datenaufkommen, bspw. während der Übertragung von Daten. Die Datenmenge wird reduziert, indem eine… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”