LZSS

From Sega Retro

LZSS[1] (Lempel–Ziv–Storer–Szymanski) is a lossless data compression algorithm and a derivate of LZ77 developed by James Andrew Storer and Thomas G. Szymanski in 1982. Many compression programs like ARJ or PKZIP use LZSS as its main algorithm.

LZSS is a dictionary encoding technique. Unlike Huffman Coding, which attempts to reduce the average amount of bits required to represent a symbol, LZSS attempts to replace a string of symbols with a reference to a dictionary location of the same string. It is intended that the dictionary reference should be shorter than the string it replaces. In the case of LZ77, the predecessor to LZSS, that isn't always the case.

The main difference is in the output with LZ77 is that LZ77 always outputs an offset/length pair, even if the match is only one byte (this cases uses more than 8 bits to represent a byte) so LZSS uses another trick to improve it - it uses bit flags that are just one bit that tells what the next data is: a literal (a byte) or a pair of offset/length.

See also

External links

References