分类： 技术文档 2008-10-20 20:31
Huffman编码原理简介
今天有同学问我huffman算法原理,我本想就在网上找篇文章给他就解决了,没想到找了半天居然看到网上的huffman算法都只是随便copy了一些文章的段落就了事,又没有图片,有没有说明。虽然huffman编码不算难，但是我个人觉得还是写个简单的说明文档要容易让人懂。所以干脆我自己来写一个图文介绍吧！
以下是Huffman编码原理简介：
霍夫曼（Huffman）编码是1952年为文本文件而建立，是一种统计编码。属于无损压缩编码。霍夫曼编码的码长是变化的，对于出现频率高的信息，编码的长度较短；而对于出现频率低的信息，编码长度较长。这样，处理全部信息的总码长一定小于实际信息的符号长度。
对于学多媒体的同学来说，需要知道Huffman编码过程的几个步骤：
l）将信号源的符号按照出现概率递减的顺序排列。（注意，一定要递减）
2）将最下面的两个最小出现概率进行合并相加，得到的结果作为新符号的出现概率。
3）重复进行步骤1和2直到概率相加的结果等于1为止。
4）在合并运算时，概率大的符号用编码0表示，概率小的符号用编码1表示。
5）记录下概率为1处到当前信号源符号之间的0，l序列，从而得到每个符号的编码。
2）将最下面的两个最小出现概率进行合并相加，得到的结果作为新符号的出现概率。
3）重复进行步骤1和2直到概率相加的结果等于1为止。
4）在合并运算时，概率大的符号用编码0表示，概率小的符号用编码1表示。
5）记录下概率为1处到当前信号源符号之间的0，l序列，从而得到每个符号的编码。
下面我举个简单例子:
一串信号源S＝{s1,s2,s3,s4,s5}对应概率为p＝{40，30，15，10，5}，（百分率）
按照递减的格式排列概率后，根据第二步，会得到一个新的概率列表，依然按照递减排列，注意：如果遇到相同概率，合并后的概率放在下面！
最后概率最大的编码为0，最小的编码为1。如图所示：
所以，编码结果为
s1=1
s2=00
s3=010
s4=0110
s5=0111
霍夫曼编码具有如下特点：
1) 编出来的码都是异字头码，保证了码的唯一可译性。
2) 由于编码长度可变。因此译码时间较长，使得霍夫曼编码的压缩与还原相当费时。
3) 编码长度不统一，硬件实现有难度。
4) 对不同信号源的编码效率不同，当信号源的符号概率为2的负幂次方时，达到100％的编码效率；若信号源符号的概率相等，则编码效率最低。
5) 由于0与1的指定是任意的，故由上述过程编出的最佳码不是唯一的，但其平均码长是一样的，故不影响编码效率与数据压缩性能。
2) 由于编码长度可变。因此译码时间较长，使得霍夫曼编码的压缩与还原相当费时。
3) 编码长度不统一，硬件实现有难度。
4) 对不同信号源的编码效率不同，当信号源的符号概率为2的负幂次方时，达到100％的编码效率；若信号源符号的概率相等，则编码效率最低。
5) 由于0与1的指定是任意的，故由上述过程编出的最佳码不是唯一的，但其平均码长是一样的，故不影响编码效率与数据压缩性能。
- 上一篇： [转]钽电容封装及技术参数
- 下一篇： Huffman解码
文章评论（2条评论）
登录后参与讨论
EE直播间
更多
-
第三代功率半导体器件测试解决方案 直播时间： 03月06日 10:00
关闭
站长推荐
/3 
/3
-
返回顶部
-
用户1442571 2011-2-28 19:48
用户1442571 2011-2-16 14:42