【資料結構與算法】哈夫曼樹與哈夫曼壓縮與解壓縮

哈夫曼樹與哈夫曼編碼

壓縮與解壓縮技術

       這裡提出一種專門針對ASCII碼（英文及英文标點）的壓縮技術：對文本檔案中的字元，按照出現頻度大小，将出現頻度最大的字元，用最少的二進制位表達（替換）；

       比如：假設某檔案中，字母e出現了304325次，每一個e都應該是一個ASCII碼，即，占用8bit；若能用2個bit的資訊替換，則，可以省304325bit * (8-2) = 228243Byte        304325 * 2 / 8 = 76082         76081 / 304325 = 0.25

       假設，有如下字元及其出現頻度：

       a        2

       b        8

       c        1

       d        7

       e        20

       f        3

那麼我們就可以形成一棵哈夫曼樹，如下圖所示：

        其形成的原理是：先找出兩個出現頻度最小的，作為左右孩子，然後将兩者頻度之和作為根節點；再找出頻度第三小的，作為左孩子，與剛才的根節點形成左右孩子，依此類推，形成一棵哈夫曼樹。令：向左為0；向右為1，從根出發，到達某一個葉子節點的0、1集合，就是那個葉子節點所表示的字元對應的哈夫曼編碼。

e：0

b：10

d：110

f：1110

c：11110

a：11111

而哈夫曼壓縮與解壓縮要解決的第一個問題就是：統計給定字元串（檔案）中出現的字元種類及其頻度。

哈夫曼壓縮與解壓縮

1.針對檔案進行壓縮和解壓縮；即，輸入是檔案，輸出也是檔案；

2.針對檔案進行操作：

       2.1統計該檔案中出現的不同位元組（應該隻能使用：unsigned char 類型！！！）及其頻度；

       2.2根據上述統計資料，構造哈夫曼樹；

       2.3根據上述哈夫曼樹，構造每一個位元組的哈夫曼編碼；

       2.4将檔案中的位元組，轉換成哈夫曼編碼；

3.将由哈夫曼編碼形成的最終壓縮檔案作為輸出。

綜上，結構體應定義為：

typedef struct TREE{
	char ch;
	int freq;
	struct TREE *leftChild;
	struct TREE *rightChild;
}TREE;
           

其實大緻思路就是這樣，其中最關鍵的就是，先形成一個表，再由表形成樹，具體怎麼實作，還是直接上代碼吧！！！

github：https://github.com/xiami-maker/aboutHuffman/tree/master

感悟：對于哈夫曼壓縮和解壓縮，主要是對于哈夫曼樹的應用，還有一些思想：把壓縮和解壓縮過程做成工具以便代碼複用，友善閱讀，減少程式設計量，采用檔案的形式來存放更具有實際意義等。需要讀者浏覽代碼的過程中，自行體會。