什么是哈夫曼编码
出现频次越高的字符，编码长度越小。
哈夫曼编码的价值
变长编码，使得编码的平均长度最短，实现压缩率大的无损压缩。
因为哈夫曼树是最优的，每次的选择都是贪心选择，这个局部最优也是全局最优。
哈夫曼编码过程
- 把文本中字符按出现的频次排序。
- 每个字符作为一个结点放入一个集合。
- 取集合最小的两个频次的结点，为左右子结点，生成一个父结点，父结点的频次是两个子结点频次之和，把父结点再加入到集合中。
- 重复这个构造过程，生成一个最优二叉树。
- 给二叉树所有左边设置0，所有右边设置1。
- 字符都在叶子结点。
- 根结点到叶子结点路径上的0和1组成的码字就是该字符的编码。
因为所有字符都出现在叶子结点，保证了哈夫曼编码当中的任何一个字符的编码都不能是另一个字符编码的前缀。也就是说哈夫曼编码是一种前缀编码。
如何证明哈夫曼编码是最优的？
哈夫曼编码过程每次的选择都是贪心选择，这个局部最优也是全局最优。
其正确性证明依赖于贪心选择性质和最优子结构。
哈夫曼编码的特点
- 编码非等长
- 编码前缀不重复
哈夫曼编码的压缩效果？
哈夫曼编码可以很有效的压缩数据，具体压缩率依赖于数据本身的特性。
齐夫定律：
发现某一单词出现的频率与其在频率表里名次的常数次幂成反比，也就是说极少数的单词会被经常使用，而绝大多数单词很少被提及，这种20/80法则在很多领域都被逐步发现，这种幂律分布被称为“齐夫定律”（Zipf’s law）
一般信息的分配都是幂率分布。
所以用哈夫曼编码压缩的比例一般都挺高的，70%以上。
信息压缩的极限在哪？
香农第一定理给出了无损的情况下数据压缩的临界值。
参考：信息论入门教程