数据压缩算法-LZMA
2013-05-24 10:52:36 
阿炯
LZMA(Lempel-Ziv-Markov chain-Algorithm的缩写)是2001年以来得到发展的一个数据压缩算法，它用于7-Zip归档工具中的7z格式。它使用类似于LZ77的字典编码机制，在一般的情况下压缩率比bzip2为高，用于压缩的字典文件大小可达4GB。
C++语言写成的LZMA开放源码压缩库使用了区间编码支持的LZ77改进压缩算法以及特殊的用于二进制的预处理程序，在对数据流、重复串行大小以及重续串行位置单独进行了压缩。
LZMA支持几种散列链变体、二叉树以及基数树作为它的字典查找算法基础。LZMA的原始地址已经在互联网上不可考了，目前最为权威的地址为7-Zip的开发主页上，基本上可以得知LZMA采用的公有领域协议授权。
BCJ与BCJ2二进制文件压缩
BCJ/BCJ2压缩工具所附带的LZMA SDK包括：在X86、ARM、PowerPC、IA-64以及ARM Thumb处理器上在压缩之前跳转目标进行归一化处理。对于x86平台来说，这是一个近跳转、近调用以及近条件跳转需要从“向后跳1665字节”这样的机器语言归一化到“跳转到5554”这样的格式，但是短跳转及短条件跳转不需要进行这样的处理。它们之间的区别在于前者只将近跳转及近调用目标地址转换到归一化的形式，而BCJ2只将x86平台下的近跳转、近调用及条件近跳转目标分别进行压缩。
实现和可移植性
一些Windows操作系统专有的特性深深嵌入在原始程序中，使得最初很难生成一个与Unix等系统兼容的版本；然而LZMA由于其开放源码特性，仍然最终获得了各种平台的实现：
7-Zip/p7zip
在GNU通用公共许可证下发布的 7-zip 参考版本有以下几个特点：
高压缩比
解压缩代码较小：约5 KB
解压缩时仅需少量存储器取决于字典大小
解压缩速度：在一部2GHz的处理器上运行，约可达10-20MB每秒的速度
支持在多核心系统上多线程运行包括超线程。
这个特点使得这个这个算法的解压过程非常适合于嵌入式系统应用的场合。p7zip 为 7-zip 的 POSIX 系统移植。
xz 和 LZMA Unix Port
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 是另一个 Unix-like 系统下的 LZMA 压缩格式，其主要目的之一就是和 xz 竞争。与 xz 相比的最大亮点在于提供更简单的文件格式和因此得来的更方便的数据恢复。Lzip 的格式如此简单以至于其文档中就存在一个解压器实现，于是未来的数据考古学家即使在量子计算机使得 LZMA 无用多时之后只靠文档也能成功解压文件。
压缩格式表示
LZMA的压缩输出流是一个比特流，采用自适应二进制行程编码器adaptive binary range coder。比特流划分为包packet，每个包或者表示一个字节的被压缩数据，或者如同LZ77的压缩输出序列那样的长度与距离的对pair。每个包得每个部分作为独立的上下文context，从而对每个比特的概率预测仅相关于前一个包的同类型比特值。有7类包：
C++语言写成的LZMA开放源码压缩库使用了区间编码支持的LZ77改进压缩算法以及特殊的用于二进制的预处理程序，在对数据流、重复串行大小以及重续串行位置单独进行了压缩。
LZMA支持几种散列链变体、二叉树以及基数树作为它的字典查找算法基础。LZMA的原始地址已经在互联网上不可考了，目前最为权威的地址为7-Zip的开发主页上，基本上可以得知LZMA采用的公有领域协议授权。
BCJ与BCJ2二进制文件压缩
BCJ/BCJ2压缩工具所附带的LZMA SDK包括：在X86、ARM、PowerPC、IA-64以及ARM Thumb处理器上在压缩之前跳转目标进行归一化处理。对于x86平台来说，这是一个近跳转、近调用以及近条件跳转需要从“向后跳1665字节”这样的机器语言归一化到“跳转到5554”这样的格式，但是短跳转及短条件跳转不需要进行这样的处理。它们之间的区别在于前者只将近跳转及近调用目标地址转换到归一化的形式，而BCJ2只将x86平台下的近跳转、近调用及条件近跳转目标分别进行压缩。
实现和可移植性
一些Windows操作系统专有的特性深深嵌入在原始程序中，使得最初很难生成一个与Unix等系统兼容的版本；然而LZMA由于其开放源码特性，仍然最终获得了各种平台的实现：
7-Zip/p7zip
在GNU通用公共许可证下发布的 7-zip 参考版本有以下几个特点：
高压缩比
解压缩代码较小：约5 KB
解压缩时仅需少量存储器取决于字典大小
解压缩速度：在一部2GHz的处理器上运行，约可达10-20MB每秒的速度
支持在多核心系统上多线程运行包括超线程。
这个特点使得这个这个算法的解压过程非常适合于嵌入式系统应用的场合。p7zip 为 7-zip 的 POSIX 系统移植。
xz 和 LZMA Unix Port
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 是另一个 Unix-like 系统下的 LZMA 压缩格式，其主要目的之一就是和 xz 竞争。与 xz 相比的最大亮点在于提供更简单的文件格式和因此得来的更方便的数据恢复。Lzip 的格式如此简单以至于其文档中就存在一个解压器实现，于是未来的数据考古学家即使在量子计算机使得 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 |