【CPP】各种各样的树（8）——赫夫曼树

看完了这么多树，来看个二叉树的小应用——赫夫曼编码（Huffman Coding），是一种用于无损数据压缩的熵编码（权编码）算法。由大卫·霍夫曼在1952年发明（这居然只是他1951年的期末作业而已，1952年发表为论文《一种构建极小多余编码的方法》（A Method for the Construction of Minimum-Redundancy Codes）https://web.archive.org/web/20050530145744/http://compression.graphicon.ru/download/articles/huff/huffman_1952_minimum-redundancy-codes.pdf）。它又称最优二叉树，是一种带权路径长度最短的二叉树。是二叉树的一个常见应用。

我们知道英文字符在计算机中可以用标准的ASCII字符集来表示，而用ASCII来表示字符的话每个字符需要8bit的位置，例如大写字母A用十进制表示为65，写为二进制就是0100 0001，这样编写我们可以很方便地表示出ASCII中的128个字符（正好八位二进制bit，第一位为0），但是其实这么写其实会造成很大的浪费。我们平时需要储存的文章中字符的出现记录是不平均的，例如在常见的英文文章中不会出现很多的‘z’，但是会有很多的‘e’，我们都用一样的字符数来表达它们就太浪费了。所以引出了最优二叉树压缩，也就是赫夫曼编码（最优前缀码）了。

编码的思想很简单，先统计或估计出将要出现的每个字符的权值（例如频次），然后按照权值摆放在一棵完全二叉树上，让权值大的字符尽可能接近树根即可，然后将各个字符对应这棵树的访问路径用01来表示，也就可以用较少的bit来表达出权值大的字符了。这里要注意一定要将字符放在树的叶子处，也就是产生的需要是前缀码，这是为了解码的时候不会产生歧义。

理解思想后就是算法，这里就需要使用赫夫曼算法，也并不难理解。首先我们在这堆带权结点中找到最小的两个结点，将他们连接为一棵子树，子树的根的权值为这两个结点的权值和，然后我们再次寻找最小的两个结点...直到全部结点被整理在一棵树上，一棵赫夫曼树便构建好了，另左侧为0右侧为1，查找路径便是赫夫曼编码。

（下图来自维基百科）

那么理解了算法直接来看实现了，这里我的代码有很多很多能改进的地方，随便看看就好。

整体的逻辑并没有很复杂的地方，想必一篇篇文章看过来的话也就没什么难以理解的了，代码里可以改进的地方很多，例如应该支持导出编码表和读取编码表，但只写了打印编码表。编码表方法和赫夫曼树的构造，由于使用了数组来存储，我们可以直接把二叉树数组中每个结点的信息按照顺序传输就好，由于使用了数组，所以结点的指针都可以用数组下标来代替，这样更方便导出。但是这些都没有实现，摸了。

测试方面我挑了世界名篇马丁·路德·金的演讲《我有一个梦想》（http://www.americanrhetoric.com/speeches/mlkihaveadream.htm），这篇经典的英语文章也很好地表现出赫夫曼压缩的效果，73728字节的（二进制输出状态）文件被压缩到了40,665字节。

（打印出的编码表，最前是十进制的ASCII，然后是ASCII的二进制状态，后面是赫夫曼编码）可以看出频率最高的101号字符得到了最短的赫夫曼编码，001，这个字符出现了892次，它就是我们一开头说到的小写字母e。

时间过的飞快，转眼就春节了，祝看到这里的朋友们18年春节快乐吧~

下一篇没有意外的话就是这个系列暂时的完结篇了，没能在春节前写出来真可惜呢，下一篇也是这个系列的重头戏——红黑树。