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 |
解壓縮算法描述[編輯]
依據嵌入到Linux kernel的 XZ解碼算法源文件[6]。
參考資料[編輯]
- ^ 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 （頁面存檔備份，存於網際網路檔案館）
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| ||||||||||||||||||||||||||||||||
