算法科普:有趣的霍夫曼编码

栏目: 编程工具 · 发布时间: 5年前

内容简介:霍夫曼编码 ( Huffman coding ) 是一种可变长的前缀码。霍夫曼编码使用的算法是 David A. Huffman 还是在MIT 的学生时提出的,并且在 1952 年发表了名为《 A Method for the Construction of Minimum-Redundancy Codes 》的文章。编码这种编码的过程叫做霍夫曼编码使用一种特别的方法为信号源中的每个符号设定二进制码。出现频率更大的符号将获得更短的比特,出现频率更小的符号将被分配更长的比特,以此来提高数据压缩率,提高传输效率

霍夫曼编码 ( Huffman coding ) 是一种可变长的前缀码。霍夫曼编码使用的算法是 David A. Huffman 还是在MIT 的学生时提出的,并且在 1952 年发表了名为《 A Method for the Construction of Minimum-Redundancy Codes 》的文章。

编码这种编码的过程叫做 霍夫曼编码 ,它是一种普遍的熵编码技术,包括用于无损数据压缩领域。

霍夫曼编码过程

霍夫曼编码使用一种特别的方法为信号源中的每个符号设定二进制码。出现频率更大的符号将获得更短的比特,出现频率更小的符号将被分配更长的比特,以此来提高数据压缩率,提高传输效率。

以字符串 ” ABAABACD “ 为例进行说明。

接下来,按照字符出现的比例从高往低对字符进行排序。

算法科普:有趣的霍夫曼编码

然后,按出现比例低的顺序查找两个字母。在这种情况下,它是 “ C ” 12.5% 和 “ D ” 12.5% 。

通过一条线连接两个字母拼构成一个树状结果。将两个字母合并为 “ C 或 D”,并将出现比率相加起来。

算法科普:有趣的霍夫曼编码

按照同样的操作,将合并后的 “ C 或 D ” 视为一个字符,重复相同的操作。

在 “ A " "B" " C 或 D " 三个中,按照出现比例低的顺序查找两个字母。

算法科普:有趣的霍夫曼编码
算法科普:有趣的霍夫曼编码

这样,所有的字母都变成了" A 或 B 或 C 或 D" ,出现的比率为 100% 。

图 4 就是霍夫曼编码的树结构。

接下来再次显示各个字母出现的比率,同时使用 0 和 1 进行编码,代码 0 和 1 分别分配给上下延伸的分支。

算法科普:有趣的霍夫曼编码

分配完毕后,从树的根部遍历每个字符并确定相应的代码。

  • 在 ” A “ 的情况下,被分配的代码为 ” 0 “
  • 在 ” B “ 的情况下,被分配的代码为 ” 10 “
  • 在 ” C “ 的情况下,被分配的代码为 ” 110 “
  • 在 ” D “ 的情况下,被分配的代码为 ” 111 “
算法科普:有趣的霍夫曼编码

就这样,通过这样的编码规则, ” ABAABACD “ 的二进制编码就变成了 ” 01000100110111 “,只需要 14 个比特就能表示,比单纯的使用 2 比特表示一个字符缩短了很多。

算法科普:有趣的霍夫曼编码

以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

技术之瞳——阿里巴巴技术笔试心得

技术之瞳——阿里巴巴技术笔试心得

阿里巴巴集团校园招聘笔试项目组 / 电子工业出版社 / 2016-11 / 69

《技术之瞳——阿里巴巴技术笔试心得》由阿里巴巴集团校园招聘笔试项目组所著,收集了阿里历年校招中的精华笔试题,涉 及多个领域。《技术之瞳——阿里巴巴技术笔试心得》中内容大量结合了阿里巴巴的实际工作场景,以例题、解析、习题的形式,引 导读者深入理解技术上的关键点、紧要处,夯实基础,启发思考。《技术之瞳——阿里巴巴技术笔试心得》内容不仅专业、有趣,更 是将理论知识与实践应用结合起来,以场景化的问答娓娓道......一起来看看 《技术之瞳——阿里巴巴技术笔试心得》 这本书的介绍吧!

在线进制转换器
在线进制转换器

各进制数互转换器

Base64 编码/解码
Base64 编码/解码

Base64 编码/解码

MD5 加密
MD5 加密

MD5 加密工具