查看完整版本: [科普]数据是怎么被压缩的_Winrar[4P]

[科普]数据是怎么被压缩的_Winrar[4P]

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

[b]计算机上的压缩过程[/b]

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

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

假设我们有这么一串20个字母的数据：
[align=center][img]http://news.mydrivers.com/Img/20110630/S03514535.png[/img][/align]

默认情况下，用2位2进制码来表示这四个字母：
[align=center][img]http://news.mydrivers.com/Img/20110630/03510543.jpg[/img][/align]

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

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这四个字符的新的代码：

[align=center][img]http://news.mydrivers.com/Img/20110630/03523652.jpg[/img][/align]

用以上新编码代入原字符串中，得到：

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"，则由长度增加了的三位二进制码来表示。通过合理分配不同长度的编码，肯定可以对数据进行一定程度的压缩。

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

进一步思考几个问题

在压缩文件的时候，人们不禁会产生一些新想法或者遇到一些疑问：是否可以对压缩后的数据再次压缩？当2 n 的n变大后，遇到A：1010，B：10这样的情况，如何解读10101010？

就操作上来说，当然能反复编码，但通过对本文例子中得到的新编码再次操作后会发现，结果是不会有任何变化的。压缩的实质，在于消除特定字符分布上的不均衡，通过将短码分配给高频字符，而长码对应低频字符实现长度上的优化。而数据经过一次压缩后，字符的分布已经几乎平均化了，很难更进一步的压缩了。

而第二个问题描述的情况是不会出现的的。从构造霍夫曼树操作上可以看到，一个字符无法在另一个字符的上层。只要操作正确，就一定可以构造出唯一的代码表，不存在歧义。

还有一个有趣的问题是：虽然把40字节的内容压缩到了34字节，但需要将相应的码表一并发送给接收方（没有对应码表，无法解压）。这不反而使得压缩后的数据比压缩前的还要长？

事实也确实如此。本文例子中，真正的最终结果体积是大于原文的。但这不意味了算法错误。这是因为“n”过小（例子中为2，实际通常为8）导致的。

总长度的不够使得节省出来的那部分容量还不足以弥补码表本身的储存空间。实际应用中，如果你非要去压缩一个只有几个字节的文件，得到的压缩包也经常会大于文件本身。通常，压缩软件会在每压缩4kb到32kb数据后，重新生成并保存一个霍夫曼树。当分块过大时，统计上的整体平均，会掩盖小区域内的极度不平均，损失了压缩的空间。比如存在一个这样的文件：

AAAAA……AAAAA（一万个）BBBBB……BBBBB（一万个）……ZZZZ（一万个）。

如果从整体上进行霍夫曼树操作，将不会产生任何压缩，但是这时候我们把它分成26块，压缩并各自保存相应的重新编码的霍夫曼树，压缩率将非常惊人，约等于12.5%。
[img]http://news.mydrivers.com/Img/20110630/S04040507.png[/img][/color][/size]

晕了，很有技术含量的内容啊。为什么没人回复呢。其实看完这个可以明白为什么文字的压缩率大，视频等压缩率小了，

因为我们都只看懂了一部分,所以外行看门道,就不回复了，但是发帖人辛苦了。

数据的压缩方法是有很多种的，数据的编码方法也是很多的，所以这么小篇幅是说不明白的

好文章，说的通俗易懂，不过huffman编码的缺点是完全没有容错性，一个bit出错整个文件都面目全非

平时用winrar压缩感觉很方便，没想到这后面是如何操作的，今天有了一点了解了。

真正的技术贴，总算了解了一些压缩的常识了，可以用作吹牛的资本了，呵呵

这样的技术帖实在是值得mark之后，再慢慢看。
学而时习之啊！

NB，拥有各自的解码表，以进行自己的压缩。
A文件的“8“极多，“6”极少，就把“8”做成小的压缩（例如“1“）
               ，“6“的压缩很长（例如“０１００１０１”）
Ｂ文件的“６“极多，“８”极少，就把“６”做成小的压缩（例如“1“）
               ，“６”的压缩很长（例如“０１００１０１”）

综合下来，Ａ和Ｂ按此方法压缩后的占地会比传统的方式小。好东西呀

*** 作者被禁止或删除 内容自动屏蔽 ***

其实说到底就是算法的问题，不同类型的文件有不同的特点，最佳的压缩也就必须提供最符合这一类文件的算法。至于说怎样的算法最佳，那就是各人的本事了。

学习了，以前还真不知道压缩软件是怎么工作的。

其实当初学霍夫曼树的时候是真的没有想到原来压缩文件是这么个意思~当时真是都学到狗肚子里去了。

*** 作者被禁止或删除 内容自动屏蔽 ***

技术贴，得好好看看，虽然看得不是很懂，但也大概明白压缩的原理了，学习了

受教了。系统为什么不默认的就用这种存储方式呢。

哦，原来霍夫曼树是这个意思啊，上次看到有片文章提到这个，没搞懂，现在看到楼主的文章，才明白里面所说的霍夫曼树~

好头晕啊，这些数学上的东西真的太变态了，不是常人能玩的

看的都头晕的，楼主厉害的啊，这个都整明白得了。

是不是就是说，在掌握了码表后就可以破译压缩文件或者恢复损害的压缩文件了