文档章节

霍夫曼编码压缩算法

温家成
 温家成
发布于 2016/12/21 13:30
字数 968
阅读 121
收藏 1

摘自算法爱好者微信号

来源: 陈皓 链接:http://coolshell.cn/articles/7459.html

一个经典的压缩算法Huffman算法。相信大家应该听说过 David Huffman 和他的压缩算法—— Huffman Code,一种通过字符出现频率,Priority Queue,和二叉树来进行的一种压缩算法,这种二叉树又叫Huffman二叉树 —— 一种带权重的树。一篇国外的文章《A Simple Example of Huffman Code on a String》,其中的例子浅显易懂,相当不错,我就转了过来。注意,没有对此文完全翻译。

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

“beep boop beer!”

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

输入图片说明

然后,我把把这些东西放到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。我们可以看到出现频率越多的会越在上层,编码也越短,出现频率越少的就越在下层,编码也越长。

输入图片说明

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

输入图片说明

这里需要注意一点,当我们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

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

精选留言:1.由下向上,由低频向高频建立二叉树,保证了越高频字符编码越短,所有的有效自字符都出现在叶子节点上,保证了一个字符的编码不会是另外一个字符的前缀

2.编码表是约定的 对于中文编码问题 比如“的”“了”这些常用字所用的比特是要少很多的 这样编码比正常的等长编码在字符出现频率基本相同的情况下肯定可以达到压缩的效果 这个可以被理论证明

本文转载自:http://coolshell.cn/articles/7459.html

温家成

温家成

粉丝 84
博文 7
码字总数 768
作品 0
广州
程序员
私信 提问
【工具使用系列】关于 MATLAB 图像编码 & 图像压缩,你需要知道的事情

如何进行图像压缩 图像压缩 统计编码 行程编码 霍夫曼编码 预测编码 预测编码 视频压缩 图像序列和电影 时间冗余和运动补偿 什么是图像压缩 图像编码概述 图像压缩编码的必要性和可能性 图像...

AllenMoore
2018/01/27
4
0
数据压缩----霍夫曼树和霍夫曼压缩

霍夫曼压缩的思想: 使用较少的比特表示出现频繁的字符而使用较多的比特表示使用较少的字符。这样表示字符串所使用的总比特数就会减少。 前提:所有字符编码都不会成为其他字符编码的前缀。使...

SuperHeroes
2018/01/28
0
0
数据压缩算法----游程编码和霍夫曼编码

游程编码 定义: 用一个 符号值/串 代替具有相同值的连续符号(连续符号构成了一段连续的“游程”。游程编码因此而得名),使符号长度少于原始数据的长度。 应用场景: 游程编码经典应用场景...

SuperHeroes
2018/01/28
0
0
数据结构-04-霍夫曼压缩(Huffman Compression)

Huffman Compression - 霍夫曼压缩 主要思想:放弃文本文件的普通保存方式:不再使用7位或8位二进制数表示每一个字符,而是用较少的比特表示出现频率最高的字符,用较多的比特表示出现频率低...

Corwien
2016/06/17
26
0
zip 的压缩原理与实现

http://www.blueidea.com/bbs/newsdetail.asp?id=1819267&page=2&posts=&Daysprune=5&lp=1 无损数据压缩是一件奇妙的事情,想一想,一串任意的数据能够根据一定的规则转换成只有原来 1/2 - ...

晨曦之光
2012/03/09
313
0

没有更多内容

加载失败,请刷新页面

加载更多

【AI实战】手把手教你深度学习文字识别(文字检测篇:基于MSER, CTPN, SegLink, EAST等方法)

文字检测是文字识别过程中的一个非常重要的环节,文字检测的主要目标是将图片中的文字区域位置检测出来,以便于进行后面的文字识别,只有找到了文本所在区域,才能对其内容进行识别。 文字检...

雪饼
今天
5
0
思维导图XMind 8 Pro 绿化方法(附序列号)

按部就班: Step 1 -全新下载最新版本的 Xmind 8(注必须是英文官方的版本,中文代{过}{滤}理网站的版本修改过,无法使用pj); Step 2 -安装完毕后,点击文末的下载按钮下载pj补丁文件包,将...

一只小青蛙
今天
10
0
数据结构(ER数据库)设计规范

表命名规范 表命名的规则分为3个层级,层级之间通过_分割,例如b_r_identity、d_l_identity。规约为: [leavel]_[type]_[name] [leavel] 表示数据库表的层级和功能,分为: s:业务无关的系统...

随风溜达的向日葵
今天
5
0
阿里Sentinel控制台源码修改-对接Apollo规则持久化

https://github.com/alibaba/Sentinel/wiki/%E5%9C%A8%E7%94%9F%E4%BA%A7%E7%8E%AF%E5%A2%83%E4%B8%AD%E4%BD%BF%E7%94%A8-Sentinel 动态规则扩展 https://github.com/alibaba/Sentinel/wiki......

jxlgzwh
昨天
8
0
在Linux系统中创建SSH服务器别名

如果你经常通过 SSH 访问许多不同的远程系统,这个技巧将为你节省一些时间。你可以通过 SSH 为频繁访问的系统创建 SSH 别名,这样你就不必记住所有不同的用户名、主机名、SSH 端口号和 IP 地...

老孟的Linux私房菜
昨天
12
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部