前两天发布那个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
分享到:
相关推荐
Huffman 编码压缩算法,c++代码。实现数据压缩。
Huffman 编码是一种基于字符出现频率构建相应前缀码的无损数据压缩算法。 使用方法: 1. 需要安装 OpenCV 和 Numpy 库: pip install opencv-python numpy 2. 直接运行 main.py 脚本即可使用。 压缩原理: 1. 统计...
Huffman 压缩解压工具, ...Huffman 编码压缩/解压算法,实现了对二进制文件进行压缩编码,和解压缩译码功能,界面交互简单友好,易于操作。 详细说明:https://blog.csdn.net/K1052176873/article/details/107117253
纯qt5.3库编的程序所有源代码。 1.huffman编码 2.基于huffuman编码的压缩解压缩 3.基于huffuman编码的网络通信局域网聊天 4.sqlite数据库用户登入注册系统功能 5.基于QT画huffman树算法
(2)采用哈弗曼算法对各字节进行编码,建立哈弗曼对照表; a)构造二叉树 b)编码 (3)依次读取原始文件的每个字节,查找其对应的哈弗曼编码,将这些位写入到压缩文件中(注意:要凑够8位二进制才写入到文件中)。 ...
用C语言实现了Huffman编码,并对同一个文本文件进行压缩和解压缩,文本文件仅限于英文文件。解压缩后的文件跟原文件一样。压缩较大的文件效果明显,但是仅压缩1个字节或者非常少的字节文件会增大文件。
霍夫曼(Huffman)编码算法是满足前缀条件的平均二进制码长最短的编码算法。其编码思想是将较长的编码码字分配给较小概率的信源输出符号,而将较短的编码码字分配给较大概率的信源输出。文章详细描述了Huffman编解码...
根据信源压缩编码——Huffman编码的原理,制作对英文文本进行压缩,要求最终结果含有:字符频率统计报告、编码报告、压缩程度信息报告、码表存储空间报告。 由于haffman的算法许多书上都有,所以实现起来不是什么...
基于霍夫曼(Huffman)图像编码的图像压缩和重建-含Matlab代码
通过二进制流读入文件,然后以字节计算统计的方式进行文件的压缩,压缩算法使用huffman,
数据结构与算法综合实验之Huffman编码压缩实验,压缩图片、文本文件
文本文件压缩解压 vc工程 windows图形界面 大学计算机专业 数据结构 课程实验设计
武汉理工大学算法与数据结构综合实验Huffman编码压缩存储实验报告
java编写的huffman编码对文本文件进行压缩和解压,有完整的测试文件、java文件和测试结果文件,还附有详细的算法设计说明。良心资源,值得拥有!
前些时间找的关于字典编码的资料,详细介绍了几种基于字典压缩的算法,如lz77,lzw等
Huffman编码对文件进行操作,包括压缩和解压。是数据结构与算法分析课程设计的其中一个实验的源代码。
文本文件压缩的经典算法,压缩效率高,速度快,支持多种文件的压缩
1、随机产生一组不少于1000码元的二进制序列并进行Huffman编码与解码;利用Matlab, C或者其他编程语言计算信源Huffman编码的平均码长和编码效率;...试用LZW算法将文档压缩,再解压缩。 有报告和源程序
字符文件统计字符出现频度,构造Huffman 树,编制Huffman编码,并将给定字符文件编码,生成编码文件;再将给定编码文件解码,生成字符文件
HUFFMAN编码又称哈夫曼编码,是一种可变长编码方式,是由美国数学家David Huffman创立的,是二叉树的一种特殊转化形式。编码的原理是:将使用次数多的代码转换成长度较短的代码,而使用次数少的可以使用较长的编码,...