信息论大论文(共20页)

1、7z文件格式研究第 页7z文件格式研究(ynji)目 录 TOC o 1-3 h z u HYPERLINK l _Toc410305272 7z文件格式研究 PAGEREF _Toc410305272 h 1 HYPERLINK l _Toc410305273 摘 要 PAGEREF _Toc410305273 h 3 HYPERLINK l _Toc410305274 第一章 背景介绍 PAGEREF _Toc410305274 h 4 HYPERLINK l _Toc410305275 1.1 压缩软件 PAGEREF _Toc410305275 h 4 HYPERLINK l _Toc

2、410305276 1.2 7z文件格式 PAGEREF _Toc410305276 h 4 HYPERLINK l _Toc410305277 1.3 7-ZIP软件 PAGEREF _Toc410305277 h 4 HYPERLINK l _Toc410305278 第二章 主流压缩算法 PAGEREF _Toc410305278 h 6 HYPERLINK l _Toc410305279 2.1 主流压缩算法简介 PAGEREF _Toc410305279 h 6 HYPERLINK l _Toc410305280 2.2 熵编码算法 PAGEREF _Toc410305280 h 6

3、 HYPERLINK l _Toc410305281 2.3 游程编码算法 PAGEREF _Toc410305281 h 7 HYPERLINK l _Toc410305282 2.4 字典压缩算法 PAGEREF _Toc410305282 h 8 HYPERLINK l _Toc410305283 2.5 当前常用的压缩算法 PAGEREF _Toc410305283 h 9 HYPERLINK l _Toc410305284 第三章 7-ZIP软件工作流程 PAGEREF _Toc410305284 h 10 HYPERLINK l _Toc410305285 3.1工作流程 PAGE

4、REF _Toc410305285 h 10 HYPERLINK l _Toc410305286 3.2 Floder概念 PAGEREF _Toc410305286 h 12 HYPERLINK l _Toc410305287 3.2 7z文件格式解析 PAGEREF _Toc410305287 h 13 HYPERLINK l _Toc410305288 第四章 7-ZIP软件实现 PAGEREF _Toc410305288 h 17 HYPERLINK l _Toc410305289 4.1新算法的加入 PAGEREF _Toc410305289 h 17 HYPERLINK l _To

5、c410305290 4.2算法加入前后压缩性能的对比 PAGEREF _Toc410305290 h 17 HYPERLINK l _Toc410305291 第五章 结论 PAGEREF _Toc410305291 h 19 HYPERLINK l _Toc410305292 参考文献 PAGEREF _Toc410305292 h 20摘 要随着(su zhe)信息技术产业的高速发展，数据的本身的质和量都在不断地变大，由此，对数据压缩和打包的需求(xqi)也与日俱增；同时，数据安全性要求不断地提高。压缩软件进入了人们的视野。现如今，压缩软件已经成为每台智能设备上必备的软件(run jin

6、)之一。而7z是一种可以使用多种压缩算法进行数据压缩的档案格式。因此，本人在学习了压缩编码的基本知识的基础上对压缩软件进行了相关的研究。本人通过解读7-ZIP压缩软件源码、研究了7z文件的结构，了解了7-ZIP软件的工作原理，并在在7-ZIP软件中添加了PAQ压缩算法，进一步提升7-ZIP的工作性能。并对改进后的软件进行了性能分析。第一章 背景(bijng)介绍1.1 压缩软件压缩软件，通常也称为解压缩软件。是实现文件流的压缩、解压缩、加密、解密功能的应用软件。现阶段，压缩软件已经成为每个智能(zh nn)设备的标配软件。现如今的压缩软件都配上了丰富(fngf)的图形界面。当前常用的压缩软件主

7、要有WinRAR、WinZip、好压、快压、360压缩以及7-ZIP压缩等软件。由于动辄上百G甚至上T的硬盘普及和宽带网络时代已经到来，压缩软据软件的实质的压缩性能也就显得不那么重要了。压缩软件之所以现在依旧流行，是因为其归档技术，就是将数量众多的小文件可以聚合成为一个较大的文件，这样在互联网中进行传输的时候会更加方便。而且现在的压缩软件都逐步加入云功能，实现云备份。但是，本文的研究重点仍旧放在了压缩文件的压缩和解压特性上。1.2 7z文件格式7z文件指的是一种后缀名为.7z的文件。7z 文件格式严格的说是一种打包(Archive)的格式, 它规定了打包的方法。同时也采用了无损压缩算法，其中7

8、z默认的压缩算法是LZMA算法。7z格式是开源且具备模块化的组件结构，这就使得第三方可以使用任何压缩，转换或加密算法，而不需要得到软件开发者的许可。当前许多公司开发的压缩软件都是在7z的源码基础上进行适当的更改而得到的。7z格式还具有最高的压缩比，并且其配置了强大的AES-256加密算法，这使得7z格式无论在性能上还是安全性上都具有非常好的利用价值。而且用户可以随意更改和配置压缩的算法，使得其灵活度大大提升。并且7z支持多线程压缩，使得其具有更高的CPU利用率。1.3 7-ZIP软件(run jin)7-ZIP是一款有极高压缩比的开源(ki yun)压缩软件，大多数源代码都基于(jy) GNU

9、 LGPL 许可协议下发布，可任意使用。这就使得很多开发者可以使用7-ZIP的源码进行二次开发，从而使得市场上有着较多的性能高并且免费的压缩软件。7-ZIP软件不仅仅能对7z格式进行压缩和解压，同时也可以对多种其他的压缩格式进行压缩和解压，比如ARJ，CAB，CHM，CPIO，DEB，DMG，HFS，ISO，LHA，LZH，LZMA，NSIS，RPM，RAR，SPLIT，SWM，TBZ，TBZ2，TGZ，TPZ，VHD，WIM，XAR，Z格式。由于该软件开源，所以开发者可以任意修改其源码，使其支持更多的格式，实现更多的功能。7-ZIP默认使用了LZMA与LZMA2算法，这就使得其具有极高的压缩

10、比。通过实际的数据可以得到，对于 ZIP 及 GZIP 格式，7-Zip 能提供比使用 PKZip 及 WinZip 高 2-10% 的压缩比。具体测试结果如表1：软件名称Mozilla FirefoxGoogle Earth65 个文件85 280 391 字节483 个文件110 700 519 字节压缩后压缩比压缩后压缩比7-Zip 9.35-mx39 357 375100%15 964 369100%WinRAR 5.20-m5 -s -ma5 -md128m41 789 543106%17 035 432107%表 SEQ 表 * ARABIC 1而且7-ZIP本身就提供了完善的AE

11、S-256加密算法，并提供了完整的加密解密框架，可以使得第三方开发者进行二次开发。由于7-ZIP是开源软件，因此，7-ZIP软件不能仅仅能在Windows平台下使用，在Linux和Unix平台下都有较好的兼容性。本人(bnrn)通过阅读7-ZIP源码，了解7z文件格式，理解(lji)了7-ZIP的工作流程，然后向7-ZIP中加入新的压缩算法，进一步提升7-ZIP软件的工作性能。第二章 主流(zhli)压缩算法2.1 主流压缩算法简介对于压缩软件来说，无论其实现多么复杂的功能，其核心仍旧是压缩算法。现阶段主要有两种压缩算法：有损压缩算法和无损压缩算法。有损压缩算法通过移除在保真情形下需要大量的数

12、据去存储的小细节，从而使文件变小。在有损压缩里，因某些必要数据的移除，恢复原文件是不可能的。有损压缩主要用来存储图像和音频文件，同时通过移除数据可以达到一个比较高的压缩率，由于压缩软件要保证数据的完整性，因此本文不讨论有损压缩算法。无损压缩算法，也使文件变小，但对应的解压缩功能可以精确的恢复原文件，不丢失任何数据。无损压缩算法被广泛的应用在计算机领域，从节省电脑的空间，到通过web发送数据，都在使用无损压缩算法。无损压缩算法可行的基本原理是，任意一个非随机文件都含有重复数据，这些重复数据可以通过用来确定字符或短语出现概率的统计建模技术来压缩。统计模型可以用来为特定的字符或者短语生成代码，基于它

13、们出现的频率，配置最短的代码给最常用的数据。这些技术包括熵编码、游程编码以及字典压缩。下面就分别介绍这几种主流的无损压缩算法。2.2 熵编码算法数据压缩中，平均来说为了表示一个字符或短语，熵编码意味着所需要的最少比特数。一个基本的熵编码编码器包括一个分析模型以及一套编码。输入文件被解析，并产生一个由字符出现概率组成的统计模型。然后，编码器可以利用该统计模型去决定该给每一个字符多少个比特，从而使得最常用的字符用最短的编码，反之最不常用的字符用最长的编码1。其中(qzhng)最早的熵编码是Shannon-Fano编码，该压缩编码于1949年由Claude Shannon和Robert Fano发明

14、。这个技术的其中一个(y )步骤是产生一个代表字符出现概率的二叉树。字符以这样一种方式排序，出现得越频繁的字符越靠近树的顶端，越不常见的越靠近树的底部。产生Shannon-Fano编码(bin m)的步骤如下1:1.解析输入，统计每一个字符出现的频率。2.根据是上述频率计算字符的概率。3.依据概率对字符降序排序。4.为每一个字符生成一个叶节点。5.把字符列表分为左右两部分，使得左边的概率与右边的概率大致相当。6.左节点加编码”0”，右节点加编码”1”。7.对两棵子树重复的步骤5和6，直到所有的字符节点都成为叶子节点。由于二叉树是自下而上构建的，因此Shannon-Fano编码不总是能够产生最优

15、的编码。由于这个原因，使用的较多的还是对于任意输入都能够得到最优编码的Huffman编码。Huffman编码也是一种熵编码，其二叉树是自上而下构建的，因此其能产生最优编码。但是如果单论压缩比，Huffman算法并不是最优的压缩算法，算术编码算法确实是一个最优的熵编码技术，通常压缩比方面算术编码要比Huffman编码表现得更好。然而，它却也比其它技术复杂得多。算术编码不像熵编码把字符概率构建成一棵树，算术编码把输入转化为一个0到1之间的有理数，输入字符的个数记为基底，里面每一个不同的字符都分配一个零到基底之间的值。然后，最后转化为二进制得到最终的结果。结果也可以通过把基底恢复为原来的基底值，替换

16、为对应字符而得到原输入值。2.3 游程(yu chn)编码算法游程编码是一个非常简单的压缩技术，把重复出现的多个字符替换为重复次数外加字符。单个字符次数为1。游程编码非常适合数据重复度比较高的数据，同一行有很多像素颜色(yns)相同的渐进图片，也可以结合BWT等其它技术一起使用。BWT算法是1994年发明的技术，目的是可逆的处理(chl)一段输入数据，使得相同字符连续出现的次数最大化。BWT自身并不做任何的压缩操作，仅简单地转化数据，让游程编码压缩算法可以更有效的编码。BWT算法的步骤:1.创建一个字符串数组。2.把输入字符串的所有排列组合塞入上述字符串数组。3.按照字符顺序为字符串数组排序。

17、4.返回数组的最后一列。2.4 字典压缩算法字典压缩算法中最早的算法是LZ77算法。LZ77算法发表于1977年，是名副其实的字典压缩算法开山之作，相较于当时的几个主要压缩算法，压缩比都有非常明显的提高。但是LZ77还是使用窗口方法生成字典。LZ78于1978年由Lempel和Ziv发明，缩写正是来源于此。不再使用窗口方法来生成字典，输入数据要么被预处理之后用来生成字典，或者字典在文件解析过程中逐渐形成。LZ78采用了后者。字典的大小通常被限定为几兆的大小，或者所有编码上限为几个比特，比如8个。这是出于减少对内存要求的考量。算法如何处理正是LZ78的各个衍生算法的区别所在。但是LZ78有版权的

18、限制，所开发的软件大都是收费软件因此采用这种方法的软件并没有很流行。LZ78算法解析文件的时候，把新碰到的字符或者字符串加到字典中。针对每一个符号，形如字典索引以及未出现在字典中的符号的字典记录会对应地生成。如果符号已经存在于字典中，那么将从字典中搜索该符号的子字符串以及其后的其它符号。最长子串的位置即为字典索引。字典索引对应的数据被设置为最后一个未知子串。如果当前字符是未知的，那么字典索引设置为0，表示它是单字符对。这些数据对形成一个链表数据结构。这样就是字典的形成过程以及数据结构。其他算法过程和LZ77算法类似。字典压缩算法在此之后就迅速流行起来，依据LZ77以及LZ78算法为模板，很多字

19、典压缩算法被开发出来，同时字典压缩算法也成为了当今(dngjn)最主流的压缩算法。在此之后，陆续出现(chxin)了LZR算法、DEFLATE/ DEFLATE64算法、LZSS算法、LZH算法、LZB算法、ROLZ算法、LZP算法、LZRW1算法、LZJB算法、LZS算法、LZX算法、LZO算法、LZMA/LZMA2算法、LZMW算法、LZW算法以及LZJ算法等算法。2.5 当前(dngqin)常用的压缩算法基于DEFLATE算法的gzip格式，同时使用了LZ77算法与Huffman 编码算法的一个无损数据压缩算法。除了用于PNG和ZIP格式之外， DEFLATE算法也被频繁的用在其它地方。

20、例如gzip(.gz)文件格式也使用DEFLATE，gzip是ZIP的一个开源版本。其它还包括HTTP, SSL, 以及其它的高效压缩网络传输数据的技术2。LZMA以及LZMA2这两种算法基本上和LZ77算法是相同的，只不过它操作的是面向比特级别，而非传统上的面向字节级别，用于解析数据。LZMA2优化了多线程的调度，优化了算法的执行速度，并且在压缩效果上有一定程度的提升2。 PAQ于2002年由Matt Mahoney发明，是老版PPM的一个改进版。改进的方法是使用一项叫做context mixing的革命性技术。Context mixing是指智能地结合多个(PPM是单个模型)统计模型，来做

21、出对下一个符号的更好预测，比其中的任何一个模型都要好。这也使得PAQ算法是当前压缩比最高的算法2。bzip2是BWT算法的一个开源实现。它的操作原理很简单，不过却在压缩比和速度之间达到了一个平衡。首先，使用了一个游程编码器，接下来，BWT算法加入进来，然后，使用BWT算法中的转移方法以达到产生大量相同符号的目标，为接下来的另一个游程编码算法做准备。最后结果用Huffman编码，将一个消息头与其打包3。第三章 7-ZIP软件工作(gngzu)流程3.1工作(gngzu)流程(lichng)在7z的压缩过程中，一个非常核心的概念就是coder。一个coder代表一个算法，通常是指一个压缩或解压算法

22、(也包括过滤算法和加密算法等)。例如，在7z中LZMA算法就是一个coder，DEFLATE算法也是一个coder。7z中用于加密的AES256算法也是一个coder。其处理方法如图1：图 SEQ 图 * ARABIC 1这就是单独的一个coder的工作(gngzu)流程，其中文件流的生成是由7-ZIP软件(run jin)在预先就已经做好了的。通常来讲，一个coder只能处理一个输入流，并且只有一个输出流。比如把一个文件流压缩成一个输出流。但是，7z中有的coder可以把一个输入流处理成多个(du )输出流，反过来也可以把多个流处理成一个流。比如7z的BCJ2 coder，它是一个过滤cod

23、er，可以把一个exe文件过滤成四个输出流。这样的话, 7z的coder概念得到了扩展。就是可能同时处理多个输入流，并且可能输出多个流:图 SEQ 图 * ARABIC 2下面就介绍7-ZIP软件的具体工作流程了（以LZMA算法为例）：将文件流交给LZMA算法进行压缩，如图3：图 SEQ 图 * ARABIC 3多个(du )coder进行级联，由熵理论，多个压缩(y su)coder级联是没有意义的，这样不会大幅提高压缩率，反而会增加计算成本，通常coder的级联是与加密coder进行的级联，如图4所示：图 SEQ 图 * ARABIC 4这样，一次完整的7-ZIP软件按的压缩过程就已经(y

24、 jing)结束了。对于解压来所，是压缩过程的一个逆过程。3.2 Floder概念实际上，7z概念上最小的压缩单位不是文件, 而是FOLDER，它会先把所有的文件都归到一个相应的FOLDER中，然后让这个FOLDER作为文件流，流过若干个Coder。 对于7-ZIP中的FOLDER要特别注意，它不是我们通常指的文件夹。它也不是任何物理上存在的东西。7z在开始压缩之前，会把文件分类，大体上是按文件类型以及文件是否需要加密来分类的。比如说，把所有的exe文件分成一类(一个FOLDER), 或者把所有需要加密的文件分在一起。这个分类方法并不重要, 用户可以自己定义FOLDER的分类方法，7z的实现用

25、的方法比较简单。用户可以给每个文件划分成一个FOLDER。假设(jish)有五个文件a.exe、b.exe、c.dll、a.txt、b.txt需要(xyo)压缩，具体的压缩流程(lichng)如图5所示：图 SEQ 图 * ARABIC 5其压缩流程主要分为两步：1. 首先，通过一定的分组方法，我们分成了两个FOLDER，第一个FOLDER包括: a.exe, b.exe 和 c.dll 三个文件。第二个FOLDER包括:a.txt和b.txt。2. 对FOLDER1来说，它包含三个文件，FOLDER1就简单的把三个文件串联起来，当做一个大文件，作为输入流 i1 给Coder1 用。 后面的过

26、程就就是上面的图5的内容了。3.2 7z文件格式解析7z文件的总体结构，总共分为了三个部分。首先是前文件头；然后是压缩数据；最后是尾文件头。具体格式如图6所示：图 SEQ 图 * ARABIC 6首先(shuxin)是前文件头，前文件(wnjin)头是32个字节定长的。前文件头其实记录的信息很少, 它的主要目的(md)是记录尾文件头的位置，压缩信息的主要结构都是存在尾文件头中。前文件头开头是固定的6个字节的值, 前两个字节的值是字母 7 和z的ascii值。后面四个字节是固定的: 0 xbc， 0 xaf, 0 x27, 0 x1c。然后是两个字节的版本号,之后是四个字节的UINT32的值,

27、对于这四个字节来说，由于7z的所有数据都是采用小端在前的存储, 所以这四个字节的实际存储顺序是低位字节在前面, 高位字节在后。后面的所有数据都是这种结构, 所以以后就不再强调了。这4个字节是剩下的20个字节的CRC校验值。最后这20个字节，先是8个字节的UINT64的值, 它记录的是尾文件头与前文件头的距离, 这个距离是不算前面这32个字节头的, 也就是抛开前面32个字节开始计数的(7-ZIP软件通过读取这个值,然后从第33个字节开始直接跳过这个距离，就可以找到尾文件头了)。 然后是8个字节的值, 记录了尾文件头的大小(解压的时候, 通过这个值就能读出尾文件头的长度了)。最后还有4个字节的值,

28、 它也是一个Crc校验值，是整个尾文件头的校验值。压缩(y su)数据就是数据流压缩过后的FOLDER的数据。7-ZIP会把文件(wnjin)压缩成若干个包, 这里(zhl)就是按顺序存储这些包的。每个包的位置和大小信息都会记录在尾文件头中，解压的时候就会从这里读出包，然后解压出来。尾文件头是7z格式中最重要的部分，其存储了压缩文件每个包的信息，包括采用的压缩算法，加密算法，FOLDER的结构等信息。对于尾文件头，采用了两种的生成方法。第一种方法，就是把尾文件头的内容直接写在后面， 不做任何处理。这种方式最简单，但是却最不常用。因为当用户要压缩大量的文件，尾文件头里面就会有大量的空间用来存储文

29、件名，文件大小，文件时间等等。通常这些信息很多，而且重复信息特别多。对于这些简单的文本信息，其可压缩性非常强。换句话说，这些信息的压缩比比较大。第二种方法，把原始的尾文件头信息用LZMA算法再压缩一次。这样可以显著的减少尾文件头的大小，尤其是在大量文件的时候。其形成的文件如图7所示：图 SEQ 图 * ARABIC 7尾文件头压缩的思路，就是把原始的尾文件头数据当做一个单独的文件流来进行一次前面的压缩过程。就是重复一次前面的7z的压缩过程。不过这一次只有一个文件，因此只划分一个FOLDER。而且压缩方法是指定的LZMA。也就是说只有一个Coder参与。当然，原始尾文件头的内容可能有敏感信息。

30、比如里面的文件名等等信息。因此，7z也提供能力在压缩尾文件头的时候同时加密它。所以压缩尾文件头的时候如果选择加密头信息，则会加入AES加密。其具体工作流程如图8所示：图 SEQ 图 * ARABIC 8这种处理的优点是，可以直接通过加密的方式把文件结构隐藏，在第三方不知道密码(m m)的情况下，如果选择加密文件头，是无法看到整个压缩文件的文件结构的，这一点ZIP是做不到的。第四章 7-ZIP软件(run jin)实现4.1新算法(sun f)的加入本章(bn zhn)主要介绍本人通过查阅相关资料阅读相关代码从而将PAQ算法加入到了7-ZIP软件中去了。前面已经介绍过了PAQ算法的实现原理了，根

31、据GPL开源协议，PAQ算法是开放源码的。因此本人将已经开源的PAQ算法的源码加入到了7z-ZIP软件中。在整体的压缩流程上与原7z-ZIP软件是一样的。具体测试数据见4.2。4.2算法加入前后压缩性能的对比本章将7z-ZIP自带的LZMA算法，PPM算法，BZIP2算法以及后嵌入的PAQ算法对同一文档进行压缩，通过比较其压缩后的大小与压缩前的大小进行比较，可以检测改进的算法在文件压缩中是否有性能提升的作用。这些软件所选取的测试平台均为Windows 7 32bit，处理器为i7 2860qm 2.5GHz，内存为2GB。选取Python27这个包含了很多文件的文档进行压缩，该文档包含4802 个文件，205 个文件夹，其中大部分是小文档，exe程序。经过三种压缩算法进行压缩后，得到结果如图 SEQ 图 * ARABIC 9所示。图 SEQ 图 * ARABIC 10 压缩后对比图具体性能参