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编码方案
- 使用完全二叉树表示无前缀编码
- 完全二叉树
任何节点：0个或者2个孩子节点
如有孩子节点，左分支0，右分支1- 叶子节点表示编码结果
- 字符出现频次越低，用于编码的叶子节点位置越深（叶子节点的深度被称为编码代价）
上面那个例子可以按照上面的算法逻辑进行编码，得到的总长度为
70×1+3×3+20×3+37×2=213Mbit
image.png
贪心算法构造编码树
- 从f1、f2、…、fn找到频次最低的两个字符，假设为f1和f2，作为一个父节点上的两个子节点，用f1+f2表示这个父节点的代价
-
再在f1+f2、f3、…、fn找频次最低的两个元素，….
image.png
