davirain

引言

歷史

• 法律問題
• 緊縮政策的興起

當前檔案軟體

未來發展

壓縮技術

• Run-Length Encoding 游程編碼
• Burrow-Length Transform 布魯斯 - 惠勒變換
• Entropy Encoding 熵編碼法
  • Shannon-Fano CodingHuffman
  • CodingArithmetic Coding

壓縮演算法

• Sliding Window Algorithm 滑動窗口演算法
  • LZ77
  • LZR
  • DEFLATE
  • DEFLATE64
  • LZSS
  • LZH
  • LZB
  • ROLZ
  • LZP
  • LZRW11
  • LZJB
  • LZS
  • LZX
  • LZO
  • LZMA
  • LZMA2

Dictionary Algorithm 字典演算法

• LZ78
• LZW
• ZLC
• LZTL
• ZMW
• LZAP
• LZWL
• LZJ

Non-dictionary Algorithm 非字典演算法

• PPM
• bzip2
• PAQ

參考資料

1 Introduction#

壓縮演算法主要有兩大類： 有損和無損。有損數據壓縮演算法通常通過刪除需要大量保真數據的小細節來減少文件的大小。在有損數據壓縮中。由於刪除了基本數據，不可能恢復原始文件。有損數據壓縮通常用於存儲圖像和音頻數據，雖然可以通過數據刪除實現非常高的壓縮比，但本文並未涉及。無損數據壓縮是文件的大小減少，這樣一個解壓函數完全可以恢復原始文件，沒有數據丟失。無損數據壓縮在計算機中無處不在，從節省個人電腦空間到通過網絡發送數據，通過安全 shell 進行通信，或者查看 PNG 或 GIF 圖像。

無損數據壓縮演算法的工作原理是，任何非隨機文件都包含重複信息，這些信息可以通過使用統計建模技術來濃縮，從而確定字符或短語出現的概率。然後可以使用這些統計模型根據發生概率為特定字符或短語生成代碼，並未最常見的數據分配最短的代碼。這些技術包括熵編碼法、游程編碼和使用字典進行壓縮。使用這些技術和其他技術，一個 8 位字符或這種字符的字符串可以用幾位表示，從而刪除大量冗餘數據。

2 History#

20 世紀 70 年代，互聯網變得越來越流行，Lempel-Ziv 演算法被發明出來，自從那以後，數據壓縮才在計算機領域發揮了重要作用。但它在計算機之外的歷史要悠久得多。莫爾斯電碼發明於 1838 年，是數據壓縮最早的例子，因為英語中最常見的字母如 'e' 和 't' 被賦予較短的莫爾斯電碼。後來，隨著大型計算機在 1949 年開始佔據主導地位，Claude Shannon, Robert Fano 發明了 Shanno-Fano 編碼。他們的演算法基於符合出現的概率，為給定數據塊中符號分配代碼。符號出現的概率與代碼長度成反比，因此用較短的方式表示數據。[1]

兩年後，David Huffman 在麻省理工學院學習信息論，並和 Robert Fano 一起上課， Fano 讓學生選擇是寫學期論文還是參加期末考試。Huffman 選擇了學期論文，該論文是關於尋找最有效的二進制編碼方法。在工作了幾個月卻一無所獲之後，huffman 準備丟掉它所有的工作，開始為期末開始而學習，而不是寫論文。就在那個時候，它突然靈光一現，發現了一種與 Shannon-Fano 編碼非常相似但更有效的計數。Shannon-Fano 編碼和 Huffman 編碼的關鍵區別在於，前者的概率樹是自下而上構建的，產生的結果不是最優的，而後者是自上而下構建的。[2]

Shannon-Fano 和 Huffman 編碼的早期實現都是使用硬體和硬體編碼完成的。直到 20 世紀 70 年代，隨著互聯網和在線存儲的出現。軟體壓縮才得以實現，Huffamn 編碼是基於輸入數據動態生成的 [1]. 後來，在 1997 年，Abraham Lempel, Jacob Ziv 發表了他們開創性的 LZ77 演算法，這是第一個使用字典數據的演算法。更具體地說，LZ77 經常使用一種稱為滑動窗口的動態字典。[3] 1978 年，同樣是兩個人發布了他們的 LZ78 演算法，該演算法也使用了字典，與 LZ77 不同的是，該演算法解析輸入數據並生成了靜態字典，而不是動態生成。[4]

2.1 Legal Issues#

LZ77 和 LZ78 演算法都迅速流行起來，產生了許多變種，如圖所示。

自這些演算法被發明以來，大多數演算法已經消亡了，現在只有少數演算法被廣泛使用，包括 DEFLATE, LZMA, LZX. 大多數常用演算法都是從 LZ77 演算法派生出來的。這不是因為技術上的優越性，而是因為 LZ78 演算法在 1984 年 Sperry 申請了衍生物 LZW 演算法的專利，並開始起訴軟體供應商、伺服器管理員，甚至終端用於在沒有許可的情況下使用 GIF 格式，之後，就成了專利受限演算法 [5][6]

當時，UNIX 壓縮使用程序對 LZW 演算法進行了非常小的修改，稱為 LZC，後來由於專利問題而停止使用。其他 UNIX 開發人員也開始偏離使用 LZW 演算法，轉而使用開源演算法。這導致 UNIX 社區採用了基於 deflate 的 gzip 和基於 Burrows-Wheeler transform 的 bzip2 格式。從長遠來看，這對 UNIX 社區是個好處。因為 gzip 和 bzip2 幾乎總是比 LZW 格式實現更高的壓縮比。隨著 LZW 演算法的專利在 2003 年到期。圍繞 LZW 的專利問題已經平息 [5]. 儘管如此，LZW 演算法已經被很大程序上取代，並且只有在 GIF 壓縮中普遍使用。此後也出現了一些 LZW 衍生品，但他們也沒有得到廣泛應用，LZ77 演算法仍然佔據主導地位。

另一場關於 LZS 演算法的法律戰於 1993 年爆發，是由 Stac 電子公司開發的，用於磁碟壓縮軟體，比如 Stacker. 微軟使用 LZS 演算法來開發磁碟壓縮軟體，這款軟體是 MS-DOS 6.0 下發布的。據說可以使磁碟的容量翻一番。當 Stac 電子發現其知識產權被使用時。他對微軟提起了訴訟。微軟後來被判有罪，並被判向 Stac 電子支持 1.2 億美元的損害補償，減去 1360 萬美元的反訴裁定，微軟的侵權並非估計 [7], 儘管 stac 電子公司訴微軟公司一案有很大的判決，但它並沒有像 LZW 專利糾紛那樣阻礙 Lempel-Ziv 演算法的發展。唯一的結果似乎是 LZS 沒有被分配到任何新的演算法。

2.2 The Rise of Deflate#

自從 Lempel-Ziv 演算法被發表以來，企業和其他大型實體就一直在使用數據壓縮，因為它們的存儲需求不斷增加，而數據壓縮可以幫助它們滿足這些需求。然而，直到互聯網開始興起，數據壓縮才開始得到廣泛應用，這是因為在 1980 年代末，出現了對數據壓縮的需求。帶寬要麼受到限制，要麼很昂貴，而數據壓縮有助於緩解這些瓶頸。當萬維網被開發出來時，壓縮變得尤為重要，因為人們開始分享更多的圖像和其他格式，這些格式比文本要大得多。為了滿足需求，開發了幾種新的文件格式，包括 ZIP、GIF 和 PNG，其中包含了壓縮技術。

1985 年，Thom Henderson 通過他的公司 System Enhancement Associates 發布了第一個商業上成功的檔案格式 ARC。由於 ARC 是能夠打包和壓縮文件的首個程序之一，因此在 BBS 社區中特別受歡迎，同時它也是開源的。ARC 格式使用對 LZW 演算法的修改來壓縮數據。Phil Katz 注意到 ARC 的流行，並決定通過使用匯編語言編寫壓縮和解壓縮程序來改進它。他在 1987 年發布了 PKARC 程序作為共享軟體，並因版權侵權被 Henderson 起訴。他被認定有罪，並被迫支付版稅和其他罰款，作為跨許可協議的一部分。他被認定有罪，因為 PKARC 是 ARC 的一個顯然的副本；在某些情況下，甚至註釋中的拼寫錯誤都是相同的。[8]

由於交叉許可協議的限制，Phil Katz 在 1988 年後不能再銷售 PKARC。因此，他在 1989 年創建了一個經過調整的 PKARC 版本，現在被稱為 ZIP 格式。由於它使用了 LZW，所以被認為是受專利限制的，後來 Katz 選擇切換到新的 IMPLODE 演算法。在 1993 年，Katz 發布了 PKZIP 2.0，實現了 DEFLATE 演算法以及其他功能，如分割卷。儘管其已經有很長時間了，但是今天幾乎所有的.zip 文件都遵循 PKZIP 2.0 格式，因此這個 ZIP 格式的版本是無處不在的。

GIF，全稱 Graphics Interchange Format，是由 CompuServe 於 1987 年開發的一種圖形交換格式，旨在允許位圖在傳輸時不會丟失數據（儘管該格式每幀僅限制為 256 種顏色），同時大幅減小文件大小以便在撥號調製解調器上傳輸。然而，像 ZIP 格式一樣，GIF 也基於 LZW 演算法。儘管受到專利限制，但 Unisys 未能充分執行其專利以阻止該格式的傳播。即使是在 20 多年後，GIF 仍然廣泛使用，特別是因其能夠製作動畫。[9]

雖然 GIF 無法被阻止，CompuServe 仍然尋求一個沒有專利限制的格式，於 1994 年推出了 Portable Network Graphics（PNG）格式。和 ZIP 一樣，PNG 標準使用 DEFLATE 演算法來進行壓縮。儘管 DEFLATE 是由 Katz 獲得專利的 [10]，但這一專利從未被執行，因此 PNG 和其他基於 DEFLATE 的格式避免了侵犯專利。雖然 LZW 在壓縮的早期被廣泛採用，但由於 Unisys 的好訴性質，它已經逐漸退出歷史舞台，被速度更快、更高效的 DEFLATE 演算法所取代。DEFLATE 是目前最常用的數據壓縮演算法，有點像壓縮中的瑞士軍刀。

除了在 PNG 和 ZIP 格式中使用 DEFLATE，DEFLATE 在計算機領域的其他地方也非常常見。例如，gzip（.gz）文件格式使用 DEFLATE，因為它本質上是 ZIP 的開源版本。DEFLATE 的其他用途包括 HTTP、SSL 和其他旨在在網絡上實現高效數據壓縮的技術。

不幸的是，Phil Katz 沒有活著看到他的 DEFLATE 演算法征服計算機世界。他多年來一直酗酒，他的生活在 1990 年代末開始瓦解，曾因酒後駕車和其他違規行為多次被捕。2000 年 4 月 14 日，37 歲的卡茨被發現死在一家旅館房間裡。死因是急性胰腺出血，由他屍體旁發現的許多空酒瓶引起的酒精中毒。[11]

2.3 Current Archival Software#

到了 1990 年代中期，新的和更好的格式開始出現，ZIP 格式和其他基於 DEFLATE 的格式不再佔據主導地位。1993 年，Eugene Roshal 發布了他的壓縮軟體 WinRAR，使用專有的 RAR 格式。RAR 的最新版本使用了 PPM 和 LZSS 演算法的組合，但較早的實現情況並不為人所知。RAR 已成為在互聯網上共享文件的標準格式，特別是在分發盜版媒體方面。一個名為 bzip2 的開源 Burrows-Wheeler 變換實現在 1996 年發布，迅速在 UNIX 平台上對 DEFLATE-based gzip 格式產生了很大的競爭。另一個開源壓縮程序在 1999 年發布，即 7-Zip 或.7z 格式。由於其通常較高的壓縮比率以及格式的模組化和開放性，7-Zip 可能是首個挑戰 ZIP 和 RAR 主導地位的格式。這種格式不限於使用一個壓縮演算法，而是可以在 bzip2、LZMA、LZMA2 和 PPMd 等演算法之間進行選擇。最後，在存檔軟體的前沿是 PAQ * 格式。第一個 PAQ 格式由 Matt Mahoney 於 2002 年發布，稱為 PAQ1。PAQ 通過使用稱為上下文混合的技術將兩個或多個統計模型結合起來，從而顯著改進了 PPM 演算法，以生成比任何一個模型單獨預測下一個符號更好的預測。

3 Future Developments#

未來從來都是不確定的，但基於當前的趨勢，可以對數據壓縮的未來做出一些預測。如 PAQ 及其變種的上下文混合演算法開始受到歡迎，它們往往可以實現最高的壓縮比，但速度通常較慢。隨著硬體速度呈指數級增長，遵循摩爾定律，上下文混合演算法將很可能在高壓縮比的情況下大放異彩，因為速度懲罰將被更快的硬體所克服。PAQ 旨在改進的預測部分匹配（PPM）演算法也可能會出現新的變種。最後，Lempel-Ziv Markov Chain 演算法（LZMA）一直表現出優秀的速度和高壓縮比之間的平衡，將很可能產生更多的變種。隨著 LZMA 自從在 7-Zip 格式中推出以來，已經被廣泛採用於許多競爭的壓縮格式中，它甚至可能成為 “贏家”。另一個潛在的發展方向是使用子串枚舉壓縮（CSE），這是一種新興的壓縮技術，尚未看到許多軟體實現。在其樸素形式下，它的表現類似於 bzip2 和 PPM，並且研究人員一直在努力提高其效率。[12]

4 Compression Techniques#

許多不同的技術被用於壓縮數據。大多數壓縮技術不能獨立存在，必須結合起來形成一個壓縮演算法。那些可以獨立存在的壓縮技術通常會在與其他壓縮技術結合時更加有效。大多數這些技術屬於熵編碼器，但還有其他一些常用的技術，如游程編碼和 Burrows-Wheeler 變換。

4.1 Run-Length Encoding#

運行長度編碼是一種非常簡單的壓縮技術，它用一個數字來表示同一字符的連續出現次數，後面跟著這個字符；單個字符編碼為 1 次連續出現。RLE 對於高度冗餘的數據，具有許多相同顏色的像素行的索引圖像或與其他壓縮技術（如 Burrows-Wheeler 變換）結合使用是非常有用的。

下面是 RLE 的一個快速示例：

輸入：AAABBCCCCDEEEEEEAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA

輸出：3A2B4C1D6E38A

4.2 Burrows-Wheeler Transform#

Burrows-Wheeler 變換是一種於 1994 年發明的壓縮技術，旨在可逆地轉換輸入數據塊，使得相同字符的重複出現數量最大化。BWT 本身並不執行任何壓縮操作，它只是將輸入轉換為更有效地由游程編碼器或其他次要壓縮技術編碼的形式。

BWT 的演算法很簡單：

1. 創建一個字符串數組。
2. 生成輸入字符串的所有可能旋轉，並將每個旋轉存儲在數組中。
3. 按字典序對數組進行排序。
4. 返回數組的最後一列。[13]

BWT 通常在具有許多交替出現相同字符的長輸入上效果最佳。以下是在理想輸入上運行該演算法的示例。請注意，＆是文件結束字符：

由於其交替相同的字符，對此輸入執行 BWT 會生成一個最優的結果，另一個演算法可以進一步壓縮，例如 RLE，將產生 “3H＆3A”。儘管這個例子產生了一個最優的結果，但它在大多數真實數據上並不會產生最優結果。

4.3 Entropy Encoding#

在數據壓縮中，熵指的是平均需要表示一個符號或文字所需的最少比特數。基本的熵編碼器結合了統計模型和編碼器。輸入文件被解析並用於生成統計模型，該模型由給定符號出現的概率組成。然後，編碼器將使用統計模型來確定為每個符號分配什麼位或字節碼，以使最常見的符號具有最短的代碼，最不常見的符號具有最長的代碼。

4.3.1 Shannon-Fano Coding#

這是一種最早的壓縮技術，由 Claude Shannon 和 Robert Fano 於 1949 年發明。這種技術涉及生成一個二叉樹來表示每個符號出現的概率。這些符號被排序，以便最常見的符號出現在樹的頂部，最不可能出現的符號出現在底部。

給定一個符號的編碼是通過在 Shannon-Fano 樹中搜索該符號，並附加每個左或右分支的值（0 或 1）來獲取的。例如，如果 “A” 是兩個左分支和一個右分支，它的編碼將是 “0012”。由於它從下往上構建二叉樹的方式，Shannon-Fano 編碼並不總是生成最優代碼。因此，通常使用 Huffman 編碼，因為它能為任何給定的輸入生成最優代碼。

生成 Shannon-Fano 編碼的演算法相當簡單：

1. 解析輸入，計算每個符號的出現次數。
2. 使用符號計數確定每個符號的概率。
3. 按概率排序符號，最可能的符號排在最前面。
4. 為每個符號生成葉節點。
5. 將列表分成兩個部分，同時使左分支的概率大致相等於右分支的概率。
6. 將 0 和 1 分別添加到左和右節點的代碼前面。
7. 遞歸地將步驟 5 和 6 應用於左和右子樹，直到每個節點都是樹中的葉子。

4.3.2 Huffman Coding#

Huffman 編碼是熵編碼的另一種變體，工作方式與 Shannon-Fano 編碼非常相似，但二叉樹是從上向下構建的，以生成最優結果。

生成 Huffman 編碼的演算法與 Shannon-Fano 共享其前幾個步驟：

1. 解析輸入，計算每個符號的出現次數。

2. 使用符號計數確定每個符號的概率。將符號按概率排序，最可能的排在前面。

3. 為每個符號生成葉節點，包括 P，然後將它們添加到隊列中。

4. 當隊列中的節點數量 > 1 時執行以下操作：

   • 從隊列中刪除兩個概率最低的節點。
   • 將 0 和 1 分別添加到左右節點的代碼前綴中。
   • 創建一個新節點，其值等於兩個節點的概率之和。
   • 將第一個節點分配到左分支，將第二個節點分配到右分支。
   • 將節點添加到隊列中。

5. 隊列中剩下的最後一個節點是 Huffman 樹的根節點。[16]

4.3.3 Arithmetic Coding#

這種方法是在 1979 年 IBM 公司開發的，當時該公司正在研究用於其大型計算機的數據壓縮技術。如果目標是獲得最佳的壓縮比，算術編碼可以說是最優秀的熵編碼技術，因為它通常比 Huffman 編碼獲得更好的結果。然而，相對於其他編碼技術，算術編碼要複雜得多。

算術編碼不是將符號的概率分裂成樹形結構，而是通過更改基數並為 0 到基數之間的每個唯一符號分配一個單一值，將輸入數據轉換為 0 到 1 之間的一個有理數。然後，它進一步轉換為一個固定小數位數的二進制數，這是編碼結果。可以通過將基數從二進制更改回原始基數，並將值替換為它們對應的符號，將該值解碼為原始輸出。

計算算術編碼的一般演算法如下：

1. 計算輸入中唯一符號的數量。
2. 這個數字表示算術編碼的基數 b（例如，基數 2 是二進制）。
3. 按照它們出現的順序，為每個唯一的符號分配從 0 到 b 的值。
4. 使用步驟 2 中的值，用它們的編碼替換輸入中的符號。
5. 將步驟 3 中的結果從基數 b 轉換為足夠長的固定小數位二進制數，以保留精度。
6. 將輸入字符串的長度記錄在結果中，因為這對解碼過程是必需的。

以下是一個示例編碼操作，給定輸入 “ABCDAABD”：

1. 發現輸入中有 4 個唯一符號，因此基數為 4。
   長度為 8
2. 為符號分配值：A=0，B=1，C=2，D=3
3. 使用代碼替換輸入：“0.012300134”，其中前導的 0 不是符號。
4. 將 “0.012311234” 從基數 4 轉換為基數 2：“0.011011000001112”
5. 找到結果。請注意，在結果中，輸入長度為 8。

假設為 8 位字符，則輸入長度為 64 位，而其算術編碼僅為 15 位，導致優秀的壓縮比為 24％。此示例演示了在給定有限字符集時，算術編碼如何進行良好的壓縮。

5 Compression Algorithms#

5.1 Sliding Window Algorithms#

5.1.1 LZ77#

發表於 1977 年的 LZ77 演算法是開創先河的演算法。它首次引入了 “滑動窗口” 的概念，這帶來了比更原始演算法更大的壓縮比改進。LZ77 使用三元組來維護字典，這些三元組表示偏移量、運行長度和一個偏差字符。偏移量表示給定短語從文件的開頭開始的距離，運行長度表示從偏移量到偏移量 + 長度的字符數。偏差字符只是表示發現了一個新的短語，並且該短語等於從偏移量到偏移量 + 長度加上偏差字符。使用的字典根據解析文件時滑動窗口的變化而動態改變。例如，滑動窗口可能是 64MB，這意味著字典將包含過去 64MB 輸入數據的條目。

給定輸入 “abbadabba”，輸出將類似於 “abb (0,1,'d')(0,3,'a')”，如下面的示例所示：

雖然這種替換的大小略大於輸入，但通常在輸入數據更長的情況下，它會獲得更小的結果。[3]

5.1.2 LZR#

LZR 是由 Michael Rodeh 在 1981 年改進的 LZ77 演算法。該演算法旨在成為 LZ77 的線性時間替代方法。然而，編碼指針可以指向文件中的任何偏移量，這意味著 LZR 會消耗大量的內存。加上其較差的壓縮比（LZ77 通常更優），這使得 LZR 成為一個不可行的變種。[18][19]

5.1.3 DEFLATE#

DEFLATE 是由 Phil Katz 在 1993 年發明的，是今天大部分壓縮任務的基礎。它只是簡單地將 LZ77 或 LZSS 預處理器與後端的 Huffman 編碼相結合，以在短時間內實現適度壓縮的結果。

5.1.4 DEFLATE64#

DEFLATE64 是 DEFLATE 演算法的一種專有擴展，它將字典大小增加到 64KB（因此得名），並允許在滑動窗口中有更大的距離。與 DEFLATE 相比，它提高了性能和壓縮比。然而，DEFLATE64 的專有性質以及與 DEFLATE 相比的溫和改進導致該格式的採用受限。相反，通常使用像 LZMA 這樣的開源演算法。

5.1.5 LZSS#

LZSS（Lempel-Ziv-Storer-Szymanski）演算法是由 James Storer 和 Thomas Szymanski 於 1982 年首次發布。LZSS 改進了 LZ77，因為它可以檢測替換是否會減小文件大小。如果沒有大小減小，輸入將作為字面值保留在輸出中。否則，輸入的部分將被替換為一個（偏移量，長度）對，其中偏移量表示距離輸入開頭多少個字節，長度表示從該位置讀取多少個字符。與 LZ77 相比，LZSS 的另一個改進是消除了 “下個字符”，只使用偏移量和長度對。

以下是一個簡短的示例，給定輸入 “these theses”，產生了 “ these (0,6) s”，它只節省了一個字節，但對於更大的輸入節省了更多的空間。

LZSS 仍然被許多流行的存檔格式使用，其中最著名的是 RAR。它有時也用於網絡數據壓縮。

5.1.6 LZH#

LZH 是在 1987 年開發的，“Lempel-Ziv Huffman” 的縮寫。它是 LZSS 的一個變種，利用 Huffman 編碼來壓縮指針，從而獲得稍微更好的壓縮效果。然而，使用 Huffman 編碼帶來的改進微不足道，而且壓縮效果不值得使用 Huffman 編碼所付出的性能代價。

5.1.7 LZB#

LZB 是由 Timothy Bell 等人於 1987 年開發的 LZSS 變體。與 LZH 類似，LZB 旨在通過更有效地編碼 LZSS 指針來減少壓縮文件的大小。它通過逐漸增加指針的大小來實現這一目標，隨著滑動窗口的增大，指針也變得更大。與 LZSS 和 LZH 相比，它可以實現更高的壓縮率，但由於指針的額外編碼步驟，它仍然比 LZSS 慢。

5.1.8 ROLZ#

ROLZ 指的是 “Reduced Offset Lempel-Ziv”，它的目標是通過限制 offset length 來減少編碼 offset-length 對所需的數據量，從而提高 LZ77 的壓縮率。這種 LZ77 的衍生演算法最初出現在 Ross Williams 的 LZRW4 演算法中，其他實現包括 BALZ、QUAD 和 RZM。高度優化的 ROLZ 可以實現幾乎與 LZMA 相同的壓縮比，但是由於缺乏廣泛的應用，ROLZ 的流行度較低。

5.1.9 LZP#

LZP 是 “Lempel-Ziv + Prediction” 的縮寫。它是 ROLZ 演算法的一個特例，其中偏移量被減小到 1。有幾種不同的變體，使用不同的技術來實現更快的操作或更好的壓縮比率。LZW4 實現了算術編碼器，以獲得最佳的壓縮比率，但代價是速度較慢。[22]

5.1.10 LZRW1#

Ron Williams 在 1991 年創建了 LZRW1 演算法，首次引入了 “減少偏移量的 Lempel-Ziv 壓縮” 概念。LZRW1 可以實現高壓縮比，同時保持速度快和高效的特點。Ron Williams 還創建了幾個改進 LZRW1 的變體，例如 LZRW1-A、2、3、3-A 和 4 等。

5.1.11 LZJB#

Jeff Bonwick 於 1998 年創建了他的 Lempel-Ziv Jeff Bonwick 演算法，用於 Solaris Z 文件系統（ZFS）。它被認為是 LZRW 演算法的變體，特別是 LZRW1 變體，旨在實現最大壓縮速度。由於它用於文件系統，速度尤為重要，以確保壓縮演算法不成為磁碟操作的瓶頸。

5.1.12 LZS#

Lempel-Ziv-Stac 演算法是由 Stac Electronics 於 1994 年為磁碟壓縮軟體開發的一種改進型 LZ77 演算法。它在輸出中區分了字面符號和偏移長度對，同時省略了下個遇到的符號，LZS 演算法在功能上與 LZSS 演算法最相似。

5.1.13 LZX#

LZX 演算法是由 Jonathan Forbes 和 Tomi Poutanen 於 1995 年為 Amiga 計算機開發的。LZX 中的 X 沒有特殊含義。Forbes 於 1996 年將該演算法出售給了微軟，並為微軟工作，使其進一步改進以用於 Microsoft 的 cabinet (.CAB) 格式。該演算法也被微軟用於壓縮壓縮的 HTML 幫助（CHM）文件，Windows Imaging Format（WIM）文件和 Xbox Live Avatars。

5.1.14 LZO#

LZO 是由 Markus Oberhumer 在 1996 年開發的，其開發目標是實現快速的壓縮和解壓縮。它允許調整壓縮級別，並且最高壓縮級別僅需要額外的 64KB 內存，而解壓縮僅需要輸入和輸出緩衝區。LZO 的功能與 LZSS 演算法非常相似，但其針對的是速度而不是壓縮比率。[26]

5.1.15 LZMA#

Lempel-Ziv Markov chain 演算法最早在 1998 年隨 7-Zip 壓縮軟體的發布而公開，用於.7z 文件格式。它通常能夠比 bzip2、DEFLATE 和其他演算法獲得更好的壓縮效果。LZMA 使用一系列壓縮技術來實現輸出。首先，採用修改版的 LZ77 演算法對數據進行位級別的解析，而不是傳統的字節級別。然後，LZ77 演算法的輸出經過算術編碼。根據特定的 LZMA 實現，可以應用更多技術。結果通常比大多數其他 LZ 變種的壓縮比例都要好，這主要是由於採用了位級別的壓縮方法，而不是字節級別的壓縮。

5.1.16 LZMA2#

LZMA2 是對原始 LZMA 演算法的漸進改進，最初在 2009 年通過 7-Zip 存檔軟體的更新引入 [28]。LZMA2 改善了 LZMA 演算法的多線程能力和性能，並更好地處理無法壓縮的數據，從而實現略微更好的壓縮。

5.1.17 Statistical Lempel-Ziv#

統計 Lempel-Ziv 是由 Sam Kwong 博士和 Yu Fan Ho 在 2001 年提出的概念。它的基本原則是將數據的統計分析與 LZ77 變體演算法相結合，以進一步優化存儲在字典中的編碼。[29]

5.2 Dictionary Algorithms#

5.2.1 LZ78#

LZ78 演算法是由 Lempel 和 Ziv 於 1978 年創造的，因此縮寫中包含 “78”。與使用滑動窗口生成字典的方法不同，輸入數據可以預處理以生成具有輸入無限範圍的字典，或者在解析文件時形成字典。LZ78 採用後一種策略。字典大小通常限制為幾兆字節，或所有代碼均為一定數量的字節，例如 8 個字節；這樣做是為了減少內存要求。大多數 LZ78 類型演算法如何處理字典已滿是它們的區別所在。

在解析文件的過程中，LZ78 演算法將遇到的每個新字符或字符串添加到字典中。對於輸入中的每個符號，會生成一個以字典索引和未知符號為形式的字典條目；如果一個符號已經在字典中，則字典將被搜索以查找當前符號和其後面的符號的子字符串。最長子字符串匹配的索引用於字典索引。由字典索引指向的數據將添加到未知子串的最後一個字符。如果當前符號未知，則將字典索引設置為 0，以指示它是一個單字符條目。這些條目形成了一個類似於鏈表的數據結構。

例如輸入 "abbadabbaabaad" 將生成輸出 "(0,a)(0,b)(2,a)(0,d)(1,b)(3,a)(6,d)"，下面的示例演示了它是如何得出的：

5.2.2 LZW#

LZW 是 Lempel-Ziv-Welch 演算法，由特里・韋爾奇在 1984 年創建。儘管存在嚴重的專利問題，但 LZW 是 LZ78 演算法家族中使用最廣泛的演算法。與 LZ78 類似，LZW 通過消除輸出中的冗餘字符並使輸出完全由指針構成來改進 LZ78。在開始壓縮之前，它還將字典中的每個字符包括在內，並採用其他技巧來提高壓縮效果，例如將每個新短語的最後一個字符編碼為下一個短語的第一個字符。LZW 通常出現在圖形交換格式 (GIF) 以及 ZIP 格式的早期規範和其他專用應用程序中。LZW 非常快，但與大多數新演算法相比，壓縮效果較差，而有些演算法既更快速，又可以實現更好的壓縮效果。

5.2.3 LZC#

LZC（Lempel-Ziv Compress）是對 UNIX 壓縮實用程序中使用的 LZW 演算法的輕微修改。LZC 和 LZW 之間的主要區別在於，LZC 監控輸出的壓縮比。一旦比率超過某個閾值，字典就被丟棄並重建。[19]

5.2.4 LZT#

Lempel-Ziv Tischer 演算法是 LZC 的一種改進，當詞典滿時，它會刪除最近最少使用的短語，並用新條目替換它。有一些其他的漸進式改進，但是 LZC 和 LZT 今天都不常用。

5.2.5 LZMW#

LZMW 演算法是由 Victor Miller 和 Mark Wegman 於 1984 年發明的，與 LZT 類似，採用最近未使用的短語替換策略。但是，LZMW 不是將字典中的相似條目合併，而是將最後兩個編碼的短語合併，並將結果存儲為新條目。因此，字典的大小可以迅速擴大，必須更頻繁地丟棄 LRUs。與 LZT 相比，LZMW 通常實現更好的壓縮，但它是另一個不太常見的演算法。[19]

5.2.6 LZAP#

LZAP 是由詹姆斯・斯托勒於 1988 年修改 LZMW 演算法創建的。AP 代表 “所有前綴”，即字典不僅存儲單個短語，而是存儲每個排列組合。例如，如果上個短語是 “last”，當前短語是 “next”，那麼字典將存儲 “lastn”、“lastne”、“lastnex” 和 “lastnext”。[30]

5.2.7 LZWL#

LZWL 是一個修改後的 LZW 演算法，於 2006 年創造，它使用音節而不是單個字符進行壓縮。LZWL 的設計旨在更好地處理具有許多常見音節的特定數據集，例如 XML 數據。通常，此類演算法與預處理器一起使用，將輸入數據分解為音節。

5.2.8 LZJ#

Matti Jakobsson 在 1985 年發布了 LZJ 演算法 [32]，它是唯一與 LZW 不同的 LZ78 演算法之一。該演算法通過在字典中存儲已處理的輸入中的每個唯一字符串（長度不超過一個任意的最大長度）並為每個字符串分配代碼來工作。當字典已滿時，將刪除僅出現一次的所有條目。[19]

5.3 Non-dictionary Algorithms#

5.3.1 PPM#

預測通過部分匹配是一種統計建模技術，它使用輸入中一組先前的符號來預測下一個符號，以減少輸出數據的熵。這與字典不同，因為 PPM 預測下一個符號，而不是嘗試在字典中找到下一個符號進行編碼。通常將 PPM 與編碼器結合使用，如算術編碼或自適應霍夫曼編碼。PPM 或其變體 PPMd 被實現在許多存檔格式中，包括 7-Zip 和 RAR。

5.3.2 bzip2#

bzip2 是 Burrows-Wheeler 變換的一個開源實現。它的工作原理非常簡單，但它們在速度和壓縮比之間取得了非常好的平衡，這使得 bzip2 格式在 UNIX 環境中非常受歡迎。首先，對數據應用運行長度編碼。接下來，應用 Burrows-Wheeler 變換。然後，應用移動到前面的變換，旨在創建大量形成運行的相同符號，以供另一個運行長度編碼器使用。最後，結果進行霍夫曼編碼並包裝在一個頭文件中。

5.3.3 PAQ#

PAQ 是由 Matt Mahoney 於 2002 年創建的，旨在改進舊的 PPM（d）演算法。它使用一種被稱為上下文混合的革命性技術，將多個統計模型（PPM 是其中之一）智能組合在一起，以比任何單個模型更好地預測下一個符號。PAQ 是最有前途的演算法之一，因為它具有極高的壓縮比和非常活躍的開發。自其誕生以來，已經創建了 20 多個變種，其中一些變種實現了創紀錄的壓縮比。 PAQ 最大的缺點是由於使用多個統計模型以獲得最佳壓縮比而導致速度緩慢。但是，隨著硬體不斷變得更快，它可能成為未來的標準。 PAQ 正在慢慢被採用，可在 Windows 上的 PeaZip 程序中找到帶有 64 位支持和主要速度改進的 PAQ8O 變體。其他 PAQ 格式大多是僅限命令行的。

6 References#

1. Wolfram, Stephen. A New Kind of Science. Champaign, IL: Wolfram Media, 2002. 1069. Print.

2. Ken Huffman. Profile: David A. Huffman, Scientific American, September 1991, pp. 54–58.

3. Ziv J., Lempel A., “A Universal Algorithm for Sequential Data Compression”, IEEE Transactions on Information Theory, Vol. 23, No. 3 (1977), pp. 337-343.

4. Ziv J., Lempel A., “Compression of Individual Sequences via Variable-Rate Coding”, IEEE Transactions on Information Theory, Vol. 24, No. 5, pp. 530-536.

5. USPTO Patent #4814746. See http://www.theregister.co.uk/1999/09/01/unisys_demands_5k_licence_fee

6. blog [Fedora & Linux Tips]

7. http://www.msversus.org/archive/stac.html

8. ARC Info

9. comp.compression Frequently Asked Questions (part 1/3)Section - [8] What about patents on data compression algorithms?

10. USPTO Patent #5051745

11. Phil Katz' Death

12. Iwata, K., Arimura, M., and Shima, Y., "An Improvement in Lossless Data Compression via Substring Enumeration", , 2011 IEEE/ACIS 10th International Conference on Computer and Information Science (ICIS).

13. Burrows M., and Wheeler, D. J. 1994. A Block-Sorting Lossless Data Compression Algorithm. SRC Research Report 124, Digital Systems Research Center.

14. http://www.cs.tau.ac.il/~dcor/Graphics/adv-slides/entropy.pdf

15. Shannon, C.E. (July 1948). "A Mathematical Theory of Communication". Bell System Technical Journal 27: 379–423.

16. HUFFMAN, D. A. 1952. A method for the construction of minimum-redundancy codes. In Proceedings of the Institute of Electrical and Radio Engineers 40, 9 (Sept.), pp. 1098-1101.

17. RISSANEN, J., AND LANGDON, G. G. 1979. Arithmetic coding. IBM J. Res. Dev. 23, 2 (Mar.), 149-162.

18. RODEH, M., PRATT, V. R., AND EVEN, S. 1981. Linear algorithm for data compression via string matching. J. ACM 28, 1 (Jan.), 16-24.

19. Bell, T., Witten, I., Cleary, J., "Modeling for Text Compression", ACM Computing Surveys, Vol. 21, No. 4 (1989).

20. DEFLATE64 benchmarks

21. STORER, J. A., AND SZYMANSKI, T. G. 1982. Data compression via textual substitution. J. ACM 29, 4 (Oct.), 928-951.

22. Bloom, C., "LZP: a new data compression algorithm", Data Compression Conference, 1996. DCC '96. Proceedings, p. 425 10.1109/DCC.1996.488353.

23. Dr Ross's Compression Crypt

24. "Data Compression Method - Adaptive Coding witih Sliding Window for Information Interchange", American National Standard for Information Systems, August 30, 1994.

25. LZX Sold to Microsoft

26. LZO Info

27. LZMA Accessed on 12/10/2011.

28. LZMA2 Release Date

29. Kwong, S., Ho, Y.F., "A Statistical Lempel-Ziv Compression Algorithm for Personal Digital Assistant (PDA)", IEEE Transactions on Consumer Electronics, Vol. 47, No. 1, February 2001, pp 154-162.

30. David Salomon, Data Compression – The complete reference, 4th ed., page 212

31. Chernik, K., Lansky, J., Galambos, L., "Syllable-based Compression for XML Documents", Dateso 2006, pp 21-31, ISBN 80-248-1025-5.

32. Jakobsson, M., "Compression of Character Strings by an Adaptive Dictionary", BIT Computer Science and Numerical Mathematics, Vol. 25 No. 4 (1985). doi>10.1007/BF01936138

33. Cleary, J., Witten, I., "Data Compression Using Adaptive Coding and Partial String Matching", IEEE Transactions on Communications, Vol. COM-32, No. 4, April 1984, pp 396-402.

34. Seward, J., "bzip2 and libbzip2", bzip2 Manual, March 2000.

35. Mahoney, M., "Adaptive Weighting of Context Models for Lossless Data Compression", Unknown, 2002.