LZMA
LZMA(Lempel-Ziv-Markov chain-Algorithm的缩写)是2001年以来得到发展的一个数据压缩算法,它用于7-Zip归档工具中的7z格式和 Unix-like 下的 xz 格式。它使用类似于LZ77的字典编码机制,在一般的情況下壓縮率比bzip2為高,用於壓縮的字典檔案大小可達4GB。
C++语言写成的LZMA开放源码压缩库使用了区间编码支持的LZ77改进压缩算法以及特殊的用于二进制的预处理程序。LZMA 对数据流、重复序列大小以及重续序列位置单独进行了压缩。LZMA支持几种散列链变体、二叉树以及基数树作为它的字典查找算法基础。
特性
实现和可移植性
一些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,提供了更好的压缩功能,并最终以其优异的性能和压缩比[1]成为了不少开源软件(例如 Linux 内核源码、Debian deb[2] 和 Fedora rpm)的压缩方式之一,甚至是默认压缩方式。xz 命令行程序曾有过一个名为 pxz 的分支,提供多线程压缩功能,后来 xz 在 5.2 时本身就直接提供多线程了。
应用
使用或者支持LZMA的软件有:
压缩格式表示
LZMA的压缩输出流是一个比特流,采用自适应二进制行程编码器(adaptive binary range coder)。比特流划分为包(packet),每个包或者表示一个字节的被压缩数据,或者如同LZ77的压缩输出序列那样的长度与距离的对(pair)。每个包得每个部分作为独立的上下文(context),从而对每个比特的概率预测仅相关于前一个包的同类型比特值。
有7类包:[5]
包的比特序列 | 包名 | 描述 |
---|---|---|
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 |
參考資料
- Lasse Collin. . 2005-05-31 [2015-10-21].
- Guillem Jover. . Debian Package QA. [2015-10-21].
- Diaz, Diaz. . LZIP (nongnu).
- Antonio Diaz Diaz. .
- the source of LZMA SDK
- Collin, Lasse; Pavlov, Igor. . [2013-06-16].
外部链接
- 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