Go语言视频零基础入门到精通

admin

　　哈夫曼树是一种特殊的树，结合前面做书上动态规划题的了解，哈夫曼树就是最优二叉树。
　　建立一颗哈夫曼树前需要明确条件，比如一颗词典树（节点值为单词），我们希望能通过我们的查找习惯建立一颗更快、更合适的二叉树，那么，这里的条件就是树中每个单词的搜索频率，显然，搜索频率越高的单词越靠近树根，查找效率会更好，通过搜索频率（权值）与节点离根节点的路径距离计算出WPL（带权路径长），当词典树的形态为某种情况的时候（哈夫曼树总是一颗满二叉树 — 除叶节点外，内部节点都是儿孙满堂的），WPL最小，那么这样的一颗二叉树就是最优二叉树，也就是我们想要的树的形态了。
　　可通过动态规划算法证明，上面描述的二叉树的各个节点是否与最优二叉树的各节点相等。当然书上还有更严谨的算法数学证明。
　　WPL计算很简单，公式：WPL = ∑ L[sub]i[/sub] × P[sub]i[/sub] （其中L是路径长度，P是权值）。
　　建立哈夫曼树很简单：初始化节点数据，维护一个最小优先队列，将节点按权值大小加入到优先队列中，然后将队列中的节点弹出，由下而上建立哈夫曼树。
　　算法伪python代码：

1. """
2. class node:
3.     int f; //权值
4.     type var; //其他数据类型
5.     node left;
6.     ndoe right;
7. """
8. def build_Huffman_tree(nodes):
9.     """
10.     nodes是一组node类型的节点
11.     """
12.     priority_queue<node> que = nodes; //加入到优先队列
13.     while que.size > 1:
14.         left = que.top;
15.         right = que.top;
16.         p = new node; // 请求一个新节点
17.         p.f = left.f + right.f;
18.         que.add = p;
19.     return que.top;

复制代码

　　哈夫曼编码是一种变长编码的方式，变长编码一般比定长编码压缩率高，所以这里不考虑定长编码，但定长编码也很简单，自己制定一个编码表，通过查表的方式编码，效率高。解码也是查表即可。
　　制定哈夫曼编码规则：左路径编码为0，右路径编码为1。这样就可以通过遍历二叉树进行编码了。如图：
　　　　　　　　　　　　　　　图片来自百度图片
&nbsp;　　解码也很简单，只需要根据制定的规则，再进行树的遍历，然后通过查表即可解码。
　　完整代码：

1. #include <iostream>
2. #include <string.h>
4. #define MAXSIZE 0xffff
6. #define QUE_LEFT(i) (2*(i) + 1)
8. class node {
9. public:
10.         char var;
11.         size_t freq;
12.         node * left;
13.         node * right;
15.         node() {}
16.         node(char c, size_t f) : var(c), freq(f) {}
17.         node(node * l, node * r) : var(0), freq(l->freq + r->freq), left(l), right(r) {}
18.         virtual ~node() {}
19. };
21. class queue : public node{
22. public:
23.     size_t size_s;
24.     node * priority_queue[MAXSIZE];
26.     queue() : size_s(0) {}
27.     ~queue() {
28.         while(!empty())
29.             size_s--;
30.     }
31.     bool empty() const {
32.         if (size_s == 0)
33.             return true;
34.         return false;
35.     }
36.     bool full() const {
37.         if (size_s == MAXSIZE)
38.             return true;
39.         return false;
40.     }
41.     size_t size() const {
42.         return size_s;
43.     }
44.     void insert(node * n);
45.     node * pop();
46. };
48. void queue::insert(node * n) {
49.     if (full())
50.         exit(1);
51.         int i = size_s++;
52.         for (; i > 0 && priority_queue[i / 2]->freq >= n->freq; i /= 2)
53.                 priority_queue[i] = priority_queue[i / 2];
54.         priority_queue[i] = n;
55. }
57. node * queue::pop() {
58.         if (empty())
59.                 exit(1);
60.         size_s--;
61.         node * root = priority_queue[0];
62.         int i = 0;
63.         for (int l; QUE_LEFT(i) < (int)size_s; i = l) {
64.             l = QUE_LEFT(i);
65.                 if (l + 1 < (int)size_s && priority_queue[l + 1]->freq < priority_queue[l]->freq)
66.                         l++;
67.         priority_queue[i] = priority_queue[l];
68.         }
69.         priority_queue[i] = priority_queue[size_s];
71.         return root;
72. }
74. class HuffmanTree {
75. public:
76.         node * build_Huffman_tree(std::string str, int * & freq);
77.         void coding(node * root, char * write, char ** code, int len);
78.         std::string encode(node * root, std::string str, char ** code);
79.         void decode(node * root, std::string codes);
80.         void destory(node * root);
81. };
83. node * HuffmanTree::build_Huffman_tree(std::string str, int * & freq) {
84.     queue que;
85.         for (auto v : str)
86.                 ++freq[(int)v];
88.         for (int i = 0; i < 128 + 1; i++)
89.                 if (freq[i]) {
90.                         node * n = new node(i, freq[i]);
91.                         que.insert(n);
92.                 }
94.         while (que.size() > 1) {
95.                 node * left = que.pop();
96.                 node * right = que.pop();
97.                 node * parent = new node(left, right);
98.                 que.insert(parent);
99.         }
100.         return que.pop();
101. }
103. void HuffmanTree::coding(node * pr, char * write, char ** code, int len) {
104.     static char buf[MAXSIZE >> 1], *out = buf;
105.         if (pr->var) {
106.         write[len] = 0;
107.                 strcpy(out, write);
108.                 code[(int)pr->var] = out;
109.                 out += len + 1;
110.                 return;
111.         }
112.         write[len] = "0"; coding(pr->left, write, code, len + 1);
113.         write[len] = "1"; coding(pr->right, write, code, len + 1);
114. }
116. std::string HuffmanTree::encode(node * root, std::string str, char ** code) {
117.     char * write = new char;
118.         coding(root, write, code, 0);
119.         delete write;
121.         std::string read = "";
122.         for (auto v : str)
123.                 read += code[(int)v];
124.         return read;
125. }
127. void HuffmanTree::decode(node * root, std::string codes) {
128.         node * n = root;
129.         int i = 0;
130.         while (codes[i]) {
131.                 if (codes[i++] == "0")
132.                         n = n->left;
133.                 else
134.                         n = n->right;
136.                 if (n->var) putchar(n->var), n = root;
137.         }
138. }
140. void HuffmanTree::destory(node * root) {
141.     if (root) {
142.         destory(root->left);
143.         destory(root->right);
144.         delete root;
145.     }
146. }
148. void TravelTree(node * root) {
149.     if (root) {
150.         std::cout << root->freq;
151.         if (root->var)
152.             std::cout << ":" << root->var;
153.         std::cout << std::endl;
154.         TravelTree(root->left);
155.         TravelTree(root->right);
156.     }
157. }
159. int main()
160. {
161.     int freq[128 + 1] = { 0 }, *f = freq;
162.     char *code[MAXSIZE + 1];
164.     node * root;
165.         HuffmanTree tree;
167.         std::string str = "hello world!";
169.         root = tree.build_Huffman_tree(str, f);
171.         str = tree.encode(root, str, code);
172.         for (int i = 0; i < 128 + 1; i++)
173.         if (code[i]) {
174.             std::cout << (char)i << ":" << freq[i] <<
175.             " --- " << code[i] << std::endl;
176.         }
178.         std::cout << "编码结果：" << str << std::endl;
180.         std::cout << "解码：";
181.         tree.decode(root, str);
183.     return 0;
184. }

复制代码

　　运行结果：

&nbsp;　　参考资料：
　　　　1.这个网址是在维基百科找到的，有各种语言的哈夫曼编码的实现：http://rosettacode.org/wiki/Huffman_coding
　　　　2.http://www.cnblogs.com/sench/p/7798064.html