The Mathematics Behind 7-Zip LZMA Compression

The high data density achieved by the Lempel-Ziv-Markov chain Algorithm (LZMA) in 7-Zip is fundamentally powered by the combination of an extended LZ77 sliding-window dictionary, adaptive Markov chain context modeling, and range coding. While dictionary matching handles macro-level redundancies across large blocks of data, the primary mathematical driver of LZMA’s exceptional density is its range coder, an implementation of arithmetic coding. By representing entire streams of data as a single fractional value within a narrowing probability interval, range coding allows LZMA to bypass the whole-bit constraints of traditional Huffman algorithms and compress data extremely close to its theoretical Shannon entropy limit.

Sliding Dictionary Matching (LZ77 Variant)

LZMA begins by finding repeated sequences using an optimized variant of the LZ77 algorithm. Instead of storing repeated data verbatim, it replaces occurrences with a distance-length pair indicating where the sequence previously appeared and how long it lasts. 7-Zip enhances this step mathematically by supporting dictionary sizes up to several gigabytes and employing fast hash-chain or binary-tree search algorithms to identify matches across vast distances. Once parsed, the input data is divided into streams of literal bytes, match lengths, and match distances.

Markov Chains and Context Modeling

Rather than encoding literal bytes and match references directly, LZMA models the statistical likelihood of each incoming bit using Markov chains. A discrete-time Markov chain is a stochastic model where the probability of a state depends only on the state attained in the previous step. In LZMA, the algorithm maintains an array of dynamic state machines that track probabilities based on context:

  • Positional Context: The algorithm tracks the position of the byte within a word or block, accounting for structured data like 32-bit or 64-bit binaries.
  • Recency Context: Probabilities shift based on recent events—whether the previous token was a literal byte, a match, or a repeated match distance.
  • Bit-Level Context: Literal bytes are decoded bit by bit, with the probability of the current bit conditioned on the value of the most recently decoded bits of the same byte.

As symbols pass through the compressor, these context states continuously update their internal probability tables, dynamically adjusting to localized shifts in data entropy.

Range Coding: Reaching the Entropy Limit

The mathematical core enabling LZMA's superior compression ratio is the range coder. According to Claude Shannon's source coding theorem, the optimal code length for a symbol with probability \(P\) is \(-\log_2(P)\) bits. Traditional entropy algorithms like Huffman coding round these values to integer numbers of bits, introducing unavoidable inefficiencies when symbol probabilities are high (for instance, if an event has a 90% probability, its optimal information content is roughly 0.15 bits, but Huffman must allocate at least 1 full bit).

Range coding eliminates this inefficiency by operating on intervals rather than discrete bit boundaries:

  1. Interval Definition: The entire encoded message is represented as a range of real numbers between 0 and 1, mathematically defined by a lower bound (\(Low\)) and a range width (\(Range\)).
  2. Subdivision: For each bit to be encoded, the current range is divided into sub-intervals proportional to the probabilities provided by the Markov context model (\(P_0\) and \(P_1\)).
  3. Narrowing: The coder selects the sub-interval corresponding to the actual symbol that occurred, setting that sub-interval as the new active range: \[\text{New Range} = \text{Current Range} \times P(\text{symbol})\] \[\text{New Low} = \text{Current Low} + \text{Offset}\]
  4. Renormalization: As the range contracts, leading digits of \(Low\) become fixed. These digits are shifted out and output as bytes, keeping the active calculations within fixed-precision integer registers without precision loss.

By multiplying probabilities sequentially, the final range width is equal to the product of the probabilities of all symbols in the sequence. Expressing a very small interval requires a number of bits directly proportional to \(-\sum \log_2(P(x))\), matching the theoretical entropy of the modeled source.

Through the synergy of long-range dictionary parsing, predictive Markov probability modeling, and fractional-bit range coding, LZMA minimizes wasted bit space and achieves the high compression density observed in 7-Zip archives.