1218 - 聪明的木匠

哈夫曼编码与哈夫曼树

哈夫曼编码

哈夫曼编码（ Huffman Coding），又称霍夫曼编码，是一种编码方式，哈夫曼编码是可变字长编码（ VLC ）的一种。 Huffman 于 1952 年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫做 Huffman编码（有时也称为霍夫曼编码）。
定义看起来比较抽象，我们来做一下具体的解释。哈夫曼编码可以用来做无损的文件压缩，我们常用的 zip,rar,7z 等压缩算法，都用到了哈夫曼编码，而哈夫曼编码思想的本质是贪心算法。
具体原理是这样的，我们日常用到的所有文件，存储在硬盘上的每一个字节（ 8 bit ），都可以表示为 0−255的一个数字。反过来，保存这个数字需要一个字节的空间。但这些数字出现的频率是不一样的，有的高有的低。于是我们想有没有方法，让出现频率高的数字编码长度短一些，让出现频率低的数字，编码长度长一些，这样占用的总空间就变小了。

哈夫曼编码保证所有编码的前缀都不相同，这样就可以保证不同的原始数据一定编码成不同的哈夫曼码。反过来做解码的过程中，能够明确知道每一个编码的结束位置，方便快速解码。
如果我们把编码中的 0,1，看作树的节点，那么恰好对应一颗二叉树，这就是哈夫曼树。

哈夫曼树

给定 N 个权值作为 N 个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树 (Huffman Tree) 。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。

以本图为例，绿色的是最终的叶子节点，节点上的数字，是点的权值 Wi，我们可以理解为编码出现的次数。而叶子结点到根结点的距离 Li可以理解为编码的长度。而整个树的权值等于所有 Wi×Li的和，我们可以理解为总的编码长度。
按照本图的分配方法，整棵树的权值为： (2+4)×5+7×4+(8+12+19)×3+(20+30)×2=275。
这是一个最优的编码方式。构造哈夫曼树，需要配合一个优先队列来实现，后面我们用例题来帮助大家理解。