LZMA

LZMA（英語：Lempel–Ziv–Markov chain algorithm）是2001年以来得到发展的一个数据压缩算法，它用于7-Zip归档工具中的7z格式和 Unix-like 下的 xz 格式。它使用类似于LZ77的字典编码机制，在一般的情況下壓縮率比bzip2為高，用於壓縮的字典檔案大小可達4GB。

C++语言写成的LZMA开放源码压缩库使用了区间编码支持的LZ77改进压缩算法以及特殊的用于二进制的预处理程序。LZMA 对数据流、重复序列大小以及重续序列位置单独进行了压缩。LZMA支持几种散列链变体、二叉树以及基数树作为它的字典查找算法基础。

特性

BCJ / BCJ2二进制文件压缩

BCJ / BCJ2压缩工具所附带的LZMA SDK包括：在X86、ARM、PowerPC、IA-64以及ARM Thumb处理器上在压缩之前跳转目标进行归一化处理。对于x86平台来说，这是一个近跳转、近调用以及近条件跳转需要从“向后跳1665字节”这样的机器语言归一化到“跳转到5554”这样的格式，但是短跳转及短条件跳转不需要进行这样的处理。

BCJ与BCJ2之间的区别在于前者只将近跳转及近调用目标地址转换到归一化的形式，而BCJ2只将x86平台下的近跳转、近调用及条件近跳转目标分别进行压缩。

实现和可移植性

一些Windows作業系統专有的特性深深嵌入在原始程序中，使得最初很难生成一个与Unix等系统兼容的版本。然而，LZMA 由于其开放源码特性，仍然最终获得了各种平台的实现：

7-Zip/p7zip 参考实现

主条目：7-zip和p7zip

在GNU通用公共許可證下發佈的 7-zip 參考版本有以下幾個特點：

• 高壓縮比
• 解壓縮程式碼較小：約5 KB
• 解壓縮時僅需少量記憶體（取決於字典大小）
• 解壓縮速度：在一部2GHz的處理器上運行，約可達10-20MB每秒的速度。
• 支援在多核心系统上多執行緒运行（包括超執行緒）。

这个特点使得这个这个算法的解压过程非常适合于嵌入式系统应用的场合。p7zip 为 7-zip 的 POSIX 系统移植。

xz 和 LZMA Unix Port

主条目：xz

LZMA Unix Port 是一个只移植了 7-zip 中 LZMA 压缩代码的版本，内含命令行参数类似于 gzip 的基于数据流的压缩工具。它不是一个归档工具，而只是一个普通的压缩工具，并且由于它在没有数据头中没有未压缩文件大小的UInt64变量，所以它与7-zip生成的LZMA数据流中不同。7-zip使用一种更加灵活的归档格式7z，因此不能由此工具解压。

后来类似的 xz 替代了 LZMA Unix Port，提供了更好的压缩功能，并最终以其优异的性能和压缩比成为了不少开源软件（例如 Linux 内核源码、Debian deb 和 Fedora rpm）的压缩方式之一，甚至是默认压缩方式。xz 命令行程序曾有过一个名为 pxz 的分支，提供多线程压缩功能，后来 xz 在 5.2 时本身就直接提供多线程了。

lzip

主条目：lzip

Lzip 是另一个 Unix-like 系统下的 LZMA 压缩格式，其主要目的之一就是和 xz 竞争。与 xz 相比，它的最大亮点在于提供更简单的文件格式和因此得来的更方便的数据恢复。Lzip 的格式如此简单以至于其文档中就存在一个解压器实现，于是未来的数据考古学家即使在量子计算机使得 LZMA 无用多时之后只靠文档也能成功解压文件。

应用

使用或者支持LZMA的软件有：

• Nullsoft Scriptable Install System
• Inno Setup
• Linux 内核（cramfs、SquashFS、initrd 等）、GRUB
• lrzip （页面存档备份，存于互联网档案馆）（"long range zip", or "LZMA rzip"）
• PyLZMA （页面存档备份，存于互联网档案馆），Igor Pavlov的LZMA SDK的Python语言接口
• FreeArc （页面存档备份，存于互联网档案馆），归档工具及LZMA SDK的Haskell语言接口
• 用于Pascal语言的LZMA SDK （页面存档备份，存于互联网档案馆）
• 7-Zip
• osu!(用于记录玩家的游戏回放，osu!将光标移动信息以LZMA格式压缩为存档。)

压缩格式表示

LZMA的压缩输出流是一个比特流，采用自适应二进制行程编码器（adaptive binary range coder）。比特流划分为包（packet），每个包或者表示一个字节的受压缩数据，或者如同LZ77的压缩输出序列那样的长度与距离的对（pair）。每个包得每个部分作为独立的上下文（context），从而对每个比特的概率预测仅相关于前一个包的同类型比特值。

有7类包：

包的比特序列	包名	描述
0 + byteCode	LIT	单个字节，采用自适应二进制行程编码器。
1+0 + len + dist	MATCH	一个典型的LZ77序列使用长度与距离。
1+1+0+0	SHORTREP	单个字节的LZ77序列。距离等于上个LZ77包使用的距离。
1+1+0+1 + len	LONGREP[0]	单个LZ77序列。距离等于上个LZ77包使用的距离。
1+1+1+0 + len	LONGREP[1]	单个LZ77序列。距离等于倒数第二个LZ77包使用的距离。
1+1+1+1+0 + len	LONGREP[2]	单个LZ77序列。距离等于倒数第三个LZ77包使用的距离。
1+1+1+1+1 + len	LONGREP[3]	单个LZ77序列。距离等于倒数第四个LZ77包使用的距离。

LONGREP[*] 表示LONGREP[0-3]四种包, *REP指称LONGREP 与SHORTREP, *MATCH指称MATCH或*REP.

LONGREP[n]包删除了对距离的直接表示，而是使用包序列最近四个距离。

包的长度部分表示如下：

长度比特序列	描述
0+ 3 bits	长度用3比特编码，表示 2 到 9.
1+0+ 3 bits	长度用3比特编码，表示 10到17.
1+1+ 8 bits	长度用8比特编码，表示 18到273.

如同LZ77, 长度不一定要小于距离。

距离在逻辑上是32比特，距离0表示最近增加到词典的那个字节。

距离的编码以6比特"distance slot"开始，由此可知后面跟着多少比特来补全。这是可变长编码。 距离解码后为比特流，从最显著位到最不显著位。distance slots 0−3直接编码了0−3.

6-bit distance slot	Highest 2 bits	Fixed 0.5 probability bits	跟随的比特位数
0	00	0	0
1	01	0	0
2	10	0	0
3	11	0	0
4	10	0	1
5	11	0	1
6	10	0	2
7	11	0	2
8	10	0	3
9	11	0	3
10	10	0	4
11	11	0	4
12	10	0	5
13	11	0	5
14–62 (even)	10	((slot / 2) − 5)	4
15–63 (odd)	11	(((slot − 1) / 2) − 5)	4

解压缩算法描述

依据嵌入到Linux kernel的 XZ解码算法源文件。

外部链接

• 7-Zip Official Web-Site （页面存档备份，存于互联网档案馆）
• LZMA SDK （页面存档备份，存于互联网档案馆）
• p7zip Unix port of command-line utilities （页面存档备份，存于互联网档案馆）
• PyLZMA Python Wrapper （页面存档备份，存于互联网档案馆）
• Nullsoft Installer uses LZMA
• Inno Setup supports LZMA （页面存档备份，存于互联网档案馆）
• Compress home page
• LZMA support for cramfs filesystem（dead）
• LZMA utils （页面存档备份，存于互联网档案馆）
• FreeArc archiver and Haskell interface to the LZMA library （页面存档备份，存于互联网档案馆）
• at least one perl interface to LZMA library has been published （页面存档备份，存于互联网档案馆）
• Pascal port of the LZMA SDK （页面存档备份，存于互联网档案馆）