基于Huffman算法和LZ77算法的文件壓縮(一)

1. 數據壓縮的概念

數據壓縮是指 在不丟失有用信息的前提下，縮減數據量以減少存儲空間，提高其傳輸、存儲和處理效率，或按照一定的算法對數據進行重新組織，減少數據的冗余和存儲的空間 的一種技術方法

2. 為什么需要壓縮

緊縮數據存儲容量，減少存儲空間

可以提高數據傳輸的速度，減少帶寬占用量，提高通訊效率

對數據的一種加密保護，增強數據在傳輸過程中的安全性

3. 壓縮的分類

有損壓縮

有損壓縮是利用了人類對圖像或聲波中的某些頻率成分不敏感的特性，允許壓縮過程中損失一定的信息；雖然不能完全恢復原始數據，但是所損失的部分對理解原始圖像的影響縮小，卻換來了大得多的壓縮比，即指使用壓縮后的數據進行重構，重構后的數據與原來的數據有所不同，但不影響人對原始資料表達的信息造成誤解。

無損壓縮

對文件中數據按照特定的編碼格式進行重新組織，壓縮后的壓縮文件可以被還原成與源文件完全相同的格式，不會影響文件內容，對于數碼圖像而言，不會使圖像細節有任何損失

4. ZIP壓縮的歷史

1977年，兩位以色列人Jacob Ziv和Abraham Lempel，發表了一篇論文《A Universal Algorithm forSequential Data Compression》，一種通用的數據壓縮算法，所謂通用壓縮算法指的是這種壓縮算法沒有對數據的類型有什么限定，該算法奠基了今天大多數無損數據壓縮的核心，為了紀念兩位科學家，該算法被尊稱為LZ77，過了一年他們又提了一個類似的算法，稱為LZ78。ZIP這個算法就是基于LZ77的思想演變過來的，但ZIP對LZ77編碼之后的結果又繼續進行壓縮，直到難以壓縮為止。在LZ77、LZ78基礎上變種的算法很多，基本都以LZ開頭，如LZW、LZO、LZMA、LZSS、LZR、LZB、LZH、LZC、LZT、LZMW、LZJ、LZFG等等。

ZIP的作者是Phil Katz，

他算是開源界的一個具有悲劇色彩的傳奇人物。Phil Katz是個牛逼程序員，成名于DOS時代，那個時代網速很慢，Phil
Katz上網的時候還不到1990年，WWW實際上就沒出現，瀏覽器當然是沒有的，當時上網干嘛呢？基本就是類似于網管敲各種命令，這樣實際上也可以聊天、上論壇，傳個文件不
壓縮的話肯定死慢死慢的，所以壓縮在那個時代很重要。當時有個商業公司提供了一種稱為ARC的壓縮軟件，可以讓你在那個時代聊天更快，但是要付費，Phil
Katz就感覺到不爽，于是寫了一個PKARC壓縮工具，不僅免費，而且兼容ARC，于是網友都用PKARC了，ARC那個公司自然就不爽，把Phil
katz告上了法庭，說牽涉了知識產權等等，結果Phil Katz坐牢了。牛人就是牛人，
在牢里面冥思苦想，決定整一個超越ARC的牛逼算法出來，牢里面就是適合思考，用了兩周就整出來的，稱為PKZIP，不僅免費，而且這次還開源了，直接公布源代碼，因為算法都不一樣了，也就不涉及到知識產權了，于是ZIP流行開來，不過Phil
Katz這個人沒有從里面賺到一分錢，還是窮困潦倒，因為喝酒過多等眾多原因，2000年的時候死在一個汽車旅館里。英雄逝去，精神永存，現在我們用UE打開ZIP文件，我們能看到開頭的兩個字節就是PK兩個字符的ASCII碼

5. GZIP壓縮算法的原理

GZIP壓縮算法經歷了兩個階段，第一個階段使用改進的LZ77壓縮算法對上下文中的重復語句進行壓縮，第二階段，采用huffman編碼思想對第一階段壓縮完成的數據進行字節上的壓縮，從而實現對數據的高效壓縮存儲。

5.1 LZ77壓縮算法

LZ77是一種基于字典的算法，它將長字符串（也稱為短語）編碼成短小的標記，用小標記代替字典中的短 語，從而達到壓縮的目的。

LZ77使用的是一個前向緩沖區和一個滑動窗口來維護字典。它首先將一部分數據載入前向緩沖區,一旦數據中的短語通過前向緩沖區，那么它將移動到滑動窗口中，并變成字典的一部分，隨著滑動窗口的移動，字典中 的內容也在不斷的更新，也就是說它是變更新字典，邊進行壓縮。

假設字典已經建立，每讀到一個字符，就向前掃描，在字典中查看是否有重復出現的短語，若搜索出有重復 出現的短語，將其編碼成短語標記。短語標記由三部分組成：滑動窗口中的偏移量（從頭部到匹配開始的前 一個字符）、匹配中的符號個數、匹配結束后前向緩沖區中的第一個符號—(o?set, lenght, nextChar)。

當沒有找到匹配時，將未匹配的符號編碼成符號標記。這個符號標記僅僅包含符號本身，沒有壓縮過程。一 旦把n個符號編碼并生成相應的標記，就將這n個符號從滑動窗口的一端移出，并用前向緩沖區中同樣數量的 符號來代替它們。然后，重新填充前向緩沖區。

下圖展示了LZ77的壓縮過程，假設滑動窗口大小為8個字節，前向緩沖區大小為4個字節：

當解碼每個標記時，將標記編碼成字符拷貝到滑動窗口中。每當遇到一個短語標記時，就在滑動窗口中查找 相應的偏移量，同時查找在那里發現的指定長度的短語。每當遇到一個符號標記時，就生成標記中保存的一 個符號:

5.2 GZIP 中的LZ77思想

在GZIP算法中，也使用到LZ77的算法思想，但是對其進行了改進，主要是對于短語標記的改進：只使用“長 度+距離”的二元組進行表示，匹配的查找是在查找緩沖區中進行的，即字典。

注意：查找緩沖區的數據是已經被掃描過，建立的字典中的數據，先行緩沖區即為帶壓縮數據

當前先行緩沖區第一個字節就是字符“r”，要做的就是找到以“r”為起始字符，在先行緩沖區中由連續字符組成 的字符串在查找緩沖區中的最長匹配。例如，“re”在綠色部分中有，“re （這里有個空格）”在綠色部分中也 有，但是后者比前者多一個字符，所以就選后者。

現在有四個問題需要處理：

從“r”開始，先行緩沖區中的字符串由幾個字符構成？有什么規定嗎？還是說只要能找到匹配，不管幾個 字符都行？

如何高效的在查找緩沖區中找到匹配串？

如何找到最長匹配？

找不到匹配怎么辦？

5.2.1 匹配串中由幾個字符構成？

如果對單個字符用長度距離對兒替換，那還不如不替換

如果對兩個連續字符用長度距離對兒替換，那是否替換又有什么關系，反正替換前后都要用兩個數（字 符其實也是個數）

能夠替換的前提就是字符串至少要由3個位于先行緩沖區中的連續字符組成，而且還必須以先行緩沖區 中第一個字節為開始

因此：先行緩沖區中的字符串最少要由3個連續的字符構成。 也就是說，當先行緩沖區中的字符串至少由3個 連續的字符組成并且在查找緩沖區中找到了匹配，此時先行緩沖區中的這個字符串才能用“長度+距離”對兒替 換。

5.2.2 如何高效的查找匹配串

一個字符串必須至少由三個連續字符組成，此時該字符串才有資格在查找緩沖區中尋找匹配串。壓縮使用字 典(哈希表)來提高查找速度。在壓縮中，“字典”由一整塊連續的內存構成，該內存大小為64KB，分成兩部 分，每部分大小為一個WSIZE，如下圖所示

指針head = prev + WSIZE，prev指向該字典整個內存的起始位置。既然內存是連續的，所以prev和head可 以看作兩個數組，即prev[]和head[]。

壓縮就是利用這三個連續字符來計算哈希值，這個哈希值就是head[]數組的索引。 三個字符不同，排列的次 序不同，計算出的哈希值就不同，總共有 2^24 種結果，而哈希值的范圍是：[0, 32767] (head數組的大小為 32K)，因此不能做到每個哈希值對應一種字符串，肯定會存在沖突，而prev就是來解決沖突的，而且該數組 還可以幫助找到最長匹配串。

字典構建

所謂構建字典，就是將字符串插入到字典中，壓縮是逐字節進行的，每處理一個字節，查找緩沖區擴大 一個字節(如果已經達到32KB，那就沿著先行緩沖區的方向滑動一個字節)，先行緩沖區縮小一個字節， 先行緩沖區的第一個字符在不斷的變化。每次先行緩沖區的第一個字節改變的時候，就要用“由當前的 先行緩沖區第一個字節開始，在先行緩沖區中連續的三個字節”組成的字符串來計算哈希值ins_h，該哈 希值是數組head[]的索引，所以用head[ins_h]來記錄該字符串的出現位置，該字符串的出現位置就是 這個字符串第一個字符（也就是當前先行緩沖區第一個字節）在當前window中的位置，這就是把字符 串插入字典的過程。

查找匹配串

注意：將字符串插入字典，實際是將字符串的起始位置插入到字典中，哈希只是得到一次初步匹配，用 于找到符合這種初步匹配的位置，利用這個位置找到更長的匹配才是目的。

5.2.3 如何找到最長匹配

插入時字典沖突怎么辦？

插入過程就是用head[ins_h]來記錄當前字符串的出現位置，ins_h是當前字符串的哈希值，head[]數組 的索引。如果將當前字符串的出現位置插到某個head[ins_h]的時候，head[ins_h]不為空怎么辦？比 如：

假設：strstart是先行緩沖區第一個字符在window中的位置，數組元素prev[strstart]是前一個字符串 的位置。插入按照以下方式進行：

注意：strstart逐漸增大，所以能夠保證每次對prev[strstart]賦值的時候不會把舊的內容覆蓋掉，每 次賦值之前，prev[strstart]一定都是全新的。

這樣就形成了一種“鏈式”關系，這種鏈式關系通過prev[]數組的索引和數組元素值將同一哈希值但是位 置不同的字符串鏈在了一起。

注意：壓縮之前會把head[]數組全部初始化為0，但是不會初始化prev[]數組。prev[]數組的初始化會 動態進行。因此，head[x]和prev[x]使用0作為“空”，即沒有匹配串的標志，他倆的值的本身的含義是 字符串的位置，但window的第0個字符組成的字符串位置也是0，這就產生歧義了，該歧義的解決方法 非常簡單粗暴，就是干脆不讓window中的首個字符串參與匹配過程。

先行緩沖區第一個字符位置大于32K怎么辦？

隨著壓縮的逐字節進行，先行緩沖區的第一個字符strstart在不斷推進(增大)，勢必會大于32K(因為滑動 窗口的大小為64K)，當strstart超過32K時，直接用其作用prev數組的下標就會出錯。源碼的解決辦法 是：讓strstart與WMASK按位與運算的結果作prev[]的索引，而不是直接用strstart作prev[]的索引， 其中，WMASK的值是十進制的32768，即，prev[strstart & WMASK]。這樣就保證了在strstart的取值 范圍內，prev[]的索引與strstart都是完全對應的。

匹配鏈造成死循環怎么辦？ 當strstart大于32K的時候，匹配鏈有可能出現死循環。

源碼使用max_chain_length(表示最大鏈長度256)解決該問題，表示在順著匹配鏈查找時，最多查找的 個數。max_chain_length值越小，搜索的匹配節點越少，壓縮速度越快，但是壓縮率可能會相對低一 些。

懶匹配 源碼使用兩種方式找最長匹配：懶匹配和long_match。

懶惰匹配針對不同字符串找最長匹配，而longest_match找當前字符串的最長匹配。

所謂懶惰匹配就是，雖然當前字符串找到了最適合自己的那個匹配串，但是并不急于讓長度距離對兒將 其替換，而是用兩個變量prev_length和prev_match分別將匹配長度和匹配位置記錄下來。

然后讓 strstart往先行緩沖區方向挪動一個字符，現在strstart到了新的位置，當前串更新。此時再找最適合當 前串的匹配串。假設找到了最適合當前串的匹配串，得到了匹配位置以及匹配長度，此時就是懶惰匹配 大顯身手的時候了。用當前匹配串的匹配長度和prev_length做比較，如果前者大于后者，則用前者將 后者更新，同時用當前的匹配位置更新prev_match，而（當前strstart – 1）位置處的那個字符就作為 一個未匹配字符來處理，當prev_length和prev_match完成更新后，strstart再往先行緩沖區的方向挪 動一個字符并繼續進行同樣的處理，這種處理方式就是懶惰匹配；

如果前者小于后者，即上次的匹配長 度（prev_length）大于這次的，那么懶惰匹配停止，并用上次的匹配長度和匹配位置組成長度距離對兒二元組完成替換。

懶惰匹配停止之后，將prev_length和prev_match初始化，將strstart挪到新的位置（被替換字符串之外），準備開始新一輪的懶惰匹配過程。注意，被替換字符串中每一個字符所組成的 字符串仍然要插入字典。

5. longest_match

longest_match就是遍歷匹配鏈，在匹配鏈中找最長子串，當然該最長子串不一定是最優的，需要結合 懶匹配才能找到最優。

注意：

匹配節點的遍歷不是無限進行的，有一個最大匹配鏈節點個數限制

匹配串的匹配長度也不是無限的，一個匹配串的最大匹配長度為MAX_MATCH(258)

匹配距離不是無限的，匹配距離不能超過MAX_DIST

最長匹配串的獲得由longest_match和懶惰匹配共同完成。前者負責找到當前strstart的最長匹配，后者 負責在連續幾個strstart的最長匹配中找到匹配串長度最長的那個作為最終的、真正的最長匹配。

5.2.4 找不到最長匹配怎么辦?

對于壓縮結果中為匹配的字符串，或者距離對與源字符如何區分？比如：

注意：實際在壓縮字符串中距離對是沒有擴招的。那么問題來了：23不是距離對，是源字符，而12,16代表 距離對，那如何區分呢？
解決方式：用1個比特位來進行標記，比如1代表距離對，0代表源字符。

5.2.5 解壓縮

在解壓縮時，一個一個字節進行解析：

如果當前字節最高位是0，代表源字節，直接寫入文件

如果當前字節最高位是1，代表距離對，取出距離對，然后按照距離對的匹配起始位置以及長度解析出 有效字符串。

5.3 GZIP中哈夫曼思想

通過前面LZ77變形思想對源數據進行語句的重復壓縮之后，語句層面的重復性已經解決，但并不代表壓縮效 果已經達到最佳，字節層面可能也有大量重復的。

比如：“BCDCDDBDDCADCBDC”

一個字節占8個比特位，那如果能對所有字節找到小于8個比特位的編碼，然后用找到的編碼對源文件中對應 字節重新進行改寫，也可以讓源文件更小。那如何找編碼呢？

5.3.1 靜態等長編碼 每個字符的編碼長度都相等，比如：

用等長編碼對上述源數據進行壓縮：01101110 11110111 11100011 10011110，壓縮完成后的結果只占4個 字節，壓縮率還是比較高的。

5.3.2 動態不等長編碼 每個字符的編碼根據具體的字符情況來確定，比如：

使用不等長編碼對源數據進行壓縮：10111011 00101001 11000111 01011 壓縮完成后最后一個字節沒有用完，還剩余3個比特位，顯然動態不等長編碼比等長編碼壓縮率能好點。 那動態不等長編碼如何獲取到呢？

5.3.3hu?man編碼

1.ha?man樹

從二叉樹的根結點到二叉樹中所有葉結點的路徑長度與相應權值的乘積之和為該二叉樹的帶權路徑長度WPL。

上述四棵樹的帶權路徑長度分別為：

• WPLa = 1 * 2 + 3 * 2 + 5 * 2 + 7 * 2 = 32
• WPLb = 1 * 2 + 3 * 3 + 5 * 3 + 7 * 1 = 33
• WPLc = 7 * 3 + 5 * 3 + 3 * 2 + 1 * 1 = 43
• WPLd = 1 * 3 + 3 * 3 + 5 * 2 + 7 * 1 = 29
  把帶權路徑最小的二叉樹稱為Hu?man樹

2.hu?man樹構建

由給定的n個權值{ w1, w2, w3, … , wn}構造n棵只有根節點的二叉樹森林F={T1, T2 , T3, … ,Tn},每棵二叉樹Ti只有一個帶權值wi的根節點，左右孩子均為空。

重復以下步驟，直到F中只剩下一棵樹為止

• 在F中選取兩棵根節點權值最小的二叉樹，作為左右子樹構造一棵新的二叉樹,新二叉樹根節 點的權值為其左右子樹根節點的權值之和
• 在F中刪除這兩棵二叉樹
• 把新的二叉樹加入到F中

3.獲取ha?man編碼

5.3.4 利用hu?man編碼對源文件進行壓縮

統計源文件中每個字符出現的次數

以字符出現的次數為權值創建hu?man樹

通過hu?man樹獲取每個字符對應的hu?man編碼

讀取源文件，對源文件中的每個字符使用獲取的hu?man編碼進行改寫，將改寫結果寫到壓縮文件中， 直到文件結束。

5.3.4 壓縮文件格式

壓縮文件中只保存壓縮之后的數據可以嗎？

答案是不行的，因為在解壓縮時，沒有辦法進行解壓縮。比如：10111011 00101001 11000111 01011，只 有壓縮數據是沒辦法進行解壓縮的，因此壓縮文件中除了要保存壓縮數據，還必須保存解壓縮需要用到的信 息：

源文件的后綴

字符次數對的總行數

字符以及字符出現次數(為簡單期間，每個字符放置一行)

壓縮數據

5.3.5 解壓縮

從壓縮文件中獲取源文件的后綴

從壓縮文件中獲取字符次數的總行數

獲取每個字符出現的次數

重建hu?man樹

解壓縮

從壓縮文件中一個一個字節的獲取壓縮數據，每獲取到一個字節的壓縮數據，從根節點開始，按照該字 節的二進制比特位信息遍歷hu?man樹，該比特位是0，取當前節點的左孩子，否則取右孩子，直到遍 歷到葉子節點位置，該字符就被解析成功。繼續此過程，直到所有的數據解析完畢。

總結

以上是生活随笔為你收集整理的文件压缩项目铺垫的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。