LZMA

LZMA (Lempel–Ziv–Markov chain algorithm ) is a lossless data compression algorithm developed since 1998 by Igor Pavlov, the developer of 7-Zip.

Uses your system voice; voice and rate in settings.

Snapshot

≈ 6 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

LZMA (Lempel–Ziv–Markov chain algorithm ) is a lossless data compression algorithm developed since 1998 by Igor Pavlov, the developer of 7-Zip. It has been used in the 7z format of the 7-Zip archiver since 2001.

This algorithm uses a dictionary compression scheme somewhat similar to the LZ77 algorithm published by Abraham Lempel and Jacob Ziv in 19771 and features a high compression ratio (generally higher than bzip2) and a variable compression-dictionary size (up to 4 GB), while still maintaining decompression speed similar to other commonly used compression algorithms. LZMA2 is a simple container format that allows multi-threaded compression and decompression using multiple separate LZMA streams.

It is used in both in the 7z and the xz format.

LZMA (Lempel–Ziv–Markov chain algorithm ) is a lossless data compression algorithm developed since 1998 by Igor Pavlov, the developer of 7-Zip. It has been used in the 7z format of the 7-Zip archiver since 2001.

This algorithm uses a dictionary compression scheme somewhat similar to the LZ77 algorithm published by Abraham Lempel and Jacob Ziv in 1977 and features a high compression ratio (generally higher than bzip2) and a variable compression-dictionary size (up to 4 GB), while still maintaining decompression speed similar to other commonly used compression algorithms. LZMA2 is a simple container format that allows multi-threaded compression and decompression using multiple separate LZMA streams.

It is used in both in the 7z and the xz format.

Compressed format overview

In LZMA compression, the compressed stream is a stream of bits, encoded using an adaptive binary range coder. The stream is divided into packets, each packet describing either a single byte, or an LZ77 sequence with its length and distance implicitly or explicitly encoded.

Each part of each packet is modelled with independent contexts, so the probability predictions for each bit are correlated with the values of that bit (and related bits from the same field) in previous packets of the same type. Both the lzip and the LZMA SDK documentation describe this stream format.

There are 7 types of packets: LONGREP[*] refers to LONGREP[0–3] packets, *REP refers to both LONGREP and SHORTREP, and *MATCH refers to both MATCH and *REP. LONGREP[n] packets remove the distance used from the list of the most recent distances and reinsert it at the front, to avoid useless repeated entry, while MATCH just adds the distance to the front even if already present in the list and SHORTREP and LONGREP[0] don't alter the list. The length is encoded as follows: As in LZ77, the length is not limited by the distance, because copying from the dictionary is defined as if the copy was performed byte by byte, keeping the distance constant.

Distances are logically 32-bit and distance 0 points to the most recently added byte in the dictionary. The distance encoding starts with a 6-bit "distance slot", which determines how many further bits are needed.

Distances are decoded as a binary concatenation of, from most to least significant, two bits depending on the distance slot, some bits encoded with fixed 0.5 probability, and some context encoded bits, according to the following table (distance slots 0−3 directly encode distances 0−3).

Range coding of bits

LZMA data is at the lowest level decoded one bit at a time by the range decoder, at the direction of the LZMA decoder. Context-based range decoding is invoked by the LZMA algorithm passing it a reference to the "context", which consists of the unsigned 11-bit variable prob (typically implemented using a 16-bit data type) representing the predicted probability of the bit being 0, which is read and updated by the range decoder (and should be initialized to , representing 0.5 probability).

Fixed probability range decoding instead assumes a 0.5 probability, but operates slightly differently from context-based range decoding. The range decoder state consists of two unsigned 32-bit variables, range (representing the range size), and code (representing the encoded point within the range).

Initialization of the range decoder consists of setting range to , and code to the 32-bit value starting at the second byte in the stream interpreted as big-endian; the first byte in the stream is completely ignored. Normalization proceeds in this way: Shift both range and code left by 8 bits Read a byte from the compressed stream Set the least significant 8 bits of code to the byte value read Context-based range decoding of a bit using the prob probability variable proceeds in this way: If range is less than , perform normalization Set bound to If code is less than bound: Set range to bound Set prob to prob + Return bit 0 Otherwise (if code is greater than or equal to the bound): Set range to range − bound Set code to code − bound Set prob to Return bit 1 Fixed-probability range decoding of a bit proceeds in this way: If range is less than , perform normalization Set range to If code is less than range: Return bit 0 Otherwise (if code is greater or equal than range): Set code to code − range Return bit 1 The Linux kernel implementation of fixed-probability decoding in rc_direct() , for performance reasons, does not include a conditional branch, but instead subtracts range from code unconditionally.

The resulting sign bit is used to both decide the bit to return and to generate a mask that is combined with code and added to range. Note that: The division by when computing bound and floor operation is done before the multiplication, not after (apparently to avoid requiring fast hardware support for 32-bit multiplication with a 64-bit result) Fixed probability decoding is not strictly equivalent to context-based range decoding with any prob value, due to the fact that context-based range decoding discards the lower 11 bits of range before multiplying by prob as just described, while fixed probability decoding only discards the last bit

References

LZMA Utils = XZ Utils Windows Binaries for XZ Utils Data compression, Compressors & Archivers

Text derived from https://en.wikipedia.org/w/index.php?oldid=1375472761 under CC BY-SA 4.0; modifications have been made.

References

  1. ↩Wikipedia “LZMA” revision 1375472761 · retrieved 2026-10-20 publication date (×1) · confidence 0.95 revision URL