| [ << ] | [ < ] | [ Up ] | [ > ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
2 Algorithm
Lzip implements a simplified version of the LZMA (Lempel-Ziv-Markov chain-Algorithm) algorithm. The high compression of LZMA comes from combining two basic, well-proven compression ideas: sliding dictionaries (LZ77/78) and markov models (the thing used by every compression algorithm that uses a range encoder or similar order-0 entropy coder as its last stage) with segregation of contexts according to what the bits are used for.
Lzip is a two stage compressor. The first stage is a Lempel-Ziv coder, which reduces redundancy by translating chunks of data to their corresponding distance-length pairs. The second stage is a range encoder that uses a different probability model for each type of data; distances, lengths, literal bytes, etc.
The match finder, part of the LZ coder, is the most important piece of the LZMA algorithm, as it is in many Lempel-Ziv based algorithms. Most of lzip’s execution time is spent in the match finder, and it has the greatest influence on the compression ratio.
Here is how it works, step by step:
1) The member header is written to the output stream.
2) The first byte is coded literally, because there are no previous bytes to which the match finder can refer to.
3) The main encoder advances to the next byte in the input data and calls the match finder.
4) The match finder fills an array with the minimum distances before the current byte where a match of a given length can be found.
5) Go back to step 3 until a sequence (formed of pairs, repeated distances and literal bytes) of minimum price has been formed. Where the price represents the number of output bits produced.
6) The range encoder encodes the sequence produced by the main encoder and sends the produced bytes to the output stream.
7) Go back to step 3 until the input data is finished or until the member or volume size limits are reached.
8) The range encoder is flushed.
9) The member trailer is written to the output stream.
10) If there are more data to compress, go back to step 1.
The ideas embodied in lzip are due to (at least) the following people: Abraham Lempel and Jacob Ziv (for the LZ algorithm), Andrey Markov (for the definition of Markov chains), G.N.N. Martin (for the definition of range encoding), Igor Pavlov (for putting all the above together in LZMA), and Julian Seward (for bzip2’s CLI).
| [ << ] | [ < ] | [ Up ] | [ > ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
This document was generated on October 10, 2013 using texi2html 5.0.