Алгоритм сжатия данных без потерь LZMA и LZMA2

Lossless data compression algorithm

The Lempel–Ziv–Markov chain algorithm (LZMA) is an algorithm used to perform lossless data compression. It has been under development since either 1996 or 1998 by Igor Pavlov and was first used in the 7z format of the 7 Zip archiver. 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 can include both uncompressed data and LZMA data, possibly with multiple different LZMA encoding parameters. LZMA2 supports arbitrarily scalable multithreaded compression and decompression and efficient compression of data which is partially incompressible.

No complete natural language specification of the compressed format seems to exist, other than the one attempted in the following text. The description below is based on the compact XZ Embedded decoder by Lasse Collin included in the Linux kernel source from which the LZMA and LZMA2 algorithm details can be relatively easily deduced: thus, while citing source code as reference is not ideal, any programmer should be able to check the claims below with a few hours of work.

The range decoder also provides the bit tree, reverse bit tree and fixed probability integer decoding facilities, which are used to decode integers, and generalize the single bit decoding described above. To decode unsigned integers less than limit, an array of (limit − 1) 11 bit probability variables is provided, which are conceptually arranged as the internal nodes of a complete binary tree with limit leaves. Non reverse bit tree decoding works by keeping a pointer to the tree of variables, which starts at the root. As long as the pointer does not point to a leaf, a bit is decoded using the variable indicated by the pointer, and the pointer is moved to either the left or right children depending on whether the bit is 0 or 1; when the pointer points to a leaf, the number associated with the leaf is returned. Non reverse bit tree decoding thus happens from most significant to least significant bit, stopping when only one value in the valid range is possible (this conceptually allows to have range sizes that are not powers of two, even though LZMA does not make use of this). Reverse bit tree decoding instead decodes from least significant bit to most significant bits, and thus only supports ranges that are powers of two, and always decodes the same number of bits. It is equivalent to performing non reverse bittree decoding with a power of two limit, and reversing the last bits of the result. In the function in the Linux kernel, integers are actually returned in the [limit, 2 × limit) range (with limit added to the conceptual value), and the variable at index 0 in the array is unused, while the one at index 1 is the root, and the left and right children indices are computed as 2i and 2i + 1. The function instead adds integers in the [0, limit) range to a caller provided variable, where limit is implicitly represented by its logarithm, and has its own independent implementation for efficiency reasons. Fixed probability integer decoding simply performs fixed probability bit decoding repeatedly, reading bits from the most to the least significant.

Similar to the decompression format situation, no complete natural language specification of the encoding techniques in 7 zip or xz seems to exist, other than the one attempted in the following text. The description below is based on the XZ for Java encoder by Lasse Collin, which appears to be the most readable among several rewrites of the original 7 zip using the same algorithms: again, while citing source code as reference is not ideal, any programmer should be able to check the claims below with a few hours of work.

The encoder needs to be able to quickly locate matches in the dictionary. Since LZMA uses very large dictionaries (potentially on the order of gigabytes) to improve compression, simply scanning the whole dictionary would result in an encoder too slow to be practically usable, so sophisticated data structures are needed to support fast match searches.

The simplest approach, called "hash chains", is parameterized by a constant N which can be either 2, 3 or 4, which is typically chosen so that is greater than or equal to the dictionary size. It consists of creating, for each k less than or equal to N, a hash table indexed by tuples of k bytes, where each of the buckets contains the last position where the first k bytes hashed to the hash value associated with that hash table bucket. Chaining is achieved by an additional array which stores, for every dictionary position, the last seen previous position whose first N bytes hash to the same value of the first N bytes of the position in question. To find matches of length N or higher, a search is started using the N sized hash table, and continued using the hash chain array; the search stop after a pre defined number of hash chain nodes has been traversed, or when the hash chains "wraps around", indicating that the portion of the input that has been overwritten in the dictionary has been reached. Matches of size less than N are instead found by simply looking at the corresponding hash table, which either contains the latest such match, if any, or a string that hashes to the same value; in the latter case, the encoder will not be able to find the match. This issue is mitigated by the fact that for distant short matches using multiple literals might require less bits, and having hash conflicts in nearby strings is relatively unlikely; using larger hash tables or even direct lookup tables can reduce the problem at the cost of higher cache miss rate and thus lower performance. Note that all matches need to be validated to check that the actual bytes match currently at that specific dictionary position match, since the hashing mechanism only guarantees that at some past time there were characters hashing to the hash table bucket index (some implementations may not even guarantee that, because they do not initialize the data structures).

The binary tree approach follows the hash chain approach, except that it logically uses a binary tree instead of a linked list for chaining. The binary tree is maintained so that it is always both a search tree relative to the suffix lexicographic ordering, and a max heap for the dictionary position (in other words, the root is always the most recent string, and a child cannot have been added more recently than its parent): assuming all strings are lexicographically ordered, these conditions clearly uniquely determine the binary tree (this is trivially provable by induction on the size of the tree). Since the string to search for and the string to insert are the same, it is possible to perform both dictionary search and insertion (which requires to rotate the tree) in a single tree traversal.

The XZ LZMA2 encoder processes the input in chunks (of up to 2 MB uncompressed size or 64 KB compressed size, whichever is lower), handing each chunk to the LZMA encoder, and then deciding whether to output an LZMA2 LZMA chunk including the encoded data, or to output an LZMA2 uncompressed chunk, depending on which is shorter (LZMA, like any other compressor, will necessarily expand rather than compress some kinds of data). The LZMA state is reset only in the first block, if the caller requests a change of properties and every time a compressed chunk is output. The LZMA properties are changed only in the first block, or if the caller requests a change of properties. The dictionary is only reset in the first block.

Before LZMA2 encoding, depending on the options provided, xz can apply the BCJ filter, which filters executable code to replace relative offsets with absolute ones that are more repetitive, or the delta filter, which replaces each byte with the difference between it and the byte bytes before it. Parallel encoding is performed by dividing the file in chunks which are distributed to threads, and ultimately each encoded (using, for instance, xz block encoding) separately, resulting in a dictionary reset between chunks in the output file.

The LZMA implementation extracted from 7 Zip is available as LZMA SDK. It was originally dual licensed under both the GNU LGPL and Common Public License, with an additional special exception for linked binaries, but was placed by Igor Pavlov in the public domain on December 2, 2008, with the release of version 4.62. is now the default compression method for the .7z format, starting with version 9.30 on October 26, 2012. The reference open source LZMA compression library was originally written in C++ but has been ported to ANSI C, C#, and Java. The 7 Zip implementation uses several variants of hash chains, binary trees and Patricia trees as the basis for its dictionary search algorithm. In addition to LZMA, the SDK and 7 Zip also implements multiple preprocessing filters intended to improve compression, ranging from simple delta encoding (for images) and BCJ for executable code. It also provides some other compression algorithms used in 7z. Decompression only code for LZMA generally compiles to around 5 KB, and the amount of RAM required during decompression is principally determined by the size of the sliding window used during compression. Small code size and relatively low memory overhead, particularly with smaller dictionary lengths, and free source code make the LZMA decompression algorithm well suited to embedded applications.

In addition to the 7 Zip reference implementation, the following support the LZMA format. xz: a streaming implementation that contains a gzip like command line tool, supporting both LZMA and LZMA2 in its xz file format. It made its way into several software of the Unix like world with its high performance (compared to bzip2) and small size (compared to gzip). and Fedora now use xz for compressing their releases. lzip: another LZMA implementation mostly for Unix like systems to be directly competing with xz. It mainly features a simpler file format and therefore easier error recovery. ZIPX: an extension to the ZIP compressions format that was created by WinZip starting with version 12.1. It also can use various other compression methods such as BZip and PPMd.

LZHAM (LZ, Huffman, Arithmetic, Markov), is an LZMA like implementation that trades compression throughput for very high ratios and higher decompression throughput. It was placed by its author in the public domain on 15 September 2020.