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 參考實現
在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 時本身就直接提供多線程了。
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 |
解壓縮演算法描述
參考資料
- ^ Lasse Collin. A Quick Benchmark: Gzip vs. Bzip2 vs. LZMA. 2005-05-31 [2015-10-21]. （原始內容存檔於2020-11-12）.
- ^ Guillem Jover. Accepted dpkg 1.17.0 (source amd64 all). Debian Package QA. [2015-10-21]. （原始內容存檔於2017-07-06）.
- ^ Diaz, Diaz. Lzip Benchmarks. LZIP (nongnu). [2015-10-21]. （原始內容存檔於2020-06-07）.
- ^ Antonio Diaz Diaz. lziprecover. [2015-10-21]. （原始內容存檔於2020-06-27）.
- ^ the source of LZMA SDK. [2016-08-04]. （原始內容存檔於2014-06-09）.
- ^ Collin, Lasse; Pavlov, Igor. lib/xz/xz_dec_lzma2.c. [2013-06-16]. （原始內容存檔於2019-10-18）.
外部連結
- 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 （頁面存檔備份，存於互聯網檔案館）