LZMA

LZMA（英语：Lempel–Ziv–Markov chain algorithm）是2001年以来得到发展的一个数据压缩算法，它用于7-Zip归档工具中的7z格式和 Unix-like 下的 xz 格式。它使用类似于LZ77的字典编码（英语：Dictionary coder）机制，在一般的情况下压缩率比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，提供了更好的压缩功能，并最终以其优异的性能和压缩比[1]成为了不少开源软件（例如 Linux 内核源码、Debian deb[2] 和 Fedora rpm）的压缩方式之一，甚至是默认压缩方式。xz 命令行程序曾有过一个名为 pxz 的分支，提供多线程压缩功能，后来 xz 在 5.2 时本身就直接提供多线程了。

lzip

主条目：lzip（英语：lzip）

Lzip 是另一个 Unix-like 系统下的 LZMA 压缩格式，其主要目的之一就是和 xz 竞争。与 xz 相比，它的最大亮点在于提供更简单的文件格式和因此得来的更方便的数据恢复[3][4]。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类包：[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

解压缩算法描述

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

参考资料

  1. ^ Lasse Collin. A Quick Benchmark: Gzip vs. Bzip2 vs. LZMA. 2005-05-31 [2015-10-21]. （原始内容存档于2020-11-12）. 
  2. ^ Guillem Jover. Accepted dpkg 1.17.0 (source amd64 all). Debian Package QA. [2015-10-21]. （原始内容存档于2017-07-06）. 
  3. ^ Diaz, Diaz. Lzip Benchmarks. LZIP (nongnu). [2015-10-21]. （原始内容存档于2020-06-07）. 
  4. ^ Antonio Diaz Diaz. lziprecover. [2015-10-21]. （原始内容存档于2020-06-27）. 
  5. ^ the source of LZMA SDK. [2016-08-04]. （原始内容存档于2014-06-09）. 
  6. ^ Collin, Lasse; Pavlov, Igor. lib/xz/xz_dec_lzma2.c. [2013-06-16]. （原始内容存档于2019-10-18）. 

外部链接