Difference between revisions of "LZSS"
From Sega Retro
Scarred Sun (talk | contribs) m (3 revisions) |
|||
| (5 intermediate revisions by 3 users not shown) | |||
| Line 1: | Line 1: | ||
| − | '''LZSS''' is lossless data compression algorithm and a derivate of [[LZ77]]. Many compression programs like ARJ or PKZIP use LZSS as its main algorithm. | + | '''LZSS'''{{fileref|Data Compression The Complete Reference Book.pdf|page=204}} (''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 | + | 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. | 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. | ||
| Line 11: | Line 11: | ||
== External links == | == External links == | ||
| + | * [http://www.compression-links.info/LZSS List of LZSS resources, libraries and source codes] | ||
| + | |||
| + | ==References== | ||
| + | <references/> | ||
| − | |||
| − | [[Category:Data | + | [[Category:Data compression]] |
Latest revision as of 06:05, 14 November 2017
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.