ZIP文件压缩编码分析

[ZIP文件压缩编码分析] - I论文

ZIP文件压缩编码分析

摘要：ZIP是一个流行的压缩程序，广泛运用于数据文件传输、计算机文件存档、磁盘扩容等方面。本文介绍了ZIP压缩文件的格式和结构，描述了HSF码的编码方法，重点分析了ZIP压缩文件的两种压缩算法。

关键词： DEFLATE 匹配长度匹配距离 HSF树

The Analysis of Compressing Code in ZIP File

Abstract: ZIP is a popular compressing program. It is widely applied to transmit data files, keep in the archives of computer files, enlarge the capacity of disks. First, this paper introduces the format and the structure of ZIP compressed files, then describes the coding methods of HSF, at last analyses two compressing algorithms of ZIP.

Key words: DEFLATE matching length matching distance HSF Tree

一．引言

1977年和1978年，两名以色列人齐弗(J.Ziv)和兰佩尔(A.Lempel)提出了字典式编码，即著名的LZ77和LZ78算法。这两种算法在数据压缩领域获得了广泛应用，我们使用的通用压缩工具，像 ARJ，PKZip，WinZip，WinRar等，都是这两种压缩算法的变形。目前，以文件形式存储的各种媒体数据，在传输前往往都要进行压缩编码以提高传输效率，但是如果在传输过程中产生了误码，接收方就无法解压恢复出原文件。针对该问题我们对ZIP压缩算法进行了研究，试图研制纠错译码算法来解决该问题。

ZIP是一个流行的桌面压缩/文档程序，是以ASCII码“50 4B”开头的压缩软件中的一种，文件后缀名为.ZIP。ZIP压缩软件使用了多种压缩方法，尽管采用的方法可能不同，但文件的总体格式却是固定的。

二．ZIP压缩文件的结构分析

1．ZIP文件的总体格式

ZIP文件的总体格式如下所示：

[局部文件头+文件数据+数据描述符]…[中心目录]…[中心目录记录结束]

①局部文件头（Local file header）中包含了通用比特标志、压缩方式、文件建立时间和日期、CRC-32校验码、压缩数据和源文件长度等信息；

②文件数据(File Data)由参数区和数据区组成,有的算法采用固定码表，没有参数区，它的参数区数据已经规定好；

③数据描述符（Data descriptor）仅当通用比特标志的第3比特置为1时才有此字段；

④中心目录（Central directory）由文件头和中心目录记录结束两部分组成，其中，文件头的格式和局部文件头基本相同，中心目录记录结束包含了一些中心目录的参数属性。

2. ZIP压缩中所采用的压缩算法

（1）滑动窗口式字典压缩

压缩算法采用预统计滑动窗口与Huffman编码相结合的压缩算法，滑动窗口采用32K 个字节，待编码的文本窗口为0.4K个字节，其结构如下图所示：

32K字节0.4K字节

图1 滑动窗口的结构

（2）Huffman-Shannon-Fano码（HSF码）

在以LZ77为基础的许多后续算法中，都使用了HSF编码。这种码字与Huffman码字一样具有最优性，但采用Shannon-Fano码的构造方法。Huffman码性能是最优的，而SF码具有数值序列的特点，即从概率大的到概率小的码子来看，码子的二进制数值由小到大是递增的。这一点，正是用来减少译码表的尺度、缩短编译码时间的基本条件。所以HSF码既具有Huffman码的最优性，又具有Shannon-Fano码的数值序列性等优点。由于Huffman码没有数值序列的特性，而HSF码的码字的十进制数则是从0－（2k-1）的（k是最后一个码字的码元字符的个数），根据HSF码的这个性质，便可构造出较小的译码表和获得较短的编译码时间。

有一信源，其概率空间为

6

0.226,0.165,0.135,0.120,0.079,0.063,0.054,0.041,0.038,0.034,0.030,0.015

表1 Huffman码与HSF码的比较表

根据HSF码的数值序列性特点，在知道码长的情况下，构造HSF码有一个简单快速的办法：从最小码长开始编码，从0开始编码，依次加1，码长为多少，则其二进制比特就为多长。若码长发生变化，则HSF码的编码构造采用如下方式：

变化后的码值＝（变化前的码值＋1）×2m, （其中m＝变化后的码长－变化前的码长）3、ZIP压缩文件的压缩算法

ZIP压缩软件在不同的版本中采用了不同的压缩算法，像SHRINK算法、REDUCE算法(压缩系数为1-4)、IMPLODE算法，DEFLATE算法等等。在目前的版本中，主要采用的是DEFLATE 压缩算法。实际上，DEFLATE压缩算法也有多种，在这里主要分析我们研究的两种，分别是采用固定编码表的压缩算法和采用预统计滑动窗口与Huffman编码相结合的自适应方式字典编码压缩算法。这两种压缩算法都是采用滑动窗口进行压缩编码，并且对滑动窗口中的数据进行重新组织，以二叉搜索树（Binary Search Tree）的结构保存由前视缓冲区进入搜索缓冲区滑动窗口的字符，所以这两种压缩算法都是LZ77算法的变形。为了便于描述，分别起名为DEFLATE 1和DEFLATE 2。

三. DEFLATE1压缩算法

DEFLATE1压缩算法使用匹配距离、匹配长度编码与霍夫曼编码相结合的方法，以字符为最小编码单位，属于固定码表编码方法。在这种固定字典式编码方法中，字典是在压缩之前建立的，而且长时间保持不变。它的主要缺点是适应性差，效率低，主要应用于小文件的

压缩编码。

DEFLATE1压缩算法包含三个码表: THC码表、THL码表、THD码表，压缩编码和解压译码的过程都是基于这三个码表进行的。在编码过程当中，字符与长度码及距离码都采用固定的码字，具体算法如下:

①当匹配长度L 3，按单字符编码，待编码的ASCII字符的高4位按THC码表进行编码,所得到的4位或5位与原字符的低4位构成一个新比特组，然后反序发送。

②当3≤L≤258，匹配距离为d=n2-n1-1，其中n2为待编码的字符串的首字符地址，n1为所找到的匹配字符串的首字符地址。匹配长度L采用THL码表的固定霍夫曼码表编码，匹配距离d采用THD码表的固定霍夫曼码表编码。输出时, 长度和距离的霍夫曼码字即THL(L)和THD(D)要反序，先发THL(L)，再发THD(D)。由于THL码表和THD码表都采用固定霍夫曼码，而且又统一编码，所以在此编码方式中没有参数区。

需要说明的是，编码中间结果为查相应码表所得的码字；编码最后结果为反序后的中间结果；最后一列为编码最后结果。按8位字节进行重新装配后，得到信道上实际传输序列。译码则按相反过程进行。

四. DEFLATE2压缩算法

DEFLATE 2压缩算法与DEFLATE 1压缩算法在原理上基本是一致的，所不同的是DEFLATE 1压缩算法所采用的码表是固定码表，而DEFLATE 2压缩算法采用自适应方式字典编码，压缩之前是没有字典的。

DEFLATE2算法对要压缩的文件进行统计后，根据统计的结果生成两棵Huffman树(严格来说，这两棵树是Huffman-Shannon-Fano树，简称HSF树)，我们分别称之为字符树（字符树中包含字符码与匹配长度码）与距离树(匹配距离码)。在获得字符树与距离树后，还要将这两棵树变形（这种变形实际也是一种压缩）后再存入参数区。当把这两棵HSF树看作是固定码表时，可以认为DEFLATE2算法与DEFLATE1算法是一致的。

Huffman编码器根据滑动窗口压缩器输出的中间结果进行统计形成两棵HSF树，其中单字符与匹配长度在一棵HSF树上称为字符树，匹配距离在另一棵HSF树上称之为距离树。

单字符依照ASCII码编号为0－255，压缩文件结束码EOB的编号为256，257－285对应的是匹配长度及尾码位数；匹配距离码的基码编号为0－29，对应的是匹配距离及尾码位数。

1．参数区结构

在一个ZIP压缩文件中，局部文件头的后面就是参数区。

由于DEFLATE2是预统计Huffman编码的压缩算法，码树或码表是动态生成的,所以为了正确还原源文件，必须在压缩文件中存储压缩时产生的码树或码表等编码信息，这些信息就是压缩数据的参数区。

参数区分为两部分：C－DATA区与P－DATA区。这两部分数据存放着的都是某棵树的叶节点的长度，其中C－DATA区的数据构造码长编码树，P－DATA区的数据结合C－DATA区的结果分别构造出字符树与距离树，所构造的三棵树均为HSF树。

图2 参数区的结构

2．HSF码树的构造

在参数区中码树信息是由码长来表达的。由码长和一些相应的规则可以唯一确定码树，参数区部分一共可以建立三棵HSF码树。第一棵HSF码树由C－DATA区构造，它是构造后两棵HSF码树所需码长的码长编码树，后两棵HSF树是字符树与距离树，由P－DATA区构造。

①子参数区1（C－DATA区）

C－DATA区的大小为3 *（4＋NB）（0≤NB≤15），它每3bit为一组，表示字符树与距

离树码长的编码码长。

②子参数区2、3（P－DATA区）

P－DATA区是由C－DATA区所产生的码长编码生成的。字符树（子参数区2）在前，距离数在后（子参数区3）。子参数区2从码号0开始顺序编码至257＋NL，子参数区3从码号0开始编码到1＋ND。根据C－DATA区所确立的码字，在P－DATA区可以得到相应位置的字符码和距离码的编码长度，也就是码长。

从子参数区得到码长后，按照与码长编码树建立时同样的规则，我们就可以得到了字符树与距离树，由字符树可以得到字符码与匹配长度码，由距离树可以得到匹配距离码。这两棵HSF树是进行压缩编码和解压译码的基础。

参数区的后面是压缩数据区，对于ZIP文件中的压缩数据区，无论是DEFLATE2算法，还是DEFLATE2算法，其格式都是一样的。

在压缩数据区中，存储的数据是P－DATA区数据所建立的字符树与距离树所代表的码字，原文件中的数据由该区还原。接下来需要做的工作就是按照由P－DATA区数据所建立的字符树与距离树所构造的码字进行解压译码，恢复出源文件。

五. 结束语

为了对不同类型、不同大小的文件压缩时能得到尽可能大的压缩率，ZIP采用了多种压缩算法，根据我们的分析发现，这些算法都属于DEFLATE系列。文中主要分析了ZIP的两种压缩算法, 同时纠错译码算法有了一定进展，其它的算法我们正在开展进一步的研究工作。

参考文献：

1. 刘立柱，平西建. 信息论与信源编码. 中国人民解放军信息工程学院.1988.

2. 傅祖芸. 信息论基础理论与应用. 电子工业出版社. 2004.

3. Khalid Sayood. INTRODUCTION TO DATA COMPRESSION. Horgan Kaufmann Pubisher,Inc.

1996

4．T．C．Bell etc.，TEXT COMPRESSION，Prentice Hall，1990.

5. Gilbert Held etc.，DATA COMPRESSION，3rd edition，John Wiley & Sons LTD，1991.