在世界上的大多数语言中,某些字符或单词经常以相同的模式一起出现。正是由于这种高冗余性,而导致文本文件的压缩率会很高。通常,大小合适的文本文件的压缩率可以达到50%或更高。大多数编程语言的冗余度也很高,因为它们的命令相对较少,并且命令经常采用一种设定的模式。对于包含大量不重复信息的文件(如图像或MP3文件),则不能使用这种机制来获得很高的压缩率,因为它们不包含重复多次的模式。
如果文件有大量重复模式,那么压缩率通常会随着文件大小的增加而增加。此外,文件压缩效率还取决于压缩程序使用的具体算法。有些程序能够在某些类型的文件中更好地寻找到模式,因此能更有效地压缩这些类型的文件。其他一些压缩程序在字典中又使用了字典,这使它们在压缩大文件时表现很好,但是在压缩较小的文件时效率不高。尽管这一类的所有压缩程序都基于同一个基本理念,它们的执行方式却各不相同。
大多数计算机文件类型都包含相当多的冗余内容——它们会反复列出一些相同的信息。文件压缩程序就是要消除这种冗余现象。与反复列出某一块信息不同,文件压缩程序只列出该信息一次,然后当它在原始程序中出现时再重新引用它。以下使用案例进行说明。
前美国总统肯尼迪(John F.Kennedy)在1961年的就职演说中曾说过下面这段著名的话:“Ask not what your country can do for you——ask what you can do for your coun-try.”(不要问国家能为你做些什么,而要问自己能为国家做些什么。)
这段话有17个单词,包含61个字母、16个空格、1个破折号和1个句点。如果每个字母、空格或标点都占用1个内存单元,那么文件的总大小为79个单元。为了减小文件的大小,我们需要找出冗余的部分。
可以发现:如果忽略大小写字母间的区别,这个句子几乎一半是冗余的。9个单词(ask、not、what、your、country、can、do、for、you)几乎提供了组成整句Ask not what your country can do for you——ask what you can do for your country话所需的所有东西。为了构造出另一半句子,我们只需要拿出前半段句子中的单词,然后加上空格和标点就行了。
大多数压缩程序使用基于自适应字典的“LZ算法”来缩小文件。“LZ”是指此算法的发明者Lempel和Ziv,这里的“字典”是指对数据块进行归类的方法。
排列字典的机制有很多种,也可以像编号列表那样简单。在检查肯尼迪这句著名讲话时,可以挑出重复的单词,并将它们放到编号索引中,然后直接写入编号而不是写入整个单词。(www.xing528.com)
因此,如果我们的建立字典:1—ask,2—what,3—your,4—country,5—can,6—do,7—for,8—you。
上面的句子现在就应该是这样的:1 not 2 3 4 5 6 7 8——1 2 8 5 6 7 3 4。
如果这种机制,那么只需使用该字典和编号模式即可轻松重新构造出原始句子。这就是在展开某个下载文件时,计算机中的解压缩程序所做的工作。用户可能还遇到过能够自行解压缩的压缩文件。若要创建这种文件,编程人员需要在被压缩的文件中设置一个简单的解压缩程序。在下载完毕后,它可以自动重新构造出原始文件。
但是使用这种机制究竟能够节省多少空间呢?“1 not 2 3 4 5 6 7 8——1 2 8 5 6 7 3 4”当然短于“Ask not what your country can do for you——ask what you can do for your country.”,但应注意的是,我们需要随文件一起保存这个字典。
在实际压缩方案中,计算出各种文件需求是一个相当复杂的过程。让我们回过头考虑一下上而的例子。每个字符和空格都占用1个内存单元,整个原句要用79个单元。压缩后的句子(包括空格)占用了37个单元,而字典(单词和编号)也占用了37个单元。也就是说,文件的大小为74个单元,因此我们并没有把文件大小减少很多。
但这只是一个句子的情况。可以想象,如果用该压缩程序处理完肯尼迪讲话的其余部分,我们会发现各种单词重复的情况。为了得到尽可能高的组织效率,可以对字典进行重写。
注意,在使用压缩文件之前必须解压,如果试图使用文字处理软件打开某被压缩的文件,只会看到一堆乱码。通常,文字处理软件甚至不会打开这种文件,相反会显示一个错误信息,说明此种文件类型(含有.zip扩展名)不能打开。看到这种信息,就应该想到应该先把它解压缩。
免责声明:以上内容源自网络,版权归原作者所有,如有侵犯您的原创版权请告知,我们将尽快删除相关内容。