https://arolstar52-zhtest.hf.space/index.php?action=history&feed=atom&title=LZMALZMA - 版本历史2026-07-16T00:26:26Z在这个wiki上该页的修订历史MediaWiki 1.43.9https://arolstar52-zhtest.hf.space/index.php?title=LZMA&diff=168147&oldid=previmported>Willy1018-bot：BOTR：批量替換所有lang-xx模板為langx模板2025-07-02T14:41:07Z<p><a href="https://en.wikipedia.org/wiki/%E6%9C%BA%E5%99%A8%E4%BA%BA/%E4%BD%9C%E4%B8%9A%E8%AF%B7%E6%B1%82#.E8.AB.8B.E6.B1.82.E6.89.B9.E9.87.8F.E6.9B.BF.E6.8F.9B.E6.89.80.E6.9C.89lang-xx.E6.A8.A1.E6.9D.BF.E7.82.BAlangx.E6.A8.A1.E6.9D.BF" class="extiw" title="wikipedia:机器人/作业请求">BOTR</a>：批量替換所有lang-xx模板為langx模板</p>
<p><b>新页面</b></p><div>{{noteTA|G1=IT}}<br />
'''LZMA'''（{{langx|en|Lempel–Ziv–Markov chain algorithm}}）是2001年以来得到发展的一个[[数据压缩]]算法，它用于[[7-Zip]]归档工具中的[[7z]]格式和 [[Unix-like]] 下的 [[xz]] 格式。它使用类似于[[LZ77与LZ78|LZ77]]的{{tsl|en|Dictionary coder|字典编码}}机制，在一般的情況下壓縮率比[[bzip2]]為高，用於壓縮的字典檔案大小可達4GB。<br />
<br />
[[C++]]语言写成的LZMA[[开放源码]]压缩库使用了[[区间编码]]支持的[[LZ77与LZ78|LZ77]]改进压缩算法以及特殊的用于二进制的预处理程序。LZMA 对数据流、重复序列大小以及重续序列位置单独进行了压缩。LZMA支持几种[[哈希链|散列链]]变体、[[二叉树]]以及[[基数树]]作为它的字典查找算法基础。<br />
<br />
== 特性 ==<br />
<br />
=== BCJ / BCJ2二进制文件压缩 ===<br />
<br />
BCJ / BCJ2压缩工具所附带的LZMA SDK包括：在[[X86]]、[[ARM]]、[[PowerPC]]、[[IA-64]]以及[[ARM#Thumb|ARM Thumb]]处理器上在压缩之前跳转目标进行归一化处理。对于x86平台来说，这是一个近跳转、近调用以及近条件跳转需要从“向后跳1665字节”这样的机器语言归一化到“跳转到5554”这样的格式，但是短跳转及短条件跳转不需要进行这样的处理。<br />
<br />
BCJ与BCJ2之间的区别在于前者只将近跳转及近调用目标地址转换到归一化的形式，而BCJ2只将x86平台下的近跳转、近调用及条件近跳转目标分别进行压缩。<br />
<br />
== 实现和可移植性 ==<br />
<br />
一些[[Windows作業系統]]专有的特性深深嵌入在原始程序中，使得最初很难生成一个与[[Unix]]等系统兼容的版本。然而，LZMA 由于其[[开放源码]]特性，仍然最终获得了各种平台的实现：<br />
<br />
=== 7-Zip/p7zip 参考实现 ===<br />
<br />
{{main|7-zip|p7zip}}<br />
<br />
在[[GPL|GNU通用公共許可證]]下發佈的 7-zip 參考版本有以下幾個特點：<br />
<br />
* 高壓縮比<br />
* 解壓縮程式碼較小：約5 KB<br />
* 解壓縮時僅需少量記憶體（取決於字典大小）<br />
* 解壓縮速度：在一部2GHz的處理器上運行，約可達10-20MB每秒的速度。<br />
* 支援在[[多核心]]系统上[[多執行緒]]运行（包括[[超執行緒]]）。<br />
<br />
这个特点使得这个这个算法的解压过程非常适合于[[嵌入式系统]]应用的场合。p7zip 为 [[7-zip]] 的 POSIX 系统移植。<br />
<br />
=== xz 和 LZMA Unix Port ===<br />
<br />
{{main|xz}}<br />
<br />
LZMA Unix Port 是一个只移植了 7-zip 中 LZMA 压缩代码的版本，内含命令行参数类似于 [[gzip]] 的基于数据流的压缩工具。它不是一个归档工具，而只是一个普通的压缩工具，并且由于它在没有数据头中没有未压缩文件大小的UInt64变量，所以它与7-zip生成的LZMA数据流中不同。[[7-zip]]使用一种更加灵活的归档格式[[7z]]，因此不能由此工具解压。<br />
<br />
后来类似的 xz 替代了 LZMA Unix Port，提供了更好的压缩功能，并最终以其优异的性能和压缩比<ref>{{cite web|author1=Lasse Collin|title=A Quick Benchmark: Gzip vs. Bzip2 vs. LZMA|url=http://tukaani.org/lzma/benchmarks.html|accessdate=2015-10-21|ref=gzip_bzip_lzma_bench|date=2005-05-31|archive-date=2020-11-12|archive-url=https://web.archive.org/web/20201112013945/https://tukaani.org/lzma/benchmarks.html}}</ref>成为了不少开源软件（例如 [[Linux]] 内核源码、[[Debian]] deb<ref name=dpkg_use_xz>{{cite web|author1=Guillem Jover|title=Accepted dpkg 1.17.0 (source amd64 all)|url=http://packages.qa.debian.org/d/dpkg/news/20130727T040302Z.html|website=Debian Package QA|accessdate=2015-10-21|archive-date=2017-07-06|archive-url=https://web.archive.org/web/20170706124615/https://packages.qa.debian.org/d/dpkg/news/20130727T040302Z.html}}</ref>和 [[Fedora (作業系統)|Fedora]] rpm）的压缩方式之一，甚至是默认压缩方式。xz 命令行程序曾有过一个名为 pxz 的分支，提供多线程压缩功能，后来 xz 在 5.2 时本身就直接提供多线程了。<br />
<br />
=== lzip ===<br />
{{main|{{tsl|en|lzip|}}}}<br />
<br />
Lzip 是另一个 [[Unix-like]] 系统下的 LZMA 压缩格式，其主要目的之一就是和 xz 竞争。与 xz 相比，它的最大亮点在于提供更简单的文件格式和因此得来的更方便的数据恢复<ref name=lzip_bench>{{cite web|last1=Diaz|first1=Diaz|title=Lzip Benchmarks|url=http://lzip.nongnu.org/lzip_benchmark.html|publisher=LZIP (nongnu)|access-date=2015-10-21|archive-date=2020-06-07|archive-url=https://web.archive.org/web/20200607220953/http://lzip.nongnu.org/lzip_benchmark.html}}</ref><ref>{{cite web|title=lziprecover|author1=Antonio Diaz Diaz|url=http://lzip.nongnu.org/lziprecover.html|access-date=2015-10-21|archive-date=2020-06-27|archive-url=https://web.archive.org/web/20200627025910/http://lzip.nongnu.org/lziprecover.html}}</ref>。Lzip 的格式如此简单以至于其文档中就存在一个解压器实现，于是未来的数据考古学家即使在[[量子计算机]]使得 LZMA 无用多时之后只靠文档也能成功解压文件。<br />
<br />
== 应用 ==<br />
<br />
使用或者支持LZMA的软件有：<br />
<br />
* [[Nullsoft Scriptable Install System]]<br />
* [[Inno Setup]]<br />
* [[Linux]] 内核（[[cramfs]]、[[SquashFS]]、[[initrd]] 等）、[[GRUB]]<br />
* [http://ck.kolivas.org/apps/lrzip/ lrzip] {{Wayback|url=http://ck.kolivas.org/apps/lrzip/ |date=20201130041617 }}（"long range zip", or "LZMA [[rzip]]"）<br />
* [http://www.joachim-bauch.de/projects/python/pylzma PyLZMA] {{Wayback|url=http://www.joachim-bauch.de/projects/python/pylzma |date=20100402042916 }}，Igor Pavlov的LZMA SDK的[[Python]]语言接口<br />
* [http://freearc.narod.ru/ FreeArc] {{Wayback|url=http://freearc.narod.ru/ |date=20201021011924 }}，归档工具及LZMA SDK的[[Haskell]]语言接口<br />
* 用于[[Pascal語言|Pascal]]语言的[http://www.birtles.org.uk/programming/ LZMA SDK] {{Wayback|url=http://www.birtles.org.uk/programming/ |date=20201128180344 }}<br />
* [[7-Zip]]<br />
* [[osu!]](用于记录玩家的游戏回放，[[osu!]]将光标移动信息以LZMA格式压缩为存档。)<br />
<br />
== 压缩格式表示 ==<br />
<br />
LZMA的压缩输出流是一个比特流，采用自适应二进制行程编码器（adaptive binary range coder）。比特流划分为包（packet），每个包或者表示一个字节的受压缩数据，或者如同LZ77的压缩输出序列那样的长度与距离的对（pair）。每个包得每个部分作为独立的上下文（context），从而对每个比特的概率预测仅相关于前一个包的同类型比特值。<br />
<br />
有7类包：<ref>{{Cite web |url=http://7-zip.org/sdk.html |title=the source of LZMA SDK |access-date=2016-08-04 |archive-date=2014-06-09 |archive-url=https://wayback.archive-it.org/all/20140609200859/http://www.7-zip.org/sdk.html }}</ref><br />
<br />
{| class="wikitable" border="1"<br />
|-<br />
! 包的比特序列<br />
! 包名<br />
! 描述<br />
|-<br />
| 0 + byteCode<br />
| LIT<br />
| 单个字节，采用自适应二进制行程编码器。<br />
|-<br />
| 1+0 + len + dist<br />
| MATCH<br />
| 一个典型的LZ77序列使用长度与距离。<br />
|-<br />
| 1+1+0+0<br />
| SHORTREP<br />
| 单个字节的LZ77序列。距离等于上个LZ77包使用的距离。<br />
|-<br />
| 1+1+0+1 + len<br />
| LONGREP[0]<br />
| 单个LZ77序列。距离等于上个LZ77包使用的距离。<br />
|-<br />
| 1+1+1+0 + len<br />
| LONGREP[1]<br />
| 单个LZ77序列。距离等于倒数第二个LZ77包使用的距离。<br />
|-<br />
| 1+1+1+1+0 + len<br />
| LONGREP[2]<br />
| 单个LZ77序列。距离等于倒数第三个LZ77包使用的距离。<br />
|-<br />
| 1+1+1+1+1 + len<br />
| LONGREP[3]<br />
| 单个LZ77序列。距离等于倒数第四个LZ77包使用的距离。<br />
|}<br />
<br />
LONGREP[*] 表示LONGREP[0-3]四种包, *REP指称LONGREP 与SHORTREP, *MATCH指称MATCH或*REP.<br />
<br />
LONGREP[n]包删除了对距离的直接表示，而是使用包序列最近四个距离。<br />
<br />
包的长度部分表示如下：<br />
{| class="wikitable" border="1"<br />
|-<br />
! 长度比特序列<br />
! 描述<br />
|-<br />
| 0+ 3 bits<br />
| 长度用3比特编码，表示 2 到 9.<br />
|-<br />
| 1+0+ 3 bits<br />
| 长度用3比特编码，表示 10到17.<br />
|-<br />
| 1+1+ 8 bits<br />
| 长度用8比特编码，表示 18到273.<br />
|}<br />
<br />
如同LZ77, 长度不一定要小于距离。<br />
<br />
距离在逻辑上是32比特，距离0表示最近增加到词典的那个字节。<br />
<br />
距离的编码以6比特"distance slot"开始，由此可知后面跟着多少比特来补全。这是可变长编码。<br />
距离解码后为比特流，从最显著位到最不显著位。distance slots 0−3直接编码了0−3.<br />
<br />
{| class="wikitable" border="1"<br />
|-<br />
! 6-bit distance slot<br />
! Highest 2 bits<br />
! Fixed 0.5 probability bits<br />
! 跟随的比特位数<br />
|-<br />
| 0<br />
| 00<br />
| 0<br />
| 0<br />
|-<br />
| 1<br />
| 01<br />
| 0<br />
| 0<br />
|-<br />
| 2<br />
| 10<br />
| 0<br />
| 0<br />
|-<br />
| 3<br />
| 11<br />
| 0<br />
| 0<br />
|-<br />
| 4<br />
| 10<br />
| 0<br />
| 1<br />
|-<br />
| 5<br />
| 11<br />
| 0<br />
| 1<br />
|-<br />
| 6<br />
| 10<br />
| 0<br />
| 2<br />
|-<br />
| 7<br />
| 11<br />
| 0<br />
| 2<br />
|-<br />
| 8<br />
| 10<br />
| 0<br />
| 3<br />
|-<br />
| 9<br />
| 11<br />
| 0<br />
| 3<br />
|-<br />
| 10<br />
| 10<br />
| 0<br />
| 4<br />
|-<br />
| 11<br />
| 11<br />
| 0<br />
| 4<br />
|-<br />
| 12<br />
| 10<br />
| 0<br />
| 5<br />
|-<br />
| 13<br />
| 11<br />
| 0<br />
| 5<br />
|-<br />
| 14–62 (even)<br />
| 10<br />
| ((slot / 2) − 5)<br />
| 4<br />
|-<br />
| 15–63 (odd)<br />
| 11<br />
| (((slot − 1) / 2) − 5)<br />
| 4<br />
|}<br />
== 解压缩算法描述 ==<br />
依据嵌入到Linux kernel的 [[Xz|XZ]]解码算法源文件<ref>{{cite web<br />
| url=https://git.kernel.org/cgit/linux/kernel/git/torvalds/linux.git/tree/lib/xz/xz_dec_lzma2.c<br />
| title=lib/xz/xz_dec_lzma2.c<br />
| first1=Lasse<br />
| last1=Collin<br />
| first2=Igor<br />
| last2=Pavlov<br />
| accessdate=2013-06-16<br />
| archive-date=2019-10-18<br />
| archive-url=https://web.archive.org/web/20191018032241/https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/lib/xz/xz_dec_lzma2.c<br />
}}</ref>。<br />
<!--<br />
===比特的区间编码===<br />
<br />
LZMA data is at the lowest level decoded one bit at a time by the range decoder, at the direction of the LZMA decoder.<br />
<br />
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 1, which is read and updated by the range decoder (and should be initialized to 2^10, representing 0.5 probability).<br />
<br />
Fixed probability range decoding instead assumes a 0.5 probability, but operates slightly differently from context-based range decoding.<br />
<br />
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).<br />
<br />
Initialization of the range decoder consists of setting ''range'' to 2<sup>32</sup>&nbsp;−&nbsp;1, 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.<br />
<br />
Normalization proceeds in this way:<br />
# Shift both ''range'' and ''code'' left by 8 bits<br />
# Read a byte from the compressed stream<br />
# Set the least significant 8 bits of ''code'' to the byte value read<br />
<br />
Context-based range decoding of a bit using the ''prob'' probability variable proceeds in this way:<br />
# If ''range'' is less than 2^24, perform normalization<br />
# Set ''bound'' to floor(''range'' / 2^11) * ''prob''<br />
# If ''code'' is less than ''bound'':<br />
## Set ''range'' to ''bound''<br />
## Set ''prob'' to ''prob'' + floor((2^11 - ''prob'') / 2^5)<br />
## Return bit 0<br />
# Otherwise (if ''code'' is greater than or equal to the ''bound''):<br />
## Set ''range'' to ''range'' - ''bound''<br />
## Set ''code'' to ''code'' - ''bound''<br />
## Set ''prob'' to ''prob'' - floor(''prob'' / 2^5)<br />
## Return bit 1<br />
<br />
Fixed-probability range decoding of a bit proceeds in this way:<br />
# If ''range'' is less than 2^24, perform normalization<br />
# Set ''range'' to floor(''range'' / 2)<br />
# If ''code'' is less than ''range'':<br />
## Return bit 0<br />
# Otherwise (if ''code'' is greater or equal than ''range''):<br />
## Set ''code'' to ''code'' - ''range''<br />
## Return bit 1<br />
<br />
The Linux kernel implementation of fixed-probability decoding in rc_direct, for performance reasons, doesn't include a conditional branch, but instead subtracts ''range'' from ''code'' unconditionally, and uses the resulting sign bit to both decide the bit to return, and to generate a mask that is combined with ''code'' and added to ''range''.<br />
<br />
Note that:<br />
# The division by 2^11 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)<br />
# 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<br />
<br />
===Range coding of integers ===<br />
<br />
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.<br />
To decode unsigned integers less than ''limit'', an array of (''limit''&nbsp;−&nbsp;1) 11-bit probability variables is provided, which are conceptually arranged as the internal nodes of a complete binary tree with ''limit'' leaves.<br />
<br />
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 doesn't 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.<br />
<br />
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 doesn't make use of this).<br />
<br />
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 log2(''limit'') bits of the result.<br />
<br />
Note that in the rc_bittree 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 2''i'' and 2''i'' + 1. The rc_bittree_reverse 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.<br />
<br />
Fixed probability integer decoding simply performs fixed probability bit decoding repeatedly, reading bits from the most to the least significant.<br />
<br />
===LZMA configuration===<br />
<br />
The LZMA decoder is configured by an ''lclppb'' "properties" byte and a dictionary size.<br />
<br />
The value of the ''lclppb'' byte is ''lc'' + ''lp'' * 9 + ''pb'' * 9 * 5, where:<br />
*''lc'' is the number of high bits of the previous byte to use as a context for literal encoding (the default value used by the LZMA SDK is 3)<br />
*''lp'' is the number of low bits of the dictionary position to include in ''literal_pos_state'' (the default value used by the LZMA SDK is 0)<br />
*''pb'' is the number of low bits of the dictionary position to include in ''pos_state'' (the default value used by the LZMA SDK is 2)<br />
<br />
In non-LZMA2 streams, ''lc'' must not be greater than 8, and ''lp'' and ''pb'' must not be greater than 4.<br />
In LZMA2 streams, (''lc'' + ''lp'') and ''pb'' must not be greater than 4.<br />
<br />
In the 7-zip LZMA file format, configuration is performed by a header containing the "properties" byte followed by the 32-bit little-endian dictionary size in bytes. In LZMA2, the properties byte can optionally be changed at the start of LZMA2 LZMA packets, while the dictionary size is specified in the LZMA2 header as later described.<br />
<br />
===LZMA coding contexts===<br />
<br />
The LZMA packet format has already been described, and this section specifies how LZMA statistically models the LZ-encoded streams, or in other words which probability variables are passed to the range decoder to decode each bit.<br />
<br />
Those probability variables are implemented as multi-dimensional arrays; before introducing them, a few values that are used as indices in these multidimensional arrays are defined.<br />
<br />
The ''state'' value is conceptually based on which of the patterns in the following table match the latest 2-4 packet types seen, and is implemented as a state machine state updated according to the transition table listed in the table every time a packet is output.<br />
<br />
The initial state is 0, and thus packets before the beginning are assumed to be LIT packets.<br />
{| class="wikitable" border="1"<br />
|-<br />
! state<br />
! colspan="4" | previous packets<br />
! colspan="4" | next state when next packet is<br />
|-<br />
!<br />
! 4th previous<br />
! 3rd previous<br />
! 2nd previous<br />
! previous<br />
! LIT<br />
! MATCH<br />
! LONGREP[*]<br />
! SHORTREP<br />
|-<br />
| 0<br />
|<br />
| LIT<br />
| LIT<br />
| LIT<br />
| 0<br />
| 7<br />
| 8<br />
| 9<br />
|-<br />
| 1<br />
|<br />
| MATCH<br />
| LIT<br />
| LIT<br />
| 0<br />
| 7<br />
| 8<br />
| 9<br />
|-<br />
| rowspan="2" | 2<br />
|<br />
| LONGREP[*]<br />
| rowspan="2" | LIT<br />
| rowspan="2" | LIT<br />
| rowspan="2" | 0<br />
| rowspan="2" | 7<br />
| rowspan="2" | 8<br />
| rowspan="2" | 9<br />
|-<br />
| *MATCH<br />
| SHORTREP<br />
|-<br />
| 3<br />
| LIT<br />
| SHORTREP<br />
| LIT<br />
| LIT<br />
| 0<br />
| 7<br />
| 8<br />
| 9<br />
|-<br />
| 4<br />
|<br />
|<br />
| MATCH<br />
| LIT<br />
| 1<br />
| 7<br />
| 8<br />
| 9<br />
|-<br />
| rowspan="2" | 5<br />
| rowspan="2" |<br />
|<br />
| LONGREP[*]<br />
| rowspan="2" | LIT<br />
| rowspan="2" | 2<br />
| rowspan="2" | 7<br />
| rowspan="2" | 8<br />
| rowspan="2" | 9<br />
|-<br />
| *MATCH<br />
| SHORTREP<br />
|-<br />
| 6<br />
|<br />
| LIT<br />
| SHORTREP<br />
| LIT<br />
| 3<br />
| 7<br />
| 8<br />
| 9<br />
|-<br />
| 7<br />
|<br />
|<br />
| LIT<br />
| MATCH<br />
| 4<br />
| 10<br />
| 11<br />
| 11<br />
|-<br />
| 8<br />
|<br />
|<br />
| LIT<br />
| LONGREP[*]<br />
| 5<br />
| 10<br />
| 11<br />
| 11<br />
|-<br />
| 9<br />
|<br />
|<br />
| LIT<br />
| SHORTREP<br />
| 6<br />
| 10<br />
| 11<br />
| 11<br />
|-<br />
| 10<br />
|<br />
|<br />
| *MATCH<br />
| MATCH<br />
| 4<br />
| 10<br />
| 11<br />
| 11<br />
|-<br />
| 11<br />
|<br />
|<br />
| *MATCH<br />
| *REP<br />
| 5<br />
| 10<br />
| 11<br />
| 11<br />
|}<br />
<br />
The ''pos_state'' and ''literal_pos_state'' values consist of respectively the ''pb'' and ''lp'' (up to 4, from the LZMA header or LZMA2 properties packet) least significant bits of the dictionary position (the number of bytes coded since the last dictionary reset modulo the dictionary size). Note that the dictionary size is normally the multiple of a large power of 2, so these values are equivalently described as the least significant bits of the number of uncompressed bytes seen since the last dictionary reset.<br />
<br />
The ''prev_byte_lc_msbs'' value is set to the ''lc'' (up to 4, from the LZMA header or LZMA2 properties packet) most significant bits of the previous uncompressed byte.<br />
<br />
The ''is_REP'' value denotes whether a packet that includes a length is a LONGREP rather than a MATCH.<br />
<br />
The ''match_byte'' value is the byte that would have been decoded if a SHORTREP packet had been used (in other words, the byte found at the dictionary at the last used distance); it is only used just after a *MATCH packet.<br />
<br />
''literal_bit_mode'' is an array of 8 values in the 0-2 range, one for each bit position in a byte, which are 1 or 2 if the previous packet was a *MATCH and it is either the most significant bit position or all the more significant bits in the literal to encode/decode are equal to the bits in the corresponding positions in ''match_byte'', while otherwise it is 0; the choice between the 1 or 2 values depends on the value of the bit at the same position in ''match_byte''.<br />
<br />
The literal/Literal set of variables can be seen as a "pseudo-bit-tree" similar to a bit-tree but with 3 variables instead of 1 in every node, chosen depending on the ''literal_bit_mode'' value at the bit position of the next bit to decode after the bit-tree context denoted by the node.<br />
<br />
The claim, found in some sources, that literals after a *MATCH are coded as the XOR of the byte value with ''match_byte'' is incorrect; they are instead coded simply as their byte value, but using the pseudo-bit-tree just described and the additional context listed in the table below.<br />
<br />
The probability variable groups used in LZMA are those:<br />
{| class="wikitable" border="1"<br />
|-<br />
! XZ name<br />
! LZMA SDK name<br />
! parameterized by<br />
! used when<br />
! coding mode<br />
! if bit 0 then<br />
! if bit 1 then<br />
|-<br />
| is_match<br />
| IsMatch<br />
| ''state'', ''pos_state''<br />
| packet start<br />
| bit<br />
| LIT<br />
| *MATCH<br />
|-<br />
| is_rep<br />
| IsRep<br />
| ''state''<br />
| after bit sequence 1<br />
| bit<br />
| MATCH<br />
| *REP<br />
|-<br />
| is_rep0<br />
| IsRepG0<br />
| ''state''<br />
| after bit sequence 11<br />
| bit<br />
| SHORTREP/<br />
LONGREP[0]<br />
| LONGREP[1-3]<br />
|-<br />
| is_rep0_long<br />
| IsRep0Long<br />
| ''state'', ''pos_state''<br />
| after bit sequence 110<br />
| bit<br />
| SHORTREP<br />
| LONGREP[0]<br />
|-<br />
| is_rep1<br />
| IsRepG1<br />
| ''state''<br />
| after bit sequence 111<br />
| bit<br />
| LONGREP[1]<br />
| LONGREP[2/3]<br />
|-<br />
| is_rep2<br />
| IsRepG2<br />
| ''state''<br />
| after bit sequence 1111<br />
| bit<br />
| LONGREP[2]<br />
| LONGREP[3]<br />
|-<br />
| literal<br />
| Literal<br />
| ''prev_byte_lc_msbs'', ''literal_pos_state'', ''literal_bit_mode''[bit position], bit-tree context<br />
| after bit sequence 0<br />
| 256 values pseudo-bit-tree<br />
| colspan="2" | literal byte value<br />
|-<br />
| dist_slot<br />
| PosSlot<br />
| min(''match_length'', 5), bit-tree context<br />
| distance: start<br />
| 64 values bit-tree<br />
| colspan="2" | distance slot<br />
|-<br />
| dist_special<br />
| SpecPos<br />
| ''distance_slot'', reverse bit-tree context<br />
| distance: 4-13 distance slots<br />
| ((''distance_slot'' >> 1) − 1)-bit reverse bit-tree<br />
| colspan="2" | low bits of distance<br />
|-<br />
| dist_align<br />
| Align<br />
| reverse bit-tree context<br />
| distance: 14+ distance slots, after fixed probability bits<br />
| 4-bit reverse bit-tree<br />
| colspan="2" | low bits of distance<br />
|-<br />
| len_dec.choice<br />
| LenChoice<br />
| ''is_REP''<br />
| match length: start<br />
| bit<br />
| 2-9 length<br />
| 10+ length<br />
|-<br />
| len_dec.choice2<br />
| LenChoice2<br />
| ''is_REP''<br />
| match length: after bit sequence 1<br />
| bit<br />
| 10-17 length<br />
| 18+ length<br />
|-<br />
| len_dec.low<br />
| LenLow<br />
| ''is_REP'', ''pos_state'', bit-tree context<br />
| match length: after bit sequence 0<br />
| 8 values bit-tree<br />
| colspan="2" | low bits of length<br />
|-<br />
| len_dec.mid<br />
| LenMid<br />
| ''is_REP'', ''pos_state'', bit-tree context<br />
| match length: after bit sequence 10<br />
| 8 values bit-tree<br />
| colspan="2" | middle bits of length<br />
|-<br />
| len_dec.high<br />
| LenHigh<br />
| ''is_REP'', bit-tree context<br />
| match length: after bit sequence 11<br />
| 256 values bit-tree<br />
| colspan="2" | high bits of length<br />
|}<br />
<br />
===LZMA2 format===<br />
<br />
The LZMA2 container supports multiple runs of compressed LZMA data and uncompressed data. Each LZMA compressed run can have a different LZMA configuration and dictionary. This improves the compression of partially or completely incompressible files and allows multithreaded compression and multithreaded decompression by breaking the file into runs that can be compressed or decompressed independently in parallel.<br />
<br />
The LZMA2 header consists of a byte indicating the dictionary size:<br />
* 40 indicates a 4 GB − 1 dictionary size<br />
* Even values less than 40 indicate a 2<sup>''v''/2 + 12</sup> bytes dictionary size<br />
* Odd values less than 40 indicate a 3×2<sup>(''v'' − 1)/2 + 11</sup> bytes dictionary size<br />
* Values higher than 40 are invalid<br />
<br />
LZMA2 data consists of packets starting with a control byte, with the following values:<br />
* 0 denotes the end of the file<br />
* 1 denotes a dictionary reset followed by an uncompressed chunk<br />
* 2 denotes an uncompressed chunk without a dictionary reset<br />
* 3-0x7f are invalid values<br />
* 0x80-0xff denotes an LZMA chunk, where the lowest 5 bits are used as bit 16-20 of the uncompressed size minus one, and bit 5-6 indicates what should be reset<br />
<br />
Bits 5-6 for LZMA chunks can be:<br />
* 0: nothing reset<br />
* 1: state reset<br />
* 2: state reset, properties reset using properties byte<br />
* 3: state reset, properties reset using properties byte, dictionary reset<br />
<br />
LZMA state resets cause a reset of all LZMA state except the dictionary, and specifically:<br />
* The range coder<br />
* The ''state'' value<br />
* The last distances for repeated matches<br />
* All LZMA probabilities<br />
<br />
Uncompressed chunks consist of:<br />
* A 16-bit big-endian value encoding the data size minus one<br />
* The data to be copied verbatim into the dictionary and the output<br />
<br />
LZMA chunks consist of:<br />
* A 16-bit big-endian value encoding the low 16-bits of the uncompressed size minus one<br />
* A 16-bit big-endian value encoding the compressed size minus one<br />
* A properties/lclppb byte if bit 6 in the control byte is set<br />
* The LZMA compressed data, starting with the 5 bytes (of which the first is ignored) used to initialize the range coder (which are included in the compressed size)<br />
--><br />
<br />
== 參考資料 ==<br />
{{reflist}}<br />
<br />
== 外部链接 ==<br />
<br />
* [http://www.7-zip.org/ 7-Zip Official Web-Site] {{Wayback|url=http://www.7-zip.org/ |date=20060512045746 }}<br />
* [http://www.7-zip.org/sdk.html LZMA SDK] {{Wayback|url=http://www.7-zip.org/sdk.html |date=20210202185328 }}<br />
* [http://sourceforge.net/projects/p7zip/ p7zip Unix port of command-line utilities] {{Wayback|url=http://sourceforge.net/projects/p7zip/ |date=20210202185255 }}<br />
* [http://www.joachim-bauch.de/projects/python/pylzma PyLZMA Python Wrapper] {{Wayback|url=http://www.joachim-bauch.de/projects/python/pylzma |date=20100402042916 }}<br />
* [https://web.archive.org/web/20080516065536/http://nsis.sourceforge.net/ Nullsoft Installer uses LZMA]<br />
* [http://www.jrsoftware.org/isinfo.php Inno Setup supports LZMA] {{Wayback|url=http://www.jrsoftware.org/isinfo.php |date=20210126030059 }}<br />
* [https://web.archive.org/web/20060903100509/http://www.fromconcentratesoftware.com/Compress/ Compress home page]<br />
* [http://babel.ls.fi.upm.es/~aacosta/twiki/bin/view/Projects/CramfsPatches LZMA support for cramfs filesystem]{{Dead link|date=2019年5月 |bot=InternetArchiveBot |fix-attempted=yes }}（dead）<br />
* [http://tukaani.org/lzma/ LZMA utils] {{Wayback|url=http://tukaani.org/lzma/ |date=20201027013625 }}<br />
* [http://freearc.narod.ru/ FreeArc archiver and Haskell interface to the LZMA library] {{Wayback|url=http://freearc.narod.ru/ |date=20201021011924 }}<br />
* [http://search.cpan.org/search?query=lzma at least one perl interface to LZMA library has been published] {{Wayback|url=http://search.cpan.org/search?query=lzma |date=20191018032240 }}<br />
* [http://www.birtles.org.uk/programming/ Pascal port of the LZMA SDK] {{Wayback|url=http://www.birtles.org.uk/programming/ |date=20201128180344 }}<br />
<br />
{{压缩方法}}<br />
{{Archive formats}}<br />
<br />
[[Category:无损压缩算法]]<br />
[[Category:以色列发明]]</div>imported>Willy1018-bot