你的位置: iPc 首页 > 全部文章 > 编程技术 > 阅读文章
科学X网    Office    苹果中国    微软中国    VPS

电脑上的数据究竟是怎样被压缩和还原的??

02
七月

压缩软件大家想必都不不陌生。甚至是太熟悉而忽略了它的神奇。你有想过为什么压缩软件能把一组数据的体积缩小,并且还能再完整地展开还原吗?多余的体积究竟被藏在了哪里?看完本文,你就知道了……

压缩

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

计算机上的压缩过程

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

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

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

clip_image001

默认情况下,用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这四个字符的新的代码:

clip_image003

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

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%。

clip_image004英语中各字母出现频率示意图

从上面字频图我们知道,在现实的文本中,英语字母使用频率各不相同,而且差别很大。有着很高的不平均度。所以大部分压缩软件对文本文件依然有着很高的压缩率。

关于本文
各种回音
  1. 说: 回复他/她

    沙一个发的

    • 说:

      最後那一萬個A到一萬個Z不知道怎麼分26塊,怎麼壓縮法,前面的倒很容易看懂

  2. 说: 回复他/她

    难道是SF?!!!

  3. 说: 回复他/她

    好文!!!

  4. 说: 回复他/她

    第二。

  5. 说: 回复他/她

    学习了~~

  6. 说: 回复他/她

    知道了如何被压缩,那如何还原,即解压缩呢、

    • 说:

      这还不清楚吗、?

    • 说:

      这。。。

    • 说:

      你是哥。。真的

    • 说:

      确实是个哥,还是传说级的

  7. 说: 回复他/她

    头疼0…0

  8. 说: 回复他/她

    貌似本科毕业设计就是设计压缩解压缩程序,用的就是这个原理

  9. 说: 回复他/她

    那rar、zip等不同的格式是怎么来的?

  10. 说: 回复他/她

    在果壳网看过 = =`

  11. 说: 回复他/她

    嘿嘿,知道这个原理~~

  12. 说: 回复他/她

    太复杂了。。

  13. 说: 回复他/她

    从驱动之家转载的文章么- –

  14. 说: 回复他/她

    前两天刚考完编码,霍夫曼啊霍夫曼。。。

  15. 说: 回复他/她

    哈夫曼树

  16. 说: 回复他/她

    大学c、数据结构、操作系统、计算机组成原理、算法、离散……挂过的童鞋举手

  17. 说: 回复他/她

    大体一看头疼,留个脚印走人

  18. 说: 回复他/她

    猛然间发现,ipc.me的很多文章是抄袭果壳网或者别的网站的…还不注明链接和转载的出处的……

    • 说:

      不是注明的嘛,在最顶上……

    • 说:

      看他的ID就明白了,不用跟他辩解

  19. 说: 回复他/她

    哈夫曼树不错。。。

  20. 说: 回复他/她

    正好学到了这个。

  21. 说: 回复他/她

    看懂一点!

  22. 说: 回复他/她

    看 不懂

  23. 说: 回复他/她

    真是好文,学习了

  24. 说: 回复他/她

    好像懂了点,又好像不懂

  25. 说: 回复他/她

    赫夫曼编码,数据结构里学的。网络通信,不会出现重码。没想到还能这么用

  26. 说: 回复他/她

    赫夫曼编码,数据结构里学的。网络通信,不会出现重码。没想到还能这么用。

  27. 说: 回复他/她

    貌似最近有很多新童鞋来这里围观诶,但是好像都不知道引用链接在哪里却自以为是地吠那么两下呢,来这里多少要了解一下这里的文章结构嘛。。。

  28. 说: 回复他/她

    我是来打酱油的···

  29. 说: 回复他/她

    真犀利…我看懂了…但我不会编程…仅仅学习

  30. 说: 回复他/她

    又受教了

  31. 说: 回复他/她

    学习

微博评论箱