<style> .reveal p{text-align:left;}</style> # 哈夫曼编码 什么是编码？ [参考](https://blog.csdn.net/qq_41627408/article/details/137659345?utm_medium=distribute.pc_relevant.none-task-blog-2~default~baidujs_baidulandingword~default-0-137659345-blog-79513018.235^v43^pc_blog_bottom_relevance_base5&spm=1001.2101.3001.4242.1&utm_relevant_index=3) --- 哈夫曼编码，又称为赫夫曼编码（Huffman Coding），是一种可变长编码（ VLC, variable length coding)）方式，比起定长编码的 ASCII 编码来说，哈夫曼编码能节省很多的空间，因为每一个字符出现的频率不是一致的；是一种用于无损数据压缩的熵编码算法，通常用于压缩重复率比较高的字符数据。 --- 如果我们通过转换成ASCII码对应的二进制数据将字符串 BCAADDDCCACACAC 通过二进制编码进行传输，那么一个字符传输的二进制位数为 8bits，那么总共需要 120 个二进制位；而如果使用哈夫曼编码，该串字符可压缩至 28位。  --- 程序实现： ```c++ //c++编码实现 #include<iostream> #include<cstdio> char a[] = "BCAADDDCCACACAC"; using namespace std; int main(void) { return 0; } ``` --- ## 一、哈夫曼编码方法 哈夫曼编码首先会使用**字符的频率**创建一棵**树**，然后通过这个**树的结构**为每个字符生成一个特定的编码，**出现频率高的字符使用较短的编码**，出现频率低的则使用较长的编码，这样就会使编码之后的字符串**平均长度降低**，从而达到**数据无损压缩**的目的。 --- **1. 计算字符串中每个字符的频率：**  --- **2. 按照字符出现的频率进行排序，组成一个队列 Q** 出现频率最低的在前面，出现频率高的在后面。  --- 编程实现： ```c++ // 使用STL的 priority_queue来实现频率排序 #include<algorith> struct Item { char c; int freq; bool operator < (const Item it) const { if(freq == it.freq) return c < it.c; return freq < it.freq; } }; int len; priority_queue<Item> pq; void handleChar() { map<char, int> m; for(int i = 0; i < strlen(a); i++) m[a[i]]++; for(auto i:m) pq.push_back({i.first, i.second}); len = pq.size(); } ``` --- **3. 把这些字符作为叶子节点开始构建一颗哈夫曼树** 哈夫曼树又称为**最优二叉树**，是一种**带权路径长度最短的二叉树**。 --- （1）首先创建一个空节点 z，将最小频率的字符分配给 z 的左侧，并将频率排在第二位的分配给 z 的右侧，然后将 z 赋值为两个字符频率的和；然后从队列 Q 中删除 B 和 D，并将它们的和添加到队列中，上图中 * 表示的位置。  --- （2）紧接着，重新创建一个空的节点 z，并将 4 作为左侧的节点，频率为 5 的 A 作为右侧的节点，4 与 5 的和作为父节点，并**把这个和按序加入到队列中，再根据频率从小到大构建树结构（小的在左）**。  --- （3）继续按照之前的思路构建树，直到所有的字符都出现在树的节点中，哈弗曼树构建完成。 **节点的带权路径长度**为从根节点到该节点的路径长度与节点权值的乘积。 该二叉**树的带权路径长度** WPL = 6 * 1 + 5 * 2 + 3 * 3 + 1 * 3 = 28。  --- **4. 对字符进行编码：** 哈夫曼树构建完成，下面我们要对各个字母进行编码，编码原则是：对于每个非叶子节点，**将 0 分配给连接线的左侧，1 分配给连接线的右侧**，最终得到字符的编码就是**从根节点开始，到该节点的路径上的 0 1 序列组合**。  因此各个字母的编码分别为： | **A** | **B** | **C** | **D** | | ----- | ----- | ----- | ----- | | 11 | 100 | 0 | 101 | --- 在没有经过哈夫曼编码之前，字符串“BCAADDDCCACACAC”的二进制为： ```c 100001001000011010000010100000101000100010001000100010001000011010000110100000101000011010000010100001101000001010000111 ``` 也就是占了 120 比特； 编码之后为： ```c 10001111101101101001101101101 ``` 占了 28 比特。 --- **5. 确定发送的数据** 哈夫曼编码将发送字符串的数据长度极大压缩，考虑到接收方的编码，还需要把哈夫曼树的结构也传递过去。 即**字符占用**的 32 比特和 **频率占用**的 15 比特也需要传递过去。 总体上，编码后比特数为32 + 15 + 28 = 75，比 120 比特少了 45 个，效率还是非常高的。  --- 从本质上讲，哈夫曼编码是将最宝贵的资源（最短的编码）给出现概率最多的数据。 在上面的例子中，C 出现的频率最高，它的编码为 0，就省下了不少空间。 --- ## 二、特点 **哈夫曼树和编码都不唯一！只有树的WPL(带权路径长度)才是唯一的！** --- 哈夫曼编码有两个特点： 1. **带权路径长度WPL最短且唯一**； 2. **编码互不为前缀**（一个编码不是另一个编码的开头）。 --- 为什么通过哈夫曼编码后得到的二进制码**不会有前缀的问题**呢？ 这是因为在哈夫曼树中，每个字母对应的节点都是**叶子节点**，而他们对应的二进制码是由根节点到各自节点的路径所决定的，正因为是叶子节点，每个节点的路径不可能和其他节点有前缀的关系。 为什么通过哈夫曼编码获得的二进制码短呢？ 因为哈夫曼树是**带权路径长度最短的树**，权值较大的节点离根节点较近。而带权路径长度是指：树中所有的叶子节点的权值乘上其到根节点的路径长度，这与最终的哈夫曼编码总长度成正比关系的。 ---