一. 霍夫曼编码和霍夫曼树

霍夫曼编码: 霍夫曼编码使用变长编码表对源符号（如文件中的一个字母）进行编码，其中变长编码表是通过一种评估来源符号出现机率的方法得到的，出现机率高的字母使用较短的编码，反之出现机率低的则使用较长的编码，这便使编码之后的字符串的平均长度、期望值降低，从而达到无损压缩数据的目的。

霍夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度（若根结点为0层，叶结点到根结点的路径长度为叶结点的层数）。树的路径长度是从树根到每一结点的路径长度之和，记为WPL=（W1*L1+W2*L2+W3*L3+...+Wn*Ln），N个权值Wi（i=1,2,...n）构成一棵有N个叶结点的二叉树，相应的叶结点的路径长度为Li（i=1,2,...n）。可以证明霍夫曼树的WPL是最小的。

对霍夫曼编码问题的广义定义是:

Input: 一组符号（Symbol）和其对应的权重值（weight），其权重通常表示成概率或频率.

Output: 一组二元的前置码，其二元码的长度为最短。

二. 编码过程

1. 由节点森林创建霍夫曼树:

    1) 把n个终端节点加入优先队列，则n个节点都有一个优先权Pi，1 ≤ i ≤ n   

    2) 如果队列内的节点数>1，则：

a.从队列中移除两个最大的Pi节点，即连续做两次remove（max(Pi）, Priority_Queue)

b.产生一个新节点，此节点为a所移除节点的父节点，而此节点的权重值为两节点之权重和

(在具体实现的时候应该确定左右孩子的大小关系,使生成的霍夫曼树是唯一的, 以方便解码)

c.把b产生的节点加入优先队列中

    3) 最后在优先队列里的点为树的根节点（root）

2. 由霍夫曼树生成霍夫曼编码:

    1) 将霍夫曼树的左链接标记为0, 右链接标记为1

    2) 从根结点到叶节点. 记录走过的路径标记, 即为叶节点所代表字符的霍夫曼编码.

三. 完整的实现代码

  1: #include <iostream>
  2: #include <hash_map>
  3: #include <queue>
  4: #include <set>
  5: #include <list>
  6: using namespace std;
  7: 
  8: struct Node
  9: {
 10: 	char symbol;
 11: 	int weight;
 12: 	Node* left;
 13: 	Node* right;
 14: 	Node(int w = 0, char s = ‘\0‘) :symbol(s), weight(w), left(0), right(0){}
 15: };
 16: 
 17: struct Node_comparator
 18: {
 19: 	bool operator()(const Node* a, const Node* b)
 20: 	{
 21: 		return !!(a->weight > b->weight);
 22: 	}
 23: };
 24: 
 25: typedef priority_queue<Node*, vector<Node*>, Node_comparator> Forest;
 26: Node* huffman(Forest& f);
 27: void encode(Forest& f);
 28: void encode(Node* n, list<char> li=list<char>());
 29: 
 30: Node* huffman(Forest& f)
 31: {
 32: 	while (f.size() > 1)
 33: 	{
 34: 		Node* const n1 = f.top(); f.pop();
 35: 		cout << n1->weight << endl;
 36: 		Node* const n2 = f.top(); f.pop();
 37: 		cout << n2->weight << endl;
 38: 		Node* nf = new Node(n1->weight + n2->weight);
 39: 		nf->left = (n1->weight < n2->weight) ? n2 : n1;
 40: 		nf->right = (n1->weight < n2->weight) ? n1 : n2;
 41: 		f.push(nf);
 42: 	}
 43: 	return f.top();
 44: }
 45: 
 46: void encode(Forest& f)
 47: {
 48: 	encode(huffman(f));
 49: }
 50: 
 51: void encode(Node* n, list<char> li)
 52: {
 53: 	if (n == 0) return;
 54: 	if (n->symbol != ‘\0‘)
 55: 	{
 56: 		for (auto c : li)
 57: 		{
 58: 			cout << c;
 59: 		}
 60: 		cout << ": " << n->symbol << endl;
 61: 		return;
 62: 	}
 63: 	list<char> l = list<char>(li);
 64: 	l.push_back(‘0‘);
 65: 	li.push_back(‘1‘);
 66: 	encode(n->left, l);
 67: 	encode(n->right, li);
 68: }

霍夫曼编码