霍夫曼编码压缩算法

标签: IT技术 程序员 算法 | 发表时间:2012-05-23 07:59 | 作者:齐哲
出处:http://blog.jobbole.com

前两天发布那个rsync算法后,想看看数据压缩的算法,知道一个经典的压缩算法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

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

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

(全文完)

相关文章

相关 [霍夫曼 编码 压缩] 推荐:

霍夫曼编码压缩算法

- - 博客 - 伯乐在线
前两天发布那个rsync算法后,想看看数据压缩的算法,知道一个经典的压缩算法Huffman算法. 相信大家应该听说过  David Huffman 和他的压缩算法——  Huffman Code,一种通过字符出现频率, Priority Queue,和二叉树来进行的一种压缩算法,这种二叉树又叫Huffman二叉树 —— 一种带权重的树.

视频压缩编码和音频压缩编码的基本原理

- - CSDN博客推荐文章
本文介绍一下视频压缩编码和音频压缩编码的基本原理. 其实有关视频和音频编码的原理的资料非常的多,但是自己一直也没有去归纳和总结一下,在这里简单总结一下,以作备忘. 以记录数字视频的YUV分量格式为例,YUV分别代表亮度与两个色差信号. 例如对于现有的PAL制电视系统,其亮度信号采样频率为13.5MHz;色度信号的频带通常为亮度信号的一半或更少,为6.75MHz或3.375MHz.

低比特率视听会议压缩编码标准H.263

- - CSDN博客推荐文章
转载请标明是引用于 http://blog.csdn.net/chenyujing1234 . 欢迎大家提出意见,一起讨论!. H.263是国际电联ITU-T的一个标准草案,是为低码流通信而设计的. 但实际上这个标准可用在很宽的码流范围,. H.263的编码算法与H.261一样,但做了一些改善和改变,以提高性能和纠错能力.

Apple新闻之苹果宣布旗下 Apple Lossless 无损压缩音频格式的编码器开源

- D31T4 - 苹果fans-中文 Apple Blog
    “Apple Lossless(Apple Lossless Audio Codec、ALAC)为苹果的无损音频压缩编码格式,可将非压缩音频格式(WAV、AIFF)压缩至原先容量的40%至60%左右,编解码速度很快. 也因为是无损压缩,听起来与原文件完全一样,不会因解压缩和压缩而改变.     目前支持 Apple Lossless 的主要是苹果自家的 iTunes、iPod、iOS 设备,上周苹果宣布将旗下的 Apple Lossless Audio Codec(ALAC)无损音频编解码器以 Apache License 为协议公布源代码,这样无疑会吸引第三方设备和软件对它的支持.

String压缩 解压缩

- - CSDN博客推荐文章
数据传输时,有时需要将数据压缩和解压缩,本例使用GZIPOutputStream/GZIPInputStream实现. 1、使用ISO-8859-1作为中介编码,可以保证准确还原数据. 2、字符编码确定时,可以在decompress方法最后一句中显式指定编码. * @return 压缩后的字符串. GZIPOutputStream os = null; // 使用默认缓冲区大小创建新的输出流.

Nginx GZip 压缩

- - 开心平淡对待每一天。热爱生活
  Nginx GZip 模块文档详见: http://wiki.nginx.org/HttpGzipModule 常用配置片段如下:. # 压缩比例,比例越大,压缩时间越长. 默认是1 gzip_types. text/css text/javascript; # 哪些文件可以被压缩 gzip_disable.

HDFS-压缩

- - Java - 编程语言 - ITeye博客
文件压缩带来了两大益处1)减少存贮空间2)加速网络(磁盘)传输. 基于大数据的传输,都需要经过压缩处理. 压缩格式 工具 算法 文件扩展名 可分块. Java代码 复制代码 收藏代码. 24.        // io.compression.codecs 定义列表中的一个 . Native gzip 库减少解压缩时间在50%,压缩时间在10%(同java实现的压缩算法).

Doclist压缩方法简介

- flychen50 - 搜索技术博客-淘宝
本文是作者在学习doclist压缩时的一点总结,希望以尽可能简单明了的方式描述各个算法的思想和适用场景,帮助同学们理解和比较. 本文并不涉及具体的算法实现,代码请大家自行google. 这里需要强调的是“所谓的改进顺序”只是作者yy出来方便理解记忆,并不反应真实的压缩方法发展历程. 倒排表的基本组成部分,看例子:.

uglifyjs批量压缩js

- - JavaScript - Web前端 - ITeye博客
jquery官方使用uglifyjs进行压缩的,压缩比较高. uglifyjs的安装方法. . 前端js压缩,使用uglifyjs压缩当前目录里的所有js文件,. 压缩后,会将原文件替换为压缩过的文件.

android图片压缩方法

- - CSDN博客移动开发推荐文章
第一:我们先看下质量压缩方法.         image.compress(Bitmap.CompressFormat.JPEG, 100, baos);//质量压缩方法,这里100表示不压缩,把压缩后的数据存放到baos中  .         while ( baos.toByteArray().length / 1024>100) {  //循环判断如果压缩后图片是否大于100kb,大于继续压缩         .