哈夫曼编码（Huffman编码）

Huffman编码又称霍夫曼编码，是一种编码方式，哈夫曼编码是可变[字长]编码(VLC)的一种。Huffman于1952年提出一种编码方法，该方法完全依据[字符]出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫做Huffman编码（有时也称为霍夫曼编码）。

实例分析

• MP3音频压缩
  采样：每秒采用44100次，50分钟音乐产生
  T=50×60×44100≈130M个样本
  量化：每个样本量化为有限集Γ中最近的一个值
  假设量化产生四个不同的值（字符）A、B、C、D，一种编码方式
  00表示A，01表示B，02表示C，03表示D
  50分钟音乐共需要130M×2=260Mbit

假设4个字符出现频次不同，具体如下：

image.png

• 考虑用可变长编码
  比如A、B、C、D编码为{0，01，11，001}
  70×1+3×2+20×2+37×3=227Mbit
  存在问题，字符串001可能有两种解码结果AB和D
  规则：一个码字不能是其它码字的前缀

Huffman编码方案

1. 使用完全二叉树表示无前缀编码
2. 完全二叉树
   任何节点：0个或者2个孩子节点
   如有孩子节点，左分支0，右分支1
3. 叶子节点表示编码结果
4. 字符出现频次越低，用于编码的叶子节点位置越深（叶子节点的深度被称为编码代价）

上面那个例子可以按照上面的算法逻辑进行编码，得到的总长度为
70×1+3×3+20×3+37×2=213Mbit

image.png

贪心算法构造编码树

• 从f1、f2、…、fn找到频次最低的两个字符，假设为f1和f2，作为一个父节点上的两个子节点，用f1+f2表示这个父节点的代价

• 再在f1+f2、f3、…、fn找频次最低的两个元素，….

  
  image.png