哈弗曼编码(haffman-Coding)

======================= **基础知识** =======================

编码：信息的不同表示形式；

定长编码：典型的就是 ASCII 编码； 缺点：有些位数是没必要的；

变长编码：保证任意两个字符的编码都不一样，且编码的长度是不固定即可；

　　有效的变长编码：任意一个字符的编码，不能是其他字符编码的前缀；对于计算机来讲，有效变长编码更有意义；

　　　　　　　　　　因此如果把编码看成二叉树上的路径，所有字符均落在叶子节点上；

哈弗曼编码(huffman coding, 最优二叉树）： 是最优的变长编码，其平均编码长度

　　1. 统计字符出现的频率；在英文文章中，每个字符出现的频率是不一样的；step: a;

　　2. 建树；每次取频率最低的两个字符，建立一个节点；step:b ~ e;

　　3. 提取编码；step f.

======================= **代码演示** =======================

 1 /////////////////////////input///////////////////////////////////
 2 10
 3 a 12341
 4 b 1234
 5 c 235
 6 d 8753
 7 e 97553
 8 f 98752
 9 g 1178 
10 h 28909
11 i 56798
12 k 2388
13 
14 //////////////////////////////////////////////////////
15 #include 
16 #include <set>
17 #include 
18 using namespace std;
19 #define BASE 128
20 
21 struct Node {
22     Node(int f = 0, char c = 0, Node *l = nullptr, Node *r = nullptr): freq(f), ch(c), lchild(l), rchild(r) {}
23     Node(int f = 0, Node *l = nullptr, Node *r = nullptr): freq(f), ch(0), lchild(l), rchild(r) {}
24     int freq;
25     char ch;
26     Node *lchild, *rchild;
27 };
28 
29 class CMP{
30     public:
31     bool operator() (const Node* a, const Node* b) const {
32         return a->freq < b->freq;
33     }
34 };
35 
36 void getHalfmanCode(Node* root, vector<string> &code, string str) {
37     if(!root) return;
38     if(root->ch)  {
39         code[root->ch] = str;
40         return;
41     }
42 
43     getHalfmanCode(root->lchild, code, str + "0");
44     getHalfmanCode(root->rchild, code, str + "1");
45 
46     return;
47 }
48 
49 
50 int main()
51 {
52     int cnt, freq, record[BASE] = {0};
53     char c;
54     cin >> cnt;
55     multiset data;
56     for(int i = 0; i < cnt; ++i)  {
57         cin >> c >> freq;
58         record[c] = freq;
59         data.insert(new Node(freq, c));
60     }
61 
62     while(data.size() > 1) {
63         Node *a = *(data.begin()); data.erase(data.begin());
64         Node *b = *(data.begin()); data.erase(data.begin());
65 
66         data.insert(new Node(a->freq + b->freq, a, b));
67     }
68 
69     vector<string> code(BASE);
70     getHalfmanCode((*data.begin()), code, "");
71 
72     for(int i = 0; i < BASE; ++i) {
73         if(code[i] == "") continue;
74         printf("%c(%6d): %s\n", i, record[i], code[i].c_str());
75     }
76 
77     return 0;
78 }

======================= **经典问题** =======================
======================= **应用场景** =======================

在网络传输中，变长编码得到的信息的长度 <=  定长编码得到的信息长度，可以在网速相同的情况下，可以提高信息的传输效率；