Difference between revisions of "LZSS"
From Sega Retro
| Line 1: | Line 1: | ||
| − | '''LZSS''' (''Lempel–Ziv–Storer–Szymanski'') is lossless data compression algorithm and a derivate of [[LZ77]]. Many compression programs like ARJ or PKZIP use LZSS as its main algorithm. | + | '''LZSS''' (''Lempel–Ziv–Storer–Szymanski'') is a lossless data compression algorithm and a derivate of [[LZ77]]. 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. | ||
Revision as of 03:11, 22 September 2017
LZSS (Lempel–Ziv–Storer–Szymanski) is a lossless data compression algorithm and a derivate of LZ77. 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.