WatchStor.com — 领先的中文存储网络媒体 | 51CTO旗下网站

新闻资讯 > 机房 > 正文
技术文章:告诉你数据是怎么被压缩的(1)
作者: 佚名 2011-06-30 16:47 【果壳网】

回答数据是怎么压缩的这个问题之前先来看看什么是压缩。当你有天走在路上,碰见熟人对你说:“吃了?”你一定知道他是在打招呼,既不是要请客也不是让你“没吃赶紧回家吃去”。这一句简单的“吃了”是礼貌和问好的体现,也是一种信息的压缩。笼统地说,把一系列已有信息通过一定方法处理,使得其长度缩短,并且信息含量基本或者完全不变,就称之为压缩。

计算机上的压缩过程

我们都知道,计算机采用的是2进制系统。一个连续的n位二进制数集,就可以用来表示 2 n 个字符。目前的国际标准是ASCII码:用一个字节即8位数的2进制码,来表示各种字符和字母。

现在我们只使用2位二进制码,来简单地演示由4个符号组成的字符串的压缩过程。

假设我们有这么一串20个字母的数据:

数据是怎么被压缩的

默认情况下,用2位2进制码来表示这四个字母:

数据是怎么被压缩的

每个字符在字符串种各自出现的次数并不相等:

A:6次 B:10次 C:3次 D:1次

而在计算机中,数据则是以2进制码的形式储存在硬盘上的:

00 00 01 00 00 01 01 10 01 00 01 01 01 10 01 01 00 01 11 10

压缩过程如下:

①注明每个字符的出现次数。把两个出现次数最小的字符圈到一起,看作一个新字符,新字符的次数为两个组成字符的次数之和。

②重复上述操作,直至完成对所有字符的处理。这种操作形成的结构看起来像棵树(下图),被称为——霍夫曼(Huffman)树。

③在每一层的分支线上,按下图所示分别标上0和1。

从最顶端往下读,每个字符都有唯一的分支编号连到它那里,无重复也无遗漏,这样就得到了ABCD这四个字符的新的代码:

数据是怎么被压缩的

用以上新编码代入原字符串中,得到:

10 10 0 10 10 0 0 110 0 10 0 0 0 110 0 0 10 0 111 110

整理一下得到新编码:

原编码:0000010000010110010001010110010100011110
新编码:1010010100011001000011000100111110

看!数据成功被压缩。这一段40位长度的内容被压缩到了34位,压缩率是85%。

回顾过程容易发现压缩的秘密:出现频率最多的"B"由一位二进制码“0”来表示,而出现频率较低的"C"和"D",则由长度增加了的三位二进制码来表示。通过合理分配不同长度的编码,肯定可以对数据进行一定程度的压缩。

另外可以证明,霍夫曼树就是此类编码替代的最优化的方案之一。因为假如存在一个字符的出现频率高于另一个字符,而它的变长码长度却长于另一个字符,那么必然可以通过交换两者的位置,使得输出结果的总长度变短。有限次操作后可以达到无法再交换的情况,也就是霍夫曼树规则下的情况。


【内容导航】
 第 1 页:计算机上的压缩过程  第 2 页:进一步思考几个问题

标签:机房 数据压缩 

了不起的IT经理
LecVideo
论坛与活动