Difference between revisions of "LZ77"
(New page: '''LZ77''' is a wikipedia:lossless data compression technique described by Lempel and Ziv in a 1977 article in ''IEEE Transactions on Information Theory''. It...)
Revision as of 14:17, 6 December 2009
LZ77 is a lossless data compression technique described by Lempel and Ziv in a 1977 article in IEEE Transactions on Information Theory. It acts as a generalization of run-length encoding, which keeps track of one previous byte and allows the data stream to repeat that byte for a "run" of N times. LZ77 keeps track of a history of 256 or more bytes, and a "run" copies N bytes starting from any point D in the history buffer relative to the current position. This allows an RLE-style run (e.g. D = -1, N = 10), but it also allows repeating a sequence of bytes (e.g. D = -5, N = 10) or repeating a previously seen string from the history buffer (e.g. D = -35, N = 5). A lot of games especially on the Super NES and Game Boy Advance used codecs based on LZ77, and the DEFLATE codec used in .zip and .png formats uses LZ77 combined with Huffman coding of D, N, and byte values.
(Here, I use "byte" to refer to code units. These can be larger than 1 byte in some cases, such as compression of high- or true-color images.)