开发者学堂课程【高校精品课-华中科技大学 -智能媒体计算：Huffman 编码】学习笔记，与课程紧密联系，让用户快速学习知识。
课程地址：https://developer.aliyun.com/learning/course/811/detail/15683
Huffman 编码
内容介绍：
一、编码思想
二、哈夫曼编码的步骤
三、例题讲解
四、采用哈夫曼编码时注意
一、编码思想
统计中应用的最广泛的编码是 Huffman 编码。
1. 哈夫曼编码方法于1952年问世
2. 算法思想
按照概率出现大小的顺序，对输出码字分配不同码字长度的变字长编码方法
输出码字的平均码长最短，与信息嫡值接近，编码方法最佳（因为最小长度的编码是信息熵，有比其更接近的但是相比哈夫曼编码其效率更低。）
3. 迄今为止仍经久不衰，广泛应用于各种数据压缩技术中，且仍不
失为嫡编码中的最佳编码方法
二、哈夫曼编码的步骤
哈夫曼编码核心思想是概率大的得到的码字短，概率小的得到的码字长。
编码步骤就是看如何实现该核心思想，并且让其效率更高。
Step 1:概率统计（如对一幅图像作灰度信号统计)得到 n 个不同概率的信息符号（在语音中可以对其采样点的本身幅值进行统计）
Step 2:将 n 个信源信息符号的 n 个概率按概率大小排序
Step 3:将 n 个概率中最后两个小概率相加，这时概率个数减为 n-1个
Step 4:将 n-1个概率按大小重新排序（原因是最小的两个相加的和未必是最小的）
Step 5:重复( 3），将新排序后的最后两个小概率再相加，相加和与其余概率再排序
Step 6:如此反复重复 n-2次，得到只剩两个概率
Step 7:以二进制码元(0，1)赋值，构成哈夫曼码字
编码结束
三、例题讲解
假设有7个符号，分别为 X1、X2、X3、X4、X5、X6、X7。其他信息和步骤图如下图所示：
第一步将最小的两个概率相加得到0.10，然后继续将最小的两个概率相加，然后排序，重复该步骤。
最后得到0.60和0.40。
然后编码，将0.60用0表示，0.40用1表示。
发现0.60是由0.35和0.25相加得到，所以0.35用00表示，0.25用01表示。0.40是0.20和0.20相加得到，因为0.40是用1表示，所以0.20是在1的后面加0，也就是10表示，另一个0.20用11表示。
继续回溯，0.25由0.15和0.10得到，分别用010和011表示，依此类推，得到 X1、X2、X3、X4、X5、X6、X7 各自的码字：
发现概率最大用了两位表示，概率最小用了4位表示。
这就是哈夫曼编码。
其码长分别为2、2、3、3、3、4、4。
根据其概率可以统计出最终的实际码长。
四、采用哈夫曼编码时注意
采用哈夫曼编码时有两个问题值得注意:
1.口哈夫曼码没有错误保护功能
在译码时，如果码串中没有错误，那么就能一个接一个地正确译出代码
如果出错，无法查出
2. 哈夫曼码是可变长度码
很难随意查找或调用压缩文件的中间内容，然后再译码，这就需要在存储代码之前加以考虑。
思考题：
信息符号及其概率如下:
求其 Huffman 编码、信息嫡和平均码长。
