C++算法之哈夫曼樹
在數據傳輸的過程當中，我們總是希望用盡可能少的帶寬傳輸更多的數據，哈夫曼就是其中的一種較少帶寬傳輸的方法。哈夫曼的基本思想不復雜，那就是對于出現頻率高的數據用短字節表示，對于頻率比較低得數據用長字節表示。 比如說，現在有4個數據需要傳輸，分別為A、B、C、D，所以一般來說，如果此時沒有考慮四個數據出現的概率，那么我們完全可以這么分配，平均長度為2，
/*
- A - 00 B - 01
- C - 10 D - 11 */
</pre> 但是，現在條件發生了改變，四個數據出現的頻率并不一樣，分別為0.1/0.2/0.3/0.4。那么這時候應該怎么分配長度呢，其實也簡單。我們只要把所有數據按照頻率從低到高排列，每次取前兩位合并成新的節點，再把這個新節點放到隊列中重新排序即可。新節點的左結點默認設為1，右結點默認設為0。然后重復上面的過程，直到所有的節點都合并成一個節點為止。如果應用到實際的示例中，合并的過程應該是這樣的，
第一步，首先合并A和B，因為A和B是概率最小的
/*
- total_1(0.3) C (0.3) D(0.4)
- / \
- A(0.1) B(0.2)
/
</pre> 第二步，接著合并total_1和C，/
- total_2 (0.6)
- / \
- total_1(0.3) C (0.3) D(0.4)
- / \
- A(0.1) B(0.2)
/
</pre> 最后一步，合并total_2和D，/
- final (1.0)
- / \
- D (0.4) total_2 (0.6)
- / \
- total_1(0.3) C (0.3)
- / \
- A(0.1) B(0.2) */
//該代碼片段來自于: http://www.sharejs.com/codes/cpp/6552</pre> 所以按照上面的生成樹，數據的編號應該這么安排，
/*
- A - 011 B - 010
- C - 00 D - 1
/
</pre> 看上去A和B的長度還增加了，但是D的長度減少了。那么整個數據的平均長度有沒有減少呢？我們可以計算一下。3 0.1 + 3 0.2 + 2 0.3 + 0.4 = 1.9 < 2。我們發現調整后的數據平均長度比原來減少了近（2 - 1.9）/2 100% = 10 %，這可是巨大的發現啊。
為了完成整個哈夫曼樹的創建，我們還需要定義一個數據結構：typedef struct _HUFFMAN_NODE
left;
{
char str;
double frequence;
int symbol;
struct _HUFFMAN_NODE
struct _HUFFMAN_NODE right;
struct _HUFFMAN_NODE parent;
}HUFFMAN_NODE;
//該代碼片段來自于: http://www.sharejs.com/codes/cpp/6552</pre> 其中str記錄字符，frequency記錄字符出現的頻率， symbol記錄分配的數據，左子樹為1、右子樹為0，left為左子樹，right為右子樹，parent為父節點。接下來，我們從創建huffman結點開始。
HUFFMAN_NODE create_new_node(char str, double frq)
{
HUFFMAN_NODE pNode = (HUFFMAN_NODE*)malloc(sizeof(HUFFMAN_NODE));
assert(NULL != pNode);pNode->str = str; pNode->frequence = frq; pNode->symbol = -1; pNode->left = NULL; pNode->right = NULL; pNode->parent = NULL; return pNode;}
</pre> 前面說到了哈夫曼樹的創建，那下面一個重要的環節就是哈夫曼樹的排序問題。但是由于排序的內容是數據結構，因此形式上說，我們需要采用通用數據排序算法，這在我之前的博客里面已經涉及到了（通用算法設計）。所以，我們所要做的就是編寫compare和swap兩個函數。通用冒泡代碼如下所示，
void bubble_sort(void array[], int length, int (compare)(void, void), void(*swap)(void, void))
{
int outer;
int inner;for(outer = length -1; outer >0; outer --){ for(inner = 0; inner < outer; inner ++){ if(compare(array[inner], array[inner + 1])) swap(&array[inner], &array[inner + 1]); } } return;}
</pre> compare和swap代碼如下所示，int compare (void a, void b)
{
HUFFMAN_NODE node1 = (HUFFMAN_NODE)a;
HUFFMAN_NODE node2 = (HUFFMAN_NODE)b;return node1->frequence > node2->frequence ? 1 : 0;}
void swap(void a, void b)
{
HUFFMAN_NODE* median;
HUFFMAN_NODE node1 = (HUFFMAN_NODE)a;
HUFFMAN_NODE node2 = (HUFFMAN_NODE)b;median = *node1; *node1 = *node2; *node2 = median;}
</pre> 有了創建函數和排序函數，那么哈夫曼樹就可以創建了，HUFFMAN_NODE create_huffman_tree(HUFFMAN_NODE huffmanNode[], int length)
{
HUFFMAN_NODE* head = NULL;if(NULL == huffmanNode || length <= 1) return NULL; while(length > 1){ bubble_sort((void**)huffmanNode, length, compare, swap); head = create_new_node('\0', huffmanNode[0]->frequence + huffmanNode[1]->frequence); assert(NULL != head); head->left = huffmanNode[0]; head->right = huffmanNode[1]; huffmanNode[0]->parent = head; huffmanNode[0]->symbol = 1; huffmanNode[1]->parent = head; huffmanNode[1]->symbol = 0; memmove(&huffmanNode[0], &huffmanNode[2], sizeof(HUFFMAN_NODE*) * (length -2)); huffmanNode[length -2] = head; length --; } return head;}
</pre> 上面的代碼完整了寫出了huffman樹的創建過程，那么我們怎么知道符號的編碼是多少呢？這其實不難，因為根節點都知道了，我們只要按照自下而上的順序遍歷節點就可以打印出編碼，只不過編碼是逆序的而已，void print_code_for_str(HUFFMAN_NODE pNode, HUFFMAN_NODE head)
{
if(NULL == pNode || NULL == head)
return;while(head != pNode){ printf("%d", pNode->symbol); pNode = pNode->parent; } return;}
</pre> 如果對代碼本身還有懷疑，可以編譯一個測試用例驗證一下，void test()
{
HUFFMAN_NODE node1 = NULL;
HUFFMAN_NODE node2 = NULL;
HUFFMAN_NODE node3 = NULL;
HUFFMAN_NODE node4 = NULL;HUFFMAN_NODE* test[] = {node1 = create_new_node('a', 0.1), node2 = create_new_node('b', 0.2), node3 = create_new_node('c', 0.3), node4 = create_new_node('d', 0.4), }; HUFFMAN_NODE* head = create_huffman_tree(test, sizeof(test)/sizeof(HUFFMAN_NODE*)); print_code_for_str(node1, head); print_code_for_str(node2, head); print_code_for_str(node3, head); print_code_for_str(node4, head);}
</pre>
總結：
（1）哈夫曼樹不復雜，如果手算可以成功，那么編程應該也沒有什么問題
（2）復雜算法都是由小算法搭積木而成的，朋友們應該在基本算法上打下堅實的基礎
（3）算法注意復用，這里就用到了原來講到的通用算法內容