Difference between revisions of "LZ77"
From Sega Retro
old>Hivebrain m |
|||
| (7 intermediate revisions by 4 users not shown) | |||
| Line 1: | Line 1: | ||
| − | '''LZ77''' and '''LZ78''' are the names for the two lossless data compression algorithms published in papers by Abraham Lempel and Jacob Ziv in 1977 and 1978. These two algorithms form the basis for most of the LZ variations including [[LZW]], [[LZSS]] and others. | + | '''LZ77'''{{fileref|Data Compression The Complete Reference Book.pdf|page=201}} and '''LZ78'''{{fileref|Data Compression The Complete Reference Book.pdf|page=214}} (''Lempel-Ziv compression'') initially called '''LZ1''' and '''LZ2''', respectively, are the names for the two lossless data compression algorithms published in papers by Abraham Lempel and Jacob Ziv in 1977 and 1978. These two algorithms form the basis for most of the LZ variations including [[LZW]], [[LZSS]] and others. |
They are both dictionary coders, unlike minimum redundancy coders or run length coders. LZ77 is the "sliding window" compression algorithm, which was later shown to be equivalent to the explicit dictionary technique first given in LZ78. | They are both dictionary coders, unlike minimum redundancy coders or run length coders. LZ77 is the "sliding window" compression algorithm, which was later shown to be equivalent to the explicit dictionary technique first given in LZ78. | ||
The LZ77 algorithm works by keeping a history window of the most recently seen data and comparing the current data being encoded with the data in the history window. | The LZ77 algorithm works by keeping a history window of the most recently seen data and comparing the current data being encoded with the data in the history window. | ||
What is actually placed into the compressed stream are references to the position in the history window, and the length of the match. If a match cannot be found the character itself is simply encoded into the stream after being flagged as a literal. | What is actually placed into the compressed stream are references to the position in the history window, and the length of the match. If a match cannot be found the character itself is simply encoded into the stream after being flagged as a literal. | ||
| − | As of 2004, the most popular LZ77 based compression method is called DEFLATE; it combines LZ77 with Huffman | + | As of 2004, the most popular LZ77 based compression method is called DEFLATE; it combines LZ77 with [[Huffman Coding]]. |
==References== | ==References== | ||
| Line 14: | Line 14: | ||
* [http://www.compression-links.info/LZSS List of LZ77 algorithm (and its derivatives) libraries, papers and sources] | * [http://www.compression-links.info/LZSS List of LZ77 algorithm (and its derivatives) libraries, papers and sources] | ||
| − | [[Category:Data | + | [[Category:Data compression]] |
Latest revision as of 06:07, 14 November 2017
LZ77[1] and LZ78[2] (Lempel-Ziv compression) initially called LZ1 and LZ2, respectively, are the names for the two lossless data compression algorithms published in papers by Abraham Lempel and Jacob Ziv in 1977 and 1978. These two algorithms form the basis for most of the LZ variations including LZW, LZSS and others. They are both dictionary coders, unlike minimum redundancy coders or run length coders. LZ77 is the "sliding window" compression algorithm, which was later shown to be equivalent to the explicit dictionary technique first given in LZ78.
The LZ77 algorithm works by keeping a history window of the most recently seen data and comparing the current data being encoded with the data in the history window. What is actually placed into the compressed stream are references to the position in the history window, and the length of the match. If a match cannot be found the character itself is simply encoded into the stream after being flagged as a literal. As of 2004, the most popular LZ77 based compression method is called DEFLATE; it combines LZ77 with Huffman Coding.
References
- Abraham Lempel, Jacob Ziv; A Universal Algorithm for Sequential Data Compression, IEEE Transactions on Information Theory, May 1977.
- Abraham Lempel, Jacob Ziv; Compression of Individual Sequences Via Variable-Rate Coding, IEEE Transactions on Information Theory, September 1978.