一、背景
編碼是資訊處理的基礎（重新表示資訊）， 普通的編碼是等長編碼，例如7位的ASCIL編碼，對出現頻率不同的字符都使用相同的編碼長度，但其在傳輸和存盤等情況下編碼效率不高， 可使用不等長編碼，來壓縮編碼：高頻字符編碼長度更短，低頻字符編碼長度更長， [例] 將百分制的考試成績轉換成五分制的成績
按順序分別編碼，
按頻率分別編碼（高頻短編碼，類似于香農熵衡量隨機變數的編碼長度下界），
這種貪心思想，可以找到一種平均最短編碼長度-霍夫曼編碼，可將構造平均最短編碼轉化為，構造平均查找長度最小的編碼樹（構造更有效的搜索樹）
二、哈夫曼樹
哈夫曼樹的定義
帶權路徑長度就是所有葉子節點的編碼長度乘以權重的和， 希望權重越高的葉子節點，編碼長度越小，
[例] 有五個葉子結點，它們的權值為{1,2,3,4,5}，用此權值序列可以構造出形狀不同的多個二叉樹，
哈夫曼樹的構造
初始全是只有一個節點的樹構成的森林 （優先佇列存放樹的根節點，每次合并后將新的樹插入佇列）
每次把權值最小的兩棵二叉樹合并 （自底向上）
使用最小堆，Huffman樹為二叉樹
typedef struct TreeNode *HuffmanTree;
struct TreeNode{
int Weight;
HuffmanTree Left, Right;
};
/* WPL WeightPathLength Cost越小編碼越有效， O(NlogN) */
HuffmanTree Huffman( MinHeap H )
{
/* 假設H->Size個權值已經存在H->Elements[]->Weight里 */
int i;
HuffmanTree T;
BuildMinHeap(H); /* 將H->Elements[]按權值調整為最小堆 */
/* 做 H->Size - 1 次合并 */
for (i = 1; i < H->Size; i++)
{
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;
int WPL( HuffmanTree H )
{
return H->Weight;
}
哈夫曼樹的特點
- 沒有度為1的結點；
- 哈夫曼樹的任意非葉節點的左右子樹交換后仍是哈夫曼樹；
- n個葉子結點的哈夫曼樹共有2n-1個結點；
哈夫曼編碼
給定一段字串，如何對字符進行編碼，使得該字串的編碼存盤空間最少？
[例] 假設有一段文本，包含58個字符，并由以下7個字符構：a，e，i， s，t，空格（sp），換行（nl）；這7個字符出現的次數不同，如何對這7個字符進行編碼，使得總編碼空間最少？
[分析]
（1）用等長ASCII編碼：58 ×8 = 464位；
（2）用等長3位編碼：58 ×3 = 174位；
（3）不等長編碼：出現頻率高的字符用的編碼短些，出現頻率低的字符則可以編碼長些？
怎么進行不等長編碼？如何避免二義性？
- 前綴碼prefix code：任何字符的編碼，都不是另一字符編碼的前綴
〖例〗哈夫曼編碼
題外話，這種使用優先佇列的方法，在層次聚類里也有，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/550212.html
標籤：其他
上一篇：期望最大化演算法（EM）簡介