LZSS

LZSS, short for Lempel-Ziv-Storer-Szymanski, is a lossless data compression algorithm that builds on the LZ77 framework. It improves on LZ77 by using a sliding window to locate repeated strings and by encoding the output as a sequence of literals and length-distance references, with a small flag to indicate the type of each token.

During compression, the encoder maintains a window of previously output data and a lookahead buffer of upcoming symbols. For each position, it searches the window for the longest match of the lookahead text. If the match length is at least a minimum threshold (often 3), the encoder emits a length-distance pair; otherwise it outputs the literal byte. A flag bit or flag byte precedes each token to indicate whether the following data is a literal or a reference. The decoder performs the inverse operation, outputting the literal or copying data from earlier output using the specified distance and length.

Typical configurations use a sliding window of several kilobytes and a lookahead buffer of about 12 to 18 bytes, with the maximum match length constrained by the lookahead size. The exact bit widths and token encodings vary across implementations, reflecting different design choices for speed and compression.

History and usage: LZSS was described by Storer and Szymanski in 1984 as a variant of LZ77. It has influenced a range of simple, fast compression schemes, particularly in embedded systems and software tools that prioritize speed and simplicity over achieving the highest possible compression ratio. It is distinct from related schemes such as LZW and Deflate.