霍夫曼演算法編碼

A. 哈夫曼編碼碼長怎麼算

設某信源產生有五種符號u1、u2、u3、u4和u5，對應概率P1=0.4，P2=0.1，P3=P4=0.2，P5=0.1。

霍夫曼編碼是變長編碼，思路：對概率大的編的碼字短，概率小的編的碼字長，這樣一來所編的總碼長就小，這樣編碼效率就高。上面那樣求是不對的，除非你這6個碼字是等概率的，各佔1/6。應該用對應的概率*其對應得碼長，再求和。

實際應用中

除採用定時清洗以消除誤差擴散和採用緩沖存儲以解決速率匹配以外，主要問題是解決小符號集合的統計匹配，例如黑（1）、白（0）傳真信源的統計匹配，採用0和1不同長度遊程組成擴大的符號集合信源。遊程，指相同碼元的長度（如二進碼中連續的一串0或一串1的長度或個數）。

按照CCITT標准，需要統計2×1728種遊程（長度），這樣，實現時的存儲量太大。事實上長遊程的概率很小，故CCITT還規定：若l表示遊程長度，則l=64q+r。

B. 霍夫曼演算法

霍夫曼演算法的步驟是這樣的：

·從各個節點中找出最小的兩個節點，給它們建一個父節點，值為這兩個節點之和。
·然後從節點序列中去除這兩個節點，加入它們的父節點到序列中。

重復上面兩個步驟，直到節點序列中只剩下唯一一個節點。這時一棵最優二叉樹就已經建成了，它的根就是剩下的這個節點。

仍以上面的例子來看霍夫曼樹的建立過程。
最初的節點序列是這樣的：
a(6) b(15) c(2) d(9) e(1)

把最小的c和e結合起來
| (3)
a(6) b(15) d(9) +------+------+
| |
c e

不斷重復，最終得到的樹是這樣的：

根
|
+-----33-----+
| |
15 +----18----+
| |
9 +------9-----+
| |
6 +--3--+
| |
2 1

這時各個字元的編碼長度和前面我們說過的方法得到的編碼長度是相同的，因而文件的總長度也是相同的： 3*6 + 1*15 + 4*2 + 2*9 + 4*1 = 63

考察霍夫曼樹的建立過程中的每一步的節點序列的變化：

6 15 2 9 1
6 15 9 3
15 9 9
15 18
33

下面我們用逆推法來證明對於各種不同的節點序列，用霍夫曼演算法建立起來的樹總是一棵最優二叉樹：

對霍夫曼樹的建立過程運用逆推法：
當這個過程中的節點序列只有兩個節點時（比如前例中的15和18），肯定是一棵最優二叉樹，一個編碼為0，另一個編碼為1，無法再進一步優化。
然後往前步進，節點序列中不斷地減少一個節點，增加兩個節點，在步進過程中將始終保持是一棵最優二叉樹，這是因為：
1.按照霍夫曼樹的建立過程，新增的兩個節點是當前節點序列中最小的兩個，其他的任何兩個節點的父節點都大於（或等於）這兩個節點的父節點，只要前一步是最優二叉樹，其他的任何兩個節點的父節點就一定都處在它們的父節點的上層或同層，所以這兩個節點一定處在當前二叉樹的最低一層。
2.這兩個新增的節點是最小的，所以無法和其他上層節點對換。符合我們前面說的最優二叉樹的第一個條件。
3.只要前一步是最優二叉樹，由於這兩個新增的節點是最小的，即使同層有其他節點，也無法和同層其他節點重新結合，產生比它們的父節點更小的上層節點來和同層的其他節點對換。它們的父節點小於其他節點的父節點，它們又小於其他所有節點，只要前一步符合最優二叉樹的第二個條件，到這一步仍將符合。

這樣一步步逆推下去，在這個過程中霍夫曼樹每一步都始終保持著是一棵最優二叉樹。

由於每一步都從節點序列中刪除兩個節點，新增一個節點，霍夫曼樹的建立過程共需 (原始節點數 - 1) 步，所以霍夫曼演算法不失為一種精巧的編碼式壓縮演算法。

附：對於 huffman 樹，《計算機程序設計藝術》中有完全不同的證明，大意是這樣的：
1．二叉編碼樹的內部節點（非葉子節點）數等於外部節點（葉子節點）數減1。
2．二叉編碼樹的外部節點的加權路徑長度（值乘以路徑長度）之和，等於所有內部節點值之和。（這兩條都可以通過對節點數運用數學歸納法來證明，留給大家做練習。）
3．對 huffman 樹的建立過程運用逆推，當只有一個內部節點時，肯定是一棵最優二叉樹。
4．往前步進，新增兩個最小的外部節點，它們結合在一起產生一個新的內部節點，當且僅當原先的內部節點集合是極小化的，加入這個新的內部節點後仍是極小化的。（因為最小的兩個節點結合在一起，並處於最低層，相對於它們分別和其他同層或上層節點結合在一起，至少不會增加加權路徑長度。）
5．隨著內部節點數逐個增加，內部節點集合總維持極小化。

2．實現部分
如果世界上從沒有一個壓縮程序，我們看了前面的壓縮原理，將有信心一定能作出一個可以壓縮大多數格式、內容的數據的程序，當我們著手要做這樣一個程序的時候，會發現有很多的難題需要我們去一個個解決，下面將逐個描述這些難題，並詳細分析 zip 演算法是如何解決這些難題的，其中很多問題帶有普遍意義，比如查找匹配，比如數組排序等等，這些都是說不盡的話題，讓我們深入其中，做一番思考。