现在的位置: 首页 > 菲菲文章 > 学习交流 > 正文

压缩原理【转】

2005年12月16日 学习交流 ⁄ 共 4338字 ⁄ 字号 暂无评论 ⁄ 阅读 13,973 次

声明:本文内容代表作者本人的技术水平及观点,错讹之处概不负责,并谢绝篡改。

提起压缩,大家都会想到WINZIP或者RAR之类的压缩软件,实际上,电脑压缩技术的内涵和应用绝不止于此。我们能够在在电脑上欣赏到精美的电影和悦耳的歌曲,压缩技术立下了汗马功劳。在今天互联网的传送速度远不能满足我们需要的时候,网络压缩技术也显得特别重要。正是有了它,我们才得以实现网络视频/音频的即时传送。压缩技术,在不知不觉中改变着我们的生活。

【预备知识】二进制与ASCII编码

电脑里基本的存储单位是字节。ASCII码是一种以字节为单位对常用符号进行编码的方案,因其合理性而较为流行。因为一个字节有8位,所以ASCII最多可对2^8=256个字符进行编码,其中前128个称为标准ASCII码(二进制编号00000000-01111111),后128个称为扩展ASCII码(二进制编号10000000-11111111),电脑里的汉字就是利用两个扩展ASCII码的组合来实现的(GB2312汉字编码方案)。比如汉字“王”占用的两个ASCII编码分别是205和245,十六进制表示是CD和F5,化为二进制就是11001101和11110101。也就是说,在电脑处理“王”这个汉字时,电脑里的信息是“1100110111110101”这样一串数字。再如大写的英文字母“A”的ASCII编码是65,十六进制表示是41,在电脑里的信息实际上是“01000001”。

【缩位压缩】

知道了上述原理后,我们来介绍“缩位压缩”的原理。“缩位”,就是缩减编码里没有必要使用的“位”。例如文件里一个汉字也没有,也就是说内容中没有使用扩展ASCII码,这样所有字符编码的第七位(最前面那一位)将都会是0。利用这一点我们就可以缩掉这一位,假设文件内容是ABCDEFGH。

    文件内容: ABCDEFGH

    二进制内容:01000001 01000010 01000011 01000100 01000101 01000110 01000111 01001000

    压缩后文件内容: [该内容中文状态下显示是乱码,故无法写出]

    二进制内容:10000011 00001010 00011100 01001000 10110001 10100011 11001000

    这个压缩过程就是将原来顶头的0全部去掉后每8位重排,这样原来占用8个字节的文件就只占用了7个字节。只要解压时再加上第七位的0,文件就可以恢复原样。这一压缩技术特别适用于对数字的压缩。因为0~9这十个阿拉件数字占用的ASCII编码是从00110000-00111001,其前四位全部都是“0011”。

【直接压缩】

直接压缩的原理最易理解,因为有些时候,文件里不可避免地存在着连续同样的字符,比如在文件末尾加了一行“※※※※※※※※※※※※※※※※※※※※※※”符号。这样的话,压缩时可以只记住这个符号以及重复的次数,就可以迅速还原。

【字典压缩】

字典压缩是最重要的一种压缩技术,也是应用最为广泛的一种压缩技术。该技术搜索文件中重复出现的字符串,如“中华人民共和国”、“改革开放”等,记录后(记录后的内容被称为“字典”)在正文中使用另一个简短的编码来代替它。想一想Windows系统里充满了多少的“Windows”和“Microsoft”这些字符,你就会明白为什么这种压缩技术对Windows操作系统如此有效了。这种压缩方案对政治稿件和学术论文特别适用。

字典压缩技术无论对文本文件还是可执行的代码文件都同样高效,而且可以涵盖掉“直接压缩”技术。现在流行的ZIP,ARJ、RAR,AIN等压缩软件都采用了此项技术。但是此种技术中,合适的字典长度很重要,将字典设得太大或太小都严重影响压缩效果,且进行压缩时速度相对较慢。

多数压缩软件综合使用各项压缩技术。

【矢量压缩】

虽然字典压缩强劲有力,但是对有些文件内容还是无能为力,比如下面的内容:

啊雹玻长触郸锭法

这些看起来不成文的汉字实际上却有着内在的联系,它们分别是GB2312编码中的第1601、1702、1803、1904、2005、2106、2207、2308区位的汉字。对于这种情况,可以通过寻找它们之间的数学联系(如数列、方程等)进行记忆式的压缩。这种记忆式的压缩叫做矢量压缩,是一种正在兴起的新压缩技术。

矢量压缩有时可以带给我们意想不到的享受。很多人惊奇于FLASH能以如此小的体积带给我们如此丰富的信息,就是因为FLASH里使用了矢量压缩技术。使用方程记忆一个点的运动轨迹远比记忆这个点的所有位置信息量要小得多的多。但另一面,对于照片和录音这些资料,现在的矢量化技术还做不到从中找到即高保真又有规律的方案来,所以下一种压缩技术有了大显身手的空间。

【有损压缩与VCD】

VCD的产生要归功于联合图象专家组(JPEG)的努力。他们提出了一种全新的压缩技术标准,也可以说是一种全新的压缩概念。这种概念催化了运动图象专家组(MPEG)标准的诞生及VCD工业化的实现。JPEG图象压缩技术以图象的每8*8个点的点阵做为一个处理单元,在这个范围内,如果全部都是某一色彩而只有极个别的其他色彩,那么其他色彩将被忽略。这种压缩技术理论上的压缩比高达为64:1,一个64MB的文件现在只需1MB就可以了?这实在很令人心动。为了进一步扩展压缩效果和提高该技术的适应范围,JPEG做了灵活调整。允许用户自行设置处理单元的大小和忽略其他色彩的程度,这也就是为什么JPEG图像有“质量”属性的原因。

JPEG提出的这种“有损压缩”的概念使得该压缩技术有一定的局限性,比如说,JPEG不适合用来压缩工程图纸、医学影像等等资料。但其注重实用性的思路却大大启发了人们,RealPlayer就是沿着这条路率先实现了网上视频的实时播放。而VCD中剥离了图象的声音则也渐渐形成了流行的MP3音乐。(声音压缩的编码方案过于繁杂,本文未予论述)

【压缩文件缝隙】

除这些压缩技术之外,DOS/Windows系统本身也留给了大家一个压缩的故事。在DOS/Windows系统下,磁盘存储空间被划分成一小块一小块地使用,而不是象UNIX或者Novell那样在系统控制下所有文件都搅和在一起。这种开放式的磁盘文件使用格式虽然不安全(简直毫无安全可言),但是效率高,易操作。这可能也是DOS/Windows在家用和商用市场打败UNIX和Novell但在服务器领域却始终比不上他们的一个重要原因。——因为每个分配块只能供一个文件使用,所以即使文件(或文件的最后一块)只有一个字节,也必须占用一个分配块。因为当时只留了两个字节来分配这种存储块(两个字节是16位,这种分配机制叫做FAT16),所以不论分区有多么大,最多都只能被分为2^16=65536个分配块。比如说一个2GB的分区,其分配块大小是32KB;当分区超过2GB时,分配块将不得不增长到64KB。想一想,如果一个字节的文件也要占掉你的64KB时,你能够不恼火?所以从Windows 95 OSR2版本开始,Microsoft推出了FAT32解决方案。但是即使如此,“文件缝隙”依然存在。

Microsoft为了解决文件缝隙,曾在DOS 6.0时代推出过Double Space(DBLSPACE),后来改为DRVSPACE,这东西在Windows 95/98/ME上还依然存在。当时号称可以倍增硬盘容量,令大家激动不已,但是尝试过后高呼上当。原来Microsoft只不过是抄袭他人,使用了“虚拟卷”技术而已,该技术顶多可以省掉文件缝隙,对于整盘只放了一个大文件的用户来说简直毫无用途。

压缩文件缝隙现在有了一个较好的办法,那就是把不常用的文件用WINZIP打成一个包,尤其是大量的小文件和/或在FAT16的环境下,使用这一方法可以节省你很多的磁盘空间。但是无论如何,“文件缝隙”看来要在Windows系统中永远存在了。

【越压越大?】

文件会越压越大么?答案是:会的。因为压缩文件需要一个控制解压缩的文件头(文件格式及字典等),所以对已经“无以为压”的文件进行压缩时,将徒增一个文件头,文件当然会越来越大。另外,虽然压缩后的文件更省空间,更安全了(压缩文件可以加密而普通文本文件不行),但是如果一旦文件头损坏,整个文件将无法解压。所以压缩文件的文件头是很重要的。这跟刚才讲过的FAT格式与UNIX/Novell卷格式的差别比起来,倒是有相形之处。但如果大家的ZIP文件损坏,建议试一下DOS版的ZIP解压程序PKUNZIP,也许还可以解救一部分。

【可执行文件的压缩】

不但文档文件和数据文件可以压缩,可执行文件也可以进行压缩。致力于压缩技术的PKWARE Inc.公司在最早推出PKZIP软件时(大约是1990年的事情),就有三个主要程序,分别是PKZIP.EXE(压缩时用)、PKUNZIP.EXE(解压缩时用)和PKLITE.EXE(压缩可执行文件时用)。压缩可执行文件的过程很神奇,文件名并不会被改变,只是长度会变小。这样的压缩文件在执行时,会在内存中自我释放,然后重定位重加载再执行。因为电脑做起来是一瞬间的事情,所以几乎感觉不到文件被压缩过。在软盘盛行的时代,这个工具十分有用。

Windows下的程序现在是越来越大了,所以很多编程人都将自己的主程序进行压缩,一方面也可以起到防盗版的作用,著名的“Red Alert”就采取了这样的做法。随着互联网传播软件功能的发挥,很多软件被打包为可执行程序,点击后可以自行展开并进行安装,这些也都是可执行文件的压缩的例子。

【压缩技术的辨证分析】

站在历史的观点上分析,压缩技术是必然要灭亡的。我们现在看10前年的DOS时代,当时为了存储目的而实施的压缩工作现在已经淹没在海量的存储设备容量里。从理论上讲,压缩毕竟浪费了我们的时间与精力,如果存储空间足够,我们没有需要压缩的理由。考察现在的压缩目的,除了小部分是为了方便检索之外,目前大量的压缩是为了适应互联网慢吞吞的传送速度。那么,当网速能够满足我们随时将整个硬盘上的内容在网络上拖来拖去时,我们还需要压缩吗?当光盘的容量足够大时,我们还会容忍JPEG技术替我们扔掉那一两个色点吗?

但是哲学指导我们,事情总是在发展,总是有其另一面的特性,当容量不再成为压缩的目的时,传送成了我们压缩的另一个目的。又有谁能够预料,下一个压缩的目的会不会产生,而又将是什么呢?(全文完)

联想电脑

王云涛

二○○一年三月十四日

版本 1.0

该文章知识产权属作者个人,请勿篡改!转载亦请保留作者姓名、单位、著作日期及版本。

作者授权任何人可以在任何时候做合法的非商业性转载并感谢您的传播,但务请告知作者。

菲菲更名宝贝


【下篇】

菲菲更名宝贝

给我留言

留言无头像?


QR Code Business Card