三、哈夫曼編碼生成步驟：

① 掃描要壓縮的文件，對字符出現的頻率進行計算。

② 把字符按出現的頻率進行排序，組成一個隊列。

③ 把出現頻率最低（權值）的兩個字符作為葉子節點，它們的權值之和為根節點組成一棵樹。

④ 把上面葉子節點的兩個字符從隊列中移除，并把它們組成的根節點加入到隊列。

⑤ 把隊列重新進行排序。重復步驟 ③④⑤ 直到隊列中只有一個節點為止。

⑥ 把這棵樹上的根節點定義為 0 （可自行定義 0 或 1 ）左邊為 0 ，右邊為 1 。這樣就可以得到每個葉子節點的哈夫曼編碼了。

既如 (a) 、 (b) 、 (c) 、 (d) 幾個圖，就可以將離散型的數據轉化為樹型的了。

如果假設樹的左邊用0 表示右邊用 1 表示，則每一個數可以用一個 01 串表示出來。

則可以得到對應的編碼如下：

1-->110

2-->111

3-->10

4-->0

每一個01 串，既為每一個數字的哈弗曼編碼。

為什么能壓縮：

壓縮的時候當我們遇到了文本中的1 、 2 、 3 、 4 幾個字符的時候，我們不用原來的存儲，而是轉化為用它們的 01 串來存儲不久是能減小了空間占用了嗎。（什么 01 串不是比原來的字符還多了嗎？怎么減少？）大家應該知道的，計算機中我們存儲一個 int 型數據的時候一般式占用了 2^32-1 個 01 位，因為計算機中所有的數據都是最后轉化為二進制位去存儲的。所以，想想我們的編碼不就是只含有 0 和 1 嘛，因此我們就直接將編碼按照計算機的存儲規則用位的方法寫入進去就能實現壓縮了。

比如：

1這個數字，用整數寫進計算機硬盤去存儲，占用了 2^32-1 個二進制位

  而如果用它的哈弗曼編碼去存儲，只有110 三個二進制位。

效果顯而易見。

開始寫程序:

開始些程序之前，必須想好自己的文件存儲格式，和存儲規則是什么

為了簡便，我自定義存儲的基本信息，格式如下：

SaveCode[i].n    int型   // 每一個字節的編碼長度  i:0~256

B yte[]   byte數組型 // 每一個字節的編碼 SaveCode[i].node 中 String 的 01 串轉化而來。

 Byte[]  byte數組型 // 對文件中每一個 byte 的重新編碼的哈夫曼編碼寫入。

有了定義好的格式我們的讀寫就非常的方便了，

創建步驟：

①讀入文件中的所有字節：

②構建哈夫曼樹：

這里我采用了優先隊列的方法，因為優先隊列比較符合哈夫曼的構造方法，形式上也非常的相似。

③取得每一個葉子節點的哈夫曼編碼:

如此一來我們的哈夫曼樹就建好了。

下面就是按照我們之前定義的文件存儲格式直接寫進文件就可以了。

壓縮文件的寫入:

①  寫出0~256 每一個字節對應編碼的長度

② 寫出每一個字節所對應的編碼

這一步較為復雜，因為JAVA 中沒有自己定義的二進制為寫入，我們就不得不將每 8 個 01 String 轉化為一個byte 再將 byte 寫入。但是，問題又來了不是所有的 01String 都是 8 的整數倍，所以就又得在不是 8 整數倍的String 后面補上 0

③ 將源文件中的所有byte 轉化為 01 哈夫曼編碼，寫入壓縮文件

   這一步也比較復雜，原理同上一步，在SaveCode 中查找一個 byte 所對應的哈夫曼編碼，不夠 8 的整數倍的就不足，再寫入。

   值得注意的事，最后一定要寫一個byte 表示，補了多少個 0 方便解壓縮時的刪除 0

如此一來，整個的壓縮過程就完畢了。

解壓縮過程：

    與壓縮過程剛好是反著來進行的，知道的存儲的方式我們就反著來讀取看看。

①  讀入所有字節所對應的編碼長度：

② 讀入每一個字節所對應的編碼

③ 讀入文件的哈夫曼編碼

得注意的事，前面我們又補0 的位，所以在我們讀取的時候，記得把之前所補得東西，給刪除掉就 OK 了。

本次的文件讀寫比較復雜，之前些的時候遇到了很多的困難，參考了很多前輩的思路和代碼，今天終于完成了，我~內牛滿面