首页 > 杂项资源, 程序设计 > Huffman 编码压缩算法

Huffman 编码压缩算法

2012年5月22日 发表评论 阅读评论 40,658 人阅读    

前两天发布那个rsync算法后,想看看数据压缩的算法,知道一个经典的压缩算法Huffman算法。相信大家应该听说过 David Huffman 和他的压缩算法—— Huffman Code,一种通过字符出现频率,Priority Queue,和二叉树来进行的一种压缩算法,这种二叉树又叫Huffman二叉树 —— 一种带权重的树。从学校毕业很长时间的我忘了这个算法,但是网上查了一下,中文社区内好像没有把这个算法说得很清楚的文章,尤其是树的构造,而正好看到一篇国外的文章《A Simple Example of Huffman Code on a String》,其中的例子浅显易懂,相当不错,我就转了过来。注意,我没有对此文完全翻译。

我们直接来看示例,如果我们需要来压缩下面的字符串:

 “beep boop beer!” 

首先,我们先计算出每个字符出现的次数,我们得到下面这样一张表 :


字符 次数
‘b’ 3
‘e’ 4
‘p’ 2
‘ ‘ 2
‘o’ 2
‘r’ 1
‘!’ 1


然后,我把把这些东西放到Priority Queue中(用出现的次数据当 priority),我们可以看到,Priority Queue 是以Prioirry排序一个数组,如果Priority一样,会使用出现的次序排序:下面是我们得到的Priority Queue:

接下来就是我们的算法——把这个Priority Queue 转成二叉树。我们始终从queue的头取两个元素来构造一个二叉树(第一个元素是左结点,第二个是右结点),并把这两个元素的priority相加,并放回Priority中(再次注意,这里的Priority就是字符出现的次数),然后,我们得到下面的数据图表:

同样,我们再把前两个取出来,形成一个Priority为2+2=4的结点,然后再放回Priority Queue中 :

继续我们的算法(我们可以看到,这是一种自底向上的建树的过程):

最终我们会得到下面这样一棵二叉树:

此时,我们把这个树的左支编码为0,右支编码为1,这样我们就可以遍历这棵树得到字符的编码,比如:‘b’的编码是 00,’p’的编码是101, ‘r’的编码是1000。我们可以看到出现频率越多的会越在上层,编码也越短,出现频率越少的就越在下层,编码也越长

最终我们可以得到下面这张编码表:


字符 编码
‘b’ 00
‘e’ 11
‘p’ 101
‘ ‘ 011
‘o’ 010
‘r’ 1000
‘!’ 1001


这里需要注意一点,当我们encode的时候,我们是按“bit”来encode,decode也是通过bit来完成,比如,如果我们有这样的bitset “1011110111″ 那么其解码后就是 “pepe”。所以,我们需要通过这个二叉树建立我们Huffman编码和解码的字典表。

这里需要注意的一点是,我们的Huffman对各个字符的编码是不会冲突的,也就是说,不会存在某一个编码是另一个编码的前缀,不然的话就会大问题了。因为encode后的编码是没有分隔符的。

于是,对于我们的原始字符串  beep boop beer!

其对就能的二进制为 : 0110 0010 0110 0101 0110 0101 0111 0000 0010 0000 0110 0010 0110 1111 0110 1111 0111 0000 0010 0000 0110 0010 0110 0101 0110 0101 0111 0010 0010 0001

我们的Huffman的编码为: 0011 1110 1011 0001 0010 1010 1100 1111 1000 1001

从上面的例子中,我们可以看到被压缩的比例还是很可观的。

作者给出了源码你可以看看( C99标准) Download the source files

(全文完)


欢迎关注CoolShell微信公众账号

(转载本站文章请注明作者和出处 酷 壳 – CoolShell.cn ,请勿用于任何商业用途)

——=== 访问 酷壳404页面 寻找遗失儿童。 ===——
好烂啊有点差凑合看看还不错很精彩 (14 人打了分,平均分: 4.71 )
Loading...
  1. 2012年12月1日12:38 | #1

    第一就是priority queue不对,’ ‘在o前面。
    第二就是缺少必要的证明。
    第三就是源码链接失效。

  2. 2012年12月14日15:53 | #2
  3. luffyke
    2012年12月28日19:10 | #3

    皓哥, 里面的源码链接已经page not found了..

  4. 2013年1月9日16:11 | #4

    @康杜
    赞。

  5. 另一种风情
    2013年8月6日15:10 | #5

    为何我算出来的结果跟文中提到的结果不同呢?编码是唯一的吗?
    根据严蔚敏数据结构教材中的例子程序测试的:
    00
    01
    100
    101
    110
    1110
    1111

  6. gkm_leo
    2014年2月24日11:19 | #6

    您好,请问,二叉树的两支是依据什么构建的?比如您的文章中的二叉树是唯一的吗?

  7. 2014年3月11日22:58 | #7

    明确简了点

  8. 2014年3月24日03:40 | #8

    太赞了,一看就懂,比起几百页的高科技教科书都好用!摘了,并添加Huffman的比特流解码部分。如果再有篇LZ77算法的简易版就高兴死我了!

  9. furskytl
    2015年8月31日15:04 | #9

    优先队列是一个按序排列的数组?您是说C++ STL中的priority_queue吗?

  10. 小林
    2016年3月24日16:41 | #10

    请问有没有Huffman算法的C语言的实现方法,想要实现下,望大神指教…求指教求链接…谢谢!

  11. 2016年4月26日12:48 | #11

    That’s an apt answer to an initeestrng question

评论分页
1 2 3 7459
  1. 2012年11月12日18:09 | #1
  2. 2012年12月28日09:03 | #2
  3. 2012年12月28日16:22 | #3
  4. 2012年12月28日20:41 | #4
  5. 2012年12月30日19:40 | #5
  6. 2013年1月5日10:46 | #6
  7. 2013年1月14日21:44 | #7
  8. 2013年1月19日03:34 | #8
  9. 2013年1月26日18:19 | #9
  10. 2013年2月6日10:42 | #10
  11. 2013年2月24日11:03 | #11
  12. 2013年8月12日00:09 | #12
  13. 2013年10月20日08:03 | #13
  14. 2013年12月31日14:38 | #14
  15. 2014年3月31日23:44 | #15
  16. 2014年4月21日20:39 | #16
  17. 2014年9月19日20:32 | #17
  18. 2014年11月16日22:42 | #18
  19. 2014年11月19日09:52 | #19
  20. 2015年3月16日15:07 | #20
  21. 2015年3月24日15:59 | #21