首页 > 资讯 > 宏观 > 正文

天天快报!霍夫曼树(图解霍夫曼编码)

2022-06-15 08:21:49来源:互联网  

霍夫曼树(图解霍夫曼编码)

简明易懂的霍夫曼编码来啦,用图片的形式解答霍夫曼是不是很简单呢,浏览完本文就去动手试一试吧!

责编 | 张红月


(相关资料图)

出处 | 沉默王二

今天来给大家普及一下霍夫曼编码(Huffman Coding),一种用于无损数据压缩的熵编码算法,由美国计算机科学家大卫·霍夫曼在 1952 年提出——这么专业的解释,不用问,来自维基百科了。

说实话,很早之前我就听说过霍夫曼编码,除了知道它通常用于 GZIP、BZIP2、PKZIP 这些常规的压缩格式中,我还知道它通常用于压缩重复率比较高的字符数据。

大家想啊,英文就 26 个字母进行的无限组合,重复率高得一逼啊!常用的汉字也不多,2500 个左右,别问我怎么知道的,我有问过搜索引擎的。

字符重复的频率越高,霍夫曼编码的工作效率就越高!

是时候,和大家一起来了解一下霍夫曼编码的工作原理啦,毕竟一名优秀的程序员要能做到知其然知其所以然——请允许我又用了一次这句快用臭了话。

假设下面的字符串要通过网络发送。

大家应该知道,每个字符占 8 个比特,上面这串字符总共有 15 个字符,所以一共要占用 15*8=120 个比特。没有疑问吧?有疑问的同学请不好意思下。

如果我们使用霍夫曼编码的话,就可以将这串字符压缩到一个更小的尺寸。怎么做到的呢?

霍夫曼编码首先会使用字符的频率创建一棵树,然后通过这个树的结构为每个字符生成一个特定的编码,出现频率高的字符使用较短的编码,出现频率低的则使用较长的编码,这样就会使编码之后的字符串平均长度降低,从而达到数据无损压缩的目的。

拿上面这串初始字符来一步步的说明下霍夫曼编码的工作步骤。

计算字符串中每个字符的频率

B 出现 1 次,C 出现 6 次,A 出现 5 次,D 出现 3 次。

按照字符出现的频率进行排序,组成一个队列 Q

出现频率最低的在前面,出现频率高的在后面。

把这些字符作为叶子节点开始构建一颗树

首先创建一个空节点 z,将最小频率的字符分配给 z 的左侧,并将频率排在第二位的分配给 z 的右侧,然后将 z 赋值为两个字符频率的和。

B 的频率最小,所以在左侧,然后是频率为 3 的 D,在右侧;然后把它们的父节点的值设为 4,子节点的频率之和。

然后从队列 Q 中删除 B 和 D,并将它们的和添加到队列中,上图中 * 表示的位置。紧接着,重新创建一个空的节点 z,并将 4 作为左侧的节点,频率为 5 的 A 作为右侧的节点,4 与 5 的和作为父节点。

继续按照之前的思路构建树,直到所有的字符都出现在树的节点中。


标签: 霍夫曼树 图解霍夫曼编码

相关阅读

404 Not Found

404 Not Found


nginx
404 Not Found

404 Not Found


nginx
404 Not Found

404 Not Found


nginx

相关词

推荐阅读