2018-03-02 15:03:37
編碼問題是計算機科學乃至EE中的一個核心的問題，最基礎的編碼方式是采用等長的編碼，比如計算機中的字元的編碼就是采用等長的8位，即一個位元組進行的編碼。
但是在實際生活中，每個字元出現的頻率是不同的，是以，如果我們采用不等長編碼，将出現頻率高的字元采用較短的編碼，對出現頻率低的字元采用較長的編碼，就可以實作更高效和節省的編碼。
一、哈夫曼樹
霍夫曼樹又稱最優二叉樹，是一種帶權路徑長度最短的二叉樹。所謂樹的帶權路徑長度，就是樹中所有的葉結點的權值乘上其到根結點的路徑長度（若根結點為0層，葉結點到根結點的路徑長度為葉結點的層數）。樹的路徑長度是從樹根到每一結點的路徑長度之和，記為WPL=（W1*L1+W2*L2+W3*L3+...+Wn*Ln），N個權值Wi（i=1,2,...n）構成一棵有N個葉結點的二叉樹，相應的葉結點的路徑長度為Li（i=1,2,...n）。可以證明霍夫曼樹的WPL是最小的。
1951年，霍夫曼和他在MIT資訊論的同學得選擇是完成學期報告還是期末考試。導師羅伯特·法諾出的學期報告題目是，查找最有效的二進制編碼。由于無法證明哪個已有編碼是最有效的，霍夫曼放棄對已有編碼的研究，轉向新的探索，最終發現了基于有序頻率二叉樹編碼的想法，并很快證明了這個方法是最有效的。霍夫曼使用自底向上的方法建構二叉樹，避免了次優算法香農-範諾編碼的最大弊端──自頂向下建構樹。
算法流程：
假設有n個權值，則構造出的哈夫曼樹有n個葉子結點。 n個權值分别設為 w1、w2、…、wn，則哈夫曼樹的構造規則為：
(1) 将w1、w2、…，wn看成是有n 棵樹的森林(每棵樹僅有一個結點)；
(2) 在森林中選出兩個根結點的權值最小的樹合并，作為一棵新樹的左、右子樹，且新樹的根結點權值為其左、右子樹根結點權值之和；
(3)從森林中删除選取的兩棵樹，并将新樹加入森林；
(4)重複(2)、(3)步，直到森林中隻剩一棵樹為止，該樹即為所求得的哈夫曼樹。
typedef struct TreeNode *HuffmanTree;
struct TreeNode{
int Weight;
HuffmanTree Left, Right;
}
HuffmanTree Huffman( MinHeap H )
{ /* 假設H->Size 個權值已經存在H->Elements[]->Weight 裡 */
int i; HuffmanTree T;
BuildMinHeap(H); /* 将H->Elements[] 按權值調整為最小堆*/
for (i = 1; i < H->Size; i++) { /* 做H->Size-1 次合并*/
T = malloc( sizeof( struct TreeNode) ); /* 建立新結點*/
T->Left = DeleteMin(H);
/* 從最小堆中删除一個結點 ， 作為新T 的左子結點*/
T->Right = DeleteMin(H);
/* 從最小堆中删除一個結點 ， 作為新T 的右子結點*/
T->Weight = T->Left->Weight+T->Right->Weight;
/* 計算新權值*/
Insert( H, T ); /* 将新T 插入最小堆*/
}
T = DeleteMin(H);
return T;
}
二、哈夫曼編碼
問題：給定一段字元串，如何對字元進行編碼 ，可以使得該字元串的編碼存儲空間最少？
【例】假設有一段文本，包含58 個字元，并由以下7 個字元構：a ，e ，i， s ，t ，空格（sp），換行（nl）；這7個字元出現的次數不同。如何對這7個字元進行編碼，使得總編碼空間最少？
【分析】
（1）用等長ASCII 編碼：58 ×8 = 464 位；
（2）用等長3 位編碼：58 ×3 = 174 位；
（3）不等長編碼：出現頻率高的字元用的編碼短些 ，出現頻率低的字元則可以用較長的編碼進行表示。
采用不定長編碼編碼最本初的問題就是如何避免二義性，在解釋一段編碼的時候如果有多于一種的解釋，顯然這種編碼就是不可靠的。
經過證明隻要任何字元的編碼都不是另一字元編碼的字首，就可以避免二義性。