霍夫曼树基础 介绍了定长编码、变长编码、有损压缩、无损压缩的一些基本概念，并引出一个关键的发现：
利用二叉树结构来构造编码，可以确保变长编码的解码过程不产生歧义。
现在的关键在于，怎么构造这棵二叉树，才能使得编码后的数据长度最短？
霍夫曼编码（Huffman Coding）就是一种最优编码算法，它通过巧妙的方式来构造二叉树，使得树的带权路径长度（Weighted Path Length）最小，即编码后的数据长度最短。
本文将介绍它的原理，并实现一个可运行的压缩程序来运用这个算法进行文本文件压缩。
不过在介绍霍夫曼编码之前，我们不妨尝试基于目前已知的知识来发明一个构造编码树的算法。
再谈定长编码
首先可以发现，定长编码 其实就是一棵高度为 logN 的 完全二叉树。
比如这样一棵二叉树：
四个字符的编码如下：
a -> 00
b -> 01
c -> 10
d -> 11假设共有 N 个字符，这棵二叉树的高度为 logN，每个字符的编码长度等于树高，所以编码后的数据长度为 N * logN。
定长编码的问题在于没有考虑字符出现的频率，我们可以对高频的字符使用更短的编码，对低频的字符使用更长的编码，这样可以使得编码后的数据总长度更短。
再谈变长编码
显然，频率高的字符应该尽可能靠近根节点，这样能确保高频出现的字符用用更短的编码长度。
所以我能想到的一个最简单的优化思路是对所有字符按照出现的频率进行排序，然后构建一棵向右延伸的二叉树。
比如 a,b,c,d 四个字符出现的频率分别是 4,3,2,1，那么我就构建这样一棵二叉树：
在这个例子中，出现频率最高的字符 a 的编码长度为 1，频率第二高的字符 b 的编码长度为 2，频率最低的两个字符 c,d 的编码长度为 3。
这种构造方法考虑了字符出现的频率，频率越高的字符，编码越短，看起来应该会有更好的压缩效果。
那么请你仔细思考，这种编码方案是否能够保证获得最短编码方案？
实际上，这种依赖简单排序的编码方案在很多情况下都不是最优的。
举一个最简单的反例，比方说 a,b,c,d 四个字符出现的频率都是 1，按照这种构造方法，最后得到的编码长度为 1 + 2 + 3 + 3 = 9，还不如定长编码方案 4 * 2 = 8 的压缩效果好。