Editing LZMA (section)

== Overview ==
LZMA uses a [[Dictionary coder|dictionary compression]] algorithm (a variant of [[LZ77]] with huge dictionary sizes and special support for repeatedly used match distances), whose output is then encoded with a [[range encoding|range encoder]], using a complex model to make a probability prediction of each bit.  The dictionary compressor finds matches using sophisticated dictionary data structures, and produces a stream of literal symbols and phrase references, which is encoded one bit at a time by the range encoder: many encodings are possible, and a [[dynamic programming]] algorithm is used to select an optimal one under certain approximations.<ref name=lzma-sdk-format/>

Prior to LZMA, most encoder models were purely byte-based (i.e. they coded each bit using only a cascade of contexts to represent the dependencies on previous bits from the same byte).  The main innovation of LZMA is that instead of a generic byte-based model, LZMA's model uses contexts specific to the bitfields in each representation of a literal or phrase: this is nearly as simple as a generic byte-based model, but gives much better compression because it avoids mixing unrelated bits together in the same context. Furthermore, compared to classic dictionary compression (such as the one used in [[ZIP (file format)|zip]] and [[gzip]] formats), the dictionary sizes can be and usually are much larger, taking advantage of the large amount of memory available on modern systems.<ref name=lzma-sdk-format/>