基于Huffman和LZ77的檔案壓縮（一）Huffman壓縮

點我擷取代碼

1 壓縮的優點

1 節省空間

2 提高檔案在網絡上的傳輸效率

3 壓縮可以形成一定程度上的加密。

2 檔案壓縮的分類

1 有損壓縮

2 無損壓縮

無損壓縮： 通過解壓之後 能形成和源代碼一木一樣的壓縮方式。

有損： 解壓縮之後和源檔案格式不完全相同，但基本不影響。例如 視訊的清晰度。

先大概了解

LZ77  基于語句 ，用<長度，距離, 下一個字元> 替換重複出現的語句
           

**LZ77的變形 **:原理：将重複多次出現的語句用盡可能短的标記來替換。

eg :asdfghjkl1234asdfgh0

asdfghjkl1234(連着重複出現的個數，目前位置向前數距離)0

LZ77消除了檔案中重複出現的語句，但還存在位元組之間的重複 ，是以再用哈夫曼編碼壓縮一次。

Huffman壓縮

哈夫曼編碼

哈夫曼編碼是可變字長編碼，該方法完全依據字元出現機率來構造異字頭的平均長度最短的碼字

Huffman壓縮：基于位元組

1 個位元組 == 8個比特位，如果對每個位元組都能找到更好的改寫方法改寫原資料，就可以達到壓縮的目的。

舉個栗子🌰：

檔案 ：ABBBCCCCCDDDDDDD

提供這樣的哈夫曼編碼

eg： A： 00

B： 01

C： 10

D： 11

來一組字元串 ，就會進行相應的替換。大大節省空間

這種Huffman壓縮之後，大小原來的1/4

還存在不等長編碼：

A： 100

B：101

C：11

D：0

這樣的話，D出現次數處越多，壓縮的效果就越好。

如果将C的編碼改成10，那麼就成了A 或B的編碼字首，壓縮時不會出現問題，但解壓縮可能會出問題，遇見10 就不知道怎麼解析。

ABBBCCCCCDDDDDDD

什麼是huffman哈夫曼樹

帶權路徑最小的二叉樹為哈夫曼樹

帶權路徑長度WPL：

WPL = 所有葉子的權 * 根到該葉子的路徑長度 之和

Hffman壓縮四部曲：

1 ： 統計每個字元出現的次數

2 : 建立哈夫曼樹：

3 ：擷取字元的編碼（二進制串）

4 : 用編碼改寫源檔案

核心：Huffman 樹的建構

1 提供一組字元權值（出現的次數）

2 以每個權值為節點，建立n顆隻有根節點的二叉樹的森林

3 如果森林超過兩棵樹 ，進行以下操作：

a: 從森林中每次取出兩顆根節點權值最小的二叉樹

b：以這兩顆二叉樹作為某個節點的左右子樹，建立出一顆新的二叉樹，新二叉樹權值為左右子樹權值之和。

c: 将新建立的二叉樹插入到森林中，直到二叉樹森林中隻剩一棵樹。

點我繼續閱讀