LZ78算法

四 01

邱金武其他, 数据压缩, 转载 No Comments

【http://202.117.96.226:8090/dmtjs/course/ch04/tcp040404.html?ttype=1&tcode=menu4_040404】

4.4.4 LZ78算法

在介绍LZ78算法之前，首先说明在算法中用到的几个术语和符号：

  1. 字符流(Charstream)：要被编码的数据序列。
  2. 字符(Character)：字符流中的基本数据单元。
  3. 前缀(Prefix)： 在一个字符之前的字符序列。
  4. 缀-符串(String)：前缀＋字符。
  5. 码字(Code word)：码字流中的基本数据单元，代表词典中的一串字符。
  6. 码字流(Codestream)： 码字和字符组成的序列，是编码器的输出。
  7. 词典(Dictionary)： 缀-符串表。按照词典中的索引号对每条缀-符串(String)指定一个码字(Code word)。
  8. 当前前缀(Current prefix)：在编码算法中使用，指当前正在处理的前缀，用符号P表示。
  9. 当前字符(Current character)：在编码算法中使用，指当前前缀之后的字符，用符号C表示。
  10. 当前码字(Current code word)： 在译码算法中使用，指当前处理的码字，用W表示当前码字，String.W表示当前码字的缀-符串。

1. 编码算法

          LZ78的编码思想是不断地从字符流中提取新的缀-符串(String)，通俗地理解为新“词条”，然后用“代号”也就是码字(Code word)表示这个“词条”。这样一来，对字符流的编码就变成了用码字(Code word)去替换字符流(Charstream)，生成码字流(Codestream)，从而达到压缩数据的目的。

          在编码开始时词典是空的，不包含任何缀-符串(string)。在这种情况下编码器就输出一个表示空字符串的特殊码字(例如“0”)和字符流中(Charstream)的第一个字符C，并把这个字符C添加到词典中作为一个由一个字符组成的缀-符串(string)。在编码过程中，如果出现类似的情况，也照此办理。在词典中已经包含某些缀-符串(String)之后，如果“当前前缀P +当前字符C”已经在词典中，就用字符C来扩展这个前缀，这样的扩展操作一直重复到获得一个在词典中没有的缀-符串(String)为止。此时就输出表示当前前缀P的码字(Code word)和字符C，并把P+C添加到词典中作为前缀(Prefix)，然后开始处理字符流(Charstream)中的下一个前缀。

         LZ78编码器的输出是码字-字符(W,C)对，每次输出一对到码字流中，与码字W相对应的缀-符串(String)用字符C进行扩展生成新的缀-符串(String)，然后添加到词典中。LZ78编码的具体算法如下：

步骤1： 在开始时，词典和当前前缀P都是空的。
步骤2： 当前字符C ：=字符流中的下一个字符。
步骤3： 判断P+C是否在词典中：

  1. 如果“是”：用C扩展P，让P ：= P+C ；
  2. 如果“否”：
    1. 输出与当前前缀P相对应的码字和当前字符C；
    2. 把字符串P+C 添加到词典中。
    3. 令P ：=空值。
  3. 判断字符流中是否还有字符需要编码
    1. 如果“是”：返回到步骤2。
    2. 如果“否”：若当前前缀P不是空的，输出相应于当前前缀P的码字，然后结束编码。

2. 译码算法

在译码开始时译码词典是空的，它将在译码过程中从码字流中重构。每当从码字流中读入一对码字-字符(W,C)对时，码字就参考已经在词典中的缀-符串，然后把当前码字的缀-符串string.W 和字符C输出到字符流(Charstream)，而把当前缀-符串(string.W+C)添加到词典中。在译码结束之后，重构的词典与编码时生成的词典完全相同。LZ78译码的具体算法如下：
步骤1： 在开始时词典是空的。
步骤2： 当前码字W ：=码字流中的下一个码字。
步骤3： 当前字符C ：= 紧随码字之后的字符。
步骤4： 把当前码字的缀-符串(string.W)输出到字符流(Charstream)，然后输出字符C。
步骤5： 把string.W+C添加到词典中。
步骤6： 判断码字流中是否还有码字要译

  1. 如果“是”，就返回到步骤2。
  2. 如果“否”，则结束。

[例4.6] 编码字符串如表4-13所示，编码过程如表4-14所示。现说明如下：
(1) “步骤”栏表示编码步骤。
(2) “位置”栏表示在输入数据中的当前位置。
(3) “词典”栏表示添加到词典中的缀-符串，缀-符串的索引等于“步骤”序号。
(4) “输出”栏以(当前码字W, 当前字符C)简化为(W, C)的形式输出。

表4-13 编码字符串

位置    1    2    3    4    5    6    7    8    9
字符    A    B    B    C    B    C    A    B    A

表4-14 编码过程

步骤    位置    词典    输出
1         1        A        (0,A)
2         2        B       (0,B)
3         3       B C     (2,C)
4         5      B C A   (3,A)
5         8      B A      (2,A)

与LZ77相比，LZ78的最大优点是在每个编码步骤中减少了缀-符串(String)比较的数目，而压缩率与LZ77类似。

LZ77压缩算法原理

三 31

邱金武其他, 数据压缩, 转载 No Comments

【http://www.jijiao.com.cn/Perl/bianliang/00000007.htm】

       我们在第三和第四章中讨论的压缩模型都是基于对信息中单个字符出现频率的统计而设计的，直到 70 年代末期，这种思路在数据压缩领域一直占据着统治地位。在 我们今天看来，这种情形在某种程度上显得有些可笑，但事情就是这样，一旦某项 技术在某一领域形成了惯例，人们就很难创造出在思路上与其大相径庭的哪怕是更 简单更实用的技术来。

        我们敬佩那两个在数据压缩领域做出了杰出贡献的以色列人，因为正是他们打破了  Huffman 编码一统天下的格局，带给了我们既高效又简便的“字典模型”。至今 ，几乎我们日常使用的所有通用压缩工具，象 ARJ，PKZip，WinZip，LHArc，RAR ，GZip，ACE，ZOO，TurboZip，Compress，JAR……甚至许多硬件如网络设备中内 置的压缩算法，无一例外，都可以最终归结为这两个以色列人的杰出贡献。

         说起来，字典模型的思路相当简单，我们日常生活中就经常在使用这种压缩思想。 我们常常跟人说“奥运会”、“IBM”、“TCP”之类的词汇，说者和听者都明白它 们指的是“奥林匹克运动会”、“国际商业机器公司”和“传输控制协议”，这实 际就是信息的压缩。我们之所以可以顺利使用这种压缩方式而不产生语义上的误解 ，是因为在说者和听者的心中都有一个事先定义好的缩略语字典，我们在对信息进 行压缩（说）和解压缩（听）的过程中都对字典进行了查询操作。字典压缩模型正 是基于这一思路设计实现的。

        最简单的情况是，我们拥有一本预先定义好的字典。例如，我们要对一篇中文文章 进行压缩，我们手中已经有一本《现代汉语词典》。那么，我们扫描要压缩的文章 ，并对其中的句子进行分词操作，对每一个独立的词语，我们在《现代汉语词典》 查找它的出现位置，如果找到，我们就输出页码和该词在该页中的序号，如果没有 找到，我们就输出一个新词。这就是静态字典模型的基本算法了。

        你一定可以发现，静态字典模型并不是好的选择。首先，静态模型的适应性不强， 我们必须为每类不同的信息建立不同的字典；其次，对静态模型，我们必须维护信 息量并不算小的字典，这一额外的信息量影响了最终的压缩效果。所以，几乎所有 通用的字典模型都使用了自适应的方式，也就是说，将已经编码过的信息作为字典 ，如果要编码的字符串曾经出现过，就输出该字符串的出现位置及长度，否则输出 新的字符串。根据这一思路，你能从下面这幅图中读出其中包含的原始信息吗？

       啊，对了，是“吃葡萄不吐葡萄皮，不吃葡萄倒吐葡萄皮”。现在你该大致明白自 适应字典模型的梗概了吧。好了，下面就让我们来深入学习字典模型的第一类实现 
——LZ77 算法。

 

滑动的窗口

        LZ77 算法在某种意义上又可以称为“滑动窗口压缩”，这是由于该算法将一个虚 拟的，可以跟随压缩进程滑动的窗口作为术语字典，要压缩的字符串如果在该窗口 中出现，则输出其出现位置和长度。使用固定大小窗口进行术语匹配，而不是在所 有已经编码的信息中匹配，是因为匹配算法的时间消耗往往很多，必须限制字典的 大小才能保证算法的效率；随着压缩的进程滑动字典窗口，使其中总包含最近编码 过的信息，是因为对大多数信息而言，要编码的字符串往往在最近的上下文中更容 易找到匹配串。 

让我们熟悉一下 LZ77 算法的基本流程。

  1. 从当前压缩位置开始，考察未编码的数据，并试图在滑动窗口中找出最长的匹 配字符串，如果找到，则进行步骤 2，否则进行步骤 3。
  2. 输出三元符号组 ( off, len, c )。其中 off 为窗口中匹配字符串相对窗口边 
    界的偏移，len 为可匹配的长度，c 为下一个字符。然后将窗口向后滑动  len + 1 个字符，继续步骤 1。
  3. 输出三元符号组 ( 0, 0, c )。其中 c 为下一个字符。然后将窗口向后滑动  
    len + 1 个字符，继续步骤 1。

      我们结合实例来说明。假设窗口的大小为 10 个字符，我们刚编码过的 10 个字符 是：abcdbbccaa，即将编码的字符为：abaeaaabaee 我们首先发现，可以和要编码字符匹配的最长串为 ab ( off = 0, len = 2 ), ab 的下一个字符为 a，我们输出三元组：( 0, 2, a ) 现在窗口向后滑动 3 个字符，窗口中的内容为：dbbccaaaba 
下一个字符 e 在窗口中没有匹配，我们输出三元组：( 0, 0, e ) 窗口向后滑动 1 个字符，其中内容变为：bbccaaabae 我们马上发现，要编码的 aaabae 在窗口中存在( off = 4, len = 6 )，其后的字 符为 e，我们可以输出：( 4, 6, e ) 这样，我们将可以匹配的字符串都变成了指向窗口内的指针，并由此完成了对上述 数据的压缩。 
      解压缩的过程十分简单，只要我们向压缩时那样维护好滑动的窗口，随着三元组的 不断输入，我们在窗口中找到相应的匹配串，缀上后继字符 c 输出（如果 off 和  len 都为 0 则只输出后继字符 c )即可还原出原始数据。 当然，真正实现 LZ77 算法时还有许多复杂的问题需要解决，下面我们就来对可能 碰到的问题逐一加以探讨。

 

编码方法

         我们必须精心设计三元组中每个分量的表示方法，才能达到较好的压缩效果。一般 来讲，编码的设计要根据待编码的数值的分布情况而定。对于三元组的第一个分量 ——窗口内的偏移，通常的经验是，偏移接近窗口尾部的情况要多于接近窗口头部 的情况，这是因为字符串在与其接近的位置较容易找到匹配串，但对于普通的窗口 大小（例如 4096 字节）来说，偏移值基本还是均匀分布的，我们完全可以用固定 的位数来表示它。

       编码 off 需要的位数 bitnum = upper_bound( log2( MAX_WND_SIZE )) 
由此，如果窗口大小为 4096，用 12 位就可以对偏移编码。如果窗口大小为  
2048，用 11 位就可以了。复杂一点的程序考虑到在压缩开始时，窗口大小并没有 
达到 MAX_WND_SIZE，而是随着压缩的进行增长，因此可以根据窗口的当前大小动 态计算所需要的位数，这样可以略微节省一点空间。

       对于第二个分量——字符串长度，我们必须考虑到，它在大多数时候不会太大，少 数情况下才会发生大字符串的匹配。显然可以使用一种变长的编码方式来表示该长 度值。在前面我们已经知道，要输出变长的编码，该编码必须满足前缀编码的条件 。其实 Huffman 编码也可以在此处使用，但却不是最好的选择。适用于此处的好 的编码方案很多，我在这里介绍其中两种应用非常广泛的编码。

      第一种叫 Golomb 编码。假设对正整数 x 进行 Golomb 编码，选择参数 m，令  b = 2m q = INT((x – 1)/b) r = x – qb – 1 则 x 可以被编码为两部分，第一部分是由 q 个 1 加 1 个 0 组成，第二部分为  m 位二进制数，其值为 r。我们将 m = 0, 1, 2, 3 时的 Golomb 编码表列出： 
   值 x        m = 0       m = 1       m = 2       m = 3 
————————————————————- 
    1             0         0 0        0 00        0 000 
    2            10         0 1        0 01        0 001 
    3           110        10 0        0 10        0 010 
    4          1110        10 1        0 11        0 011 
    5         11110       110 0       10 00        0 100 
    6        111110       110 1       10 01        0 101 
    7       1111110      1110 0       10 10        0 110 
    8      11111110      1110 1       10 11        0 111 
    9     111111110     11110 0      110 00       10 000

      从表中我们可以看出，Golomb 编码不但符合前缀编码的规律，而且可以用较少的 位表示较小的 x 值，而用较长的位表示较大的 x 值。这样，如果 x 的取值倾向 于比较小的数值时，Golomb 编码就可以有效地节省空间。当然，根据 x 的分布规 律不同，我们可以选取不同的 m 值以达到最好的压缩效果。

       对我们上面讨论的三元组 len 值，我们可以采用 Golomb 方式编码。上面的讨论 中 len 可能取 0，我们只需用 len + 1 的 Golomb 编码即可。至于参数 m 的选 择，一般经验是取 3 或 4 即可。 可以考虑的另一种变长前缀编码叫做 γ 编码。它也分作前后两个部分，假设对 x  编码，令 q = int( log2x )，则编码的前一部分是 q 个 1 加一个 0，后一部分 是 q 位长的二进制数，其值等于 x – 2q 。γ编码表如下： 
   值 x    γ编码 
——————— 
    1       0 
    2      10 0 
    3      10 1 
    4     110 00 
    5     110 01 
    6     110 10 
    7     110 11 
    8    1110 000 
    9    1110 001

      其实，如果对 off 值考虑其倾向于窗口后部的规律，我们也可以采用变长的编码 方法。但这种方式对窗口较小的情况改善并不明显，有时压缩效果还不如固定长编 码。

       对三元组的最后一个分量——字符 c，因为其分布并无规律可循，我们只能老老实 实地用 8 个二进制位对其编码。

        根据上面的叙述，相信你一定也能写出高效的编码和解码程序了。

另一种输出方式

        LZ77 的原始算法采用三元组输出每一个匹配串及其后续字符，即使没有匹配，我 们仍然需要输出一个 len = 0 的三元组来表示单个字符。试验表明，这种方式对 于某些特殊情况（例如同一字符不断重复的情形）有着较好的适应能力。但对于一 般数据，我们还可以设计出另外一种更为有效的输出方式：将匹配串和不能匹配的 单个字符分别编码、分别输出，输出匹配串时不同时输出后续字符。

        我们将每一个输出分成匹配串和单个字符两种类型，并首先输出一个二进制位对其 加以区分。例如，输出 0 表示下面是一个匹配串，输出 1 表示下面是一个单个字 符。

       之后，如果要输出的是单个字符，我们直接输出该字符的字节值，这要用 8 个二 进制位。也就是说，我们输出一个单个的字符共需要 9 个二进制位。 

       如果要输出的是匹配串，我们按照前面的方法依次输出 off 和 len。对 off，我 们可以输出定长编码，也可以输出变长前缀码，对 len 我们输出变长前缀码。有 时候我们可以对匹配长度加以限制，例如，我们可以限制最少匹配 3 个字符。因 为，对于 2 个字符的匹配串，我们使用匹配串的方式输出并不一定比我们直接输 出 2 个单个字符（需要 18 位）节省空间（是否节省取决于我们采用何种编码输 出 off 和 len）。

      这种输出方式的优点是输出单个字符的时候比较节省空间。另外，因为不强求每次 都外带一个后续字符，可以适应一些较长匹配的情况。

如何查找匹配串

       在滑动窗口中查找最长的匹配串，大概是 LZ77 算法中的核心问题。容易知道， LZ77 算法中空间和时间的消耗集中于对匹配串的查找算法。每次滑动窗口之后， 都要进行下一个匹配串的查找，如果查找算法的时间效率在 O(n2) 或者更高，总 的算法时间效率就将达到 O(n3)，这是我们无法容忍的。正常的顺序匹配算法显然 无法满足我们的要求。事实上，我们有以下几种可选的方案。

  1. 限制可匹配字符串的最大长度（例如 20 个字节），将窗口中每一个 20 字节 长的串抽取出来，按照大小顺序组织成二叉有序树。在这样的二叉有序树中进行字 符串的查找，其效率是很高的。树中每一个节点大小是 20(key) + 4(off) +  4(left child) + 4(right child) = 32。树中共有  MAX_WND_SIZE – 19 个节点， 假如窗口大小为 4096 字节，树的大小大约是 130k 字节。空间消耗也不算多。这 种方法对匹配串长度的限制虽然影响了压缩程序对一些特殊数据（又很长的匹配串 ）的压缩效果，但就平均性能而言，压缩效果还是不错的。
  2. 将窗口中每个长度为 3 （视情况也可取 2 或 4）的字符串建立索引，先在此 索引中匹配，之后对得出的每个可匹配位置进行顺序查找，直到找到最长匹配字符 串。因为长度为 3 的字符串可以有 2563 种情况，我们不可能用静态数组存储该 索引结构。使用 Hash 表是一个明智的选择。我们可以仅用 MAX_WND_SIZE – 1 的 数组存储每个索引点，Hash 函数的参数当然是字符串本身的 3 个字符值了，Hash  函数算法及 Hash 之后的散列函数很容易设计。每个索引点之后是该字符串出现 的所有位置，我们可以使用单链表来存储每一个位置。值得注意的是，对一些特殊 情况比如 aaaaaa…之类的连续字串，字符串 aaa 有很多连续出现位置，但我们 无需对其中的每一个位置都进行匹配，只要对最左边和最右边的位置操作就可以了 。解决的办法是在链表节点中纪录相同字符连续出现的长度，对连续的出现位置不 
    再建立新的节点。这种方法可以匹配任意长度的字符串，压缩效果要好一些，但缺 点是查找耗时多于第一种方法。
  3. 使用字符树( trie )来对窗口内的字符串建立索引，因为字符的取值范围是  
    0 – 255，字符树本身的层次不可能太多，3 – 4 层之下就应该换用其他的数据结 构例如 Hash 表等。这种方法可以作为第二种方法的改进算法出现，可以提高查找 速度，但空间的消耗较多。

       如果对窗口中的数据进行索引，就必然带来一个索引位置表示的问题，即我们在索 引结构中该往偏移项中存储什么数据：首先，窗口是不断向后滑动的，我们每次将 窗口向后滑动一个位置，索引结构就要作相应的更新，我们必须删除那些已经移动 出窗口的数据，并增加新的索引信息。其次，窗口不断向后滑动的事实使我们无法 用相对窗口左边界的偏移来表示索引位置，因为随着窗口的滑动，每个被索引的字 符串相对窗口左边界的位置都在改变，我们无法承担更新所有索引位置的时间消耗 。 
       解决这一问题的办法是，使用一种可以环形滚动的偏移系统来建立索引，而输出匹 配字符串时再将环形偏移还原为相对窗口左边界的真正偏移。让我们用图形来说明 ，窗口刚刚达到最大时，环形偏移和原始偏移系统相同： 
偏移：     0 1 2 3 4 ……                                              
Max 
|————————————————————–| 
环形偏移： 0 1 2 3 4 ……                                              
Max 
窗口向后滑动一个字节后，滑出窗口左端的环形偏移 0 被补到了窗口右端： 
偏移：     0 1 2 3 4 ……                                              
Max 
|————————————————————–| 
环形偏移： 1 2 3 4 5 ……                                            
Max 0 
窗口再滑动 3 个子节后，偏移系统的情况是： 
偏移：     0 1 2 3 4 ……                                              
Max 
|————————————————————–| 
环形偏移： 4 5 6 7 8……                                      Max 0  
1 2 3 

依此类推。 我们在索引结构中保存环形偏移，但在查找到匹配字符串后，输出的匹配位置 off  必须是原始偏移（相对窗口左边），这样才可以保证解码程序的顺利执行。我们 用下面的代码将环形偏移还原为原始偏移： 
// 由环形 off 得到真正的off(相对于窗口左边) 
// 其中 nLeftOff 为当前与窗口左边对应的环形偏移值 
int GetRealOff(int off) 
{ 
    if (off >= nLeftOff) 
        return off – nLeftOff; 
    else 
        return (_MAX_WINDOW_SIZE – (nLeftOff – off)); 
} 
这样，解码程序无需考虑环形偏移系统就可以顺利高速解码了。

VPatch学习笔记

三 30

邱金武数据压缩 No Comments

        说到差异比较，很多人都会想到Linux下diff，patch命令。开源项目“bsdiff and bspatch”（http://www.daemonology.net/bsdiff/）是个不错的二进制比较工具，并且能够生成相应的patch。

        这里说一说另一个二进制patch工具VPatch（http://www.tibed.net/vpatch/）。这个工具一般用在NSIS Installer系统中，不过自动更新时对更新过的文件打Patch也不错。因为这样可能会大幅减少升级包的大小。

         整个程序代码量不大，第三方代码包括MD5和Adler32相关的部分。代码中提供了打包的范例程序（main.cpp）。奇怪的是，代码中包含生成Patch包的函数却没有解Patch包的函数，不过如果熟悉里面的协议（规范）自己写个解Patch的函数也相当简单。尽管程序中文件IO全部使用C++的文件流，不过这种对于跨平台的考虑本人很是赞同，其他基于这个考虑的还包括代码的POSIXUtil部分。

         在对二进制数据进行差异比较时，最核心的思想就是找出两者的相同点和不同点，而在这个过程中效率和精确度往往不能两全，所以程序员往往需要有所权衡。VPatch在这方面引入了一个关键参数blockSize，这个参数定义了比较的Block大小。这个参数越小比较将越精细而效率将降低。一个典型的用法如下：

		if (dwOldFileSize > 1024*1024*1024)	//大于G
		{
			pg.blockSize = 512;
			pg.maxMatches = 16;
		}
		else if (dwOldFileSize > 100*1024*1024)//大于M
		{
			pg.blockSize = 128;
			pg.maxMatches = 16;
		}
		else
		{
			pg.blockSize = 64;
			pg.maxMatches = 500;
		}

        在打包时，VPatch会将原文件分成若干段，每一段长度为blockSize。同时对每一段计算其adler32，最后将这些段通过adler32值进行排序。接着遍历目标文件的每一个字节，计算从当前字节开始的blockSize字节的adler32值，然后查询源文件的adler32表（使用二分查找），如果匹配则往前后两个方向继续匹配（每一个字节精确比较），直到找到一个最大的匹配长度。在匹配的最后会生成一个SameBlock数组

  typedef uint32_t TFileOffset;
  typedef struct SameBlock {
    TFileOffset sourceOffset;
    TFileOffset targetOffset;
    TFileOffset size;
  } SameBlock;

        这个结构表示两个文件的相同段，例如SameBlock（2，100，40）表示源文件第2字节开始的40字节和目标文件第100字节开始的40字节相同。最后将以上相关的数据写到一个文件中。

VPatch规范

  1. VPatch Magic（4）
  2. 校验类型MD5/CRC和Patch段数量（4）
  3. 每一个Patch
    1. Patch Block数量（4）
    2. 源文件MD5（16）或CRC（4）
    3. 目标文件MD5（16）或CRC（4）
    4. Patch Body Size（4）
    5. 删除和增加记录
  4. 终止 Magic （1）
  5. 时间戳（8）

删除和增加记录

相同记录

  1. 长度类型（1） ： 为了节省空间，VPath对长度的存储进行了分类，如果长度小于256，则使用1个字节存储，如果小于65536则使用两个字节存储，否则使用四个字节存储。该域可以去如下值：
    1. 1 ： 表示长度为1字节
    2. 2 ： 表示长度为2字节
    3. 3 ： 表示长度为4字节
  2. 长度 （1/2/4）：两个文件相同范围的长度
  3. 源文件偏移（4） ：相同区域在源文件中的偏移，在生成目标文件时从源文件这个地方开始拷贝数据。

不同记录

  1. 长度类型（1） ： 为了节省空间，VPath对长度的存储进行了分类，如果长度小于256，则使用1个字节存储，如果小于65536则使用两个字节存储，否则使用四个字节存储。该域可以去如下值：
    1. 4 ： 表示长度为1字节
    2. 5 ： 表示长度为2字节
    3. 6 ： 表示长度为4字节
  2. 长度 （1/2/4） ：两个文件相同范围的长度
  3. 目标文件的内容（x） ： 这些内容从目标文件中拷贝而来，长度为【2】项指定的长度。

     Patch Block数量可以理解为上面记录的多少加1。之所要加1，是因为在最后会写入一个终止标记和时间戳。

数据压缩之名词学习

三 27

邱金武数据压缩 No Comments

        如果仔细观察7z（for windows）的ui可以发现其支持多种数据格式，包括7z, zip, gzip, bzip2和tar。如果同时又选择多个文件然后右键进行压缩，就只剩下7z、zip和tar了。

有三个概念，归档工具、数据压缩工具和压缩算法

        简单的讲，归档工具一般就是将多个文件（夹）打包使之看起来像一个文件，而数据压缩工具就是能够压缩单个文件并且能够解压之的工具。而压缩算法则是压缩工具用来压缩数据的工具了。

        上面tar算是一个归档工具，而zip、7z则包含归档功能和压缩功能，而gzip和bzip2仅仅只是压缩工具（内部使用特定算法），这也是为什么在Linux经常会看到文件后缀如.tar.gz或者.tar.bz2。这是因为首先使用tar将需要压缩的所有内容打包成一个文件，然后再用gzip或者bzip2压缩文件。

         关于zip文件的起源，可以查看（http://zh.wikipedia.org/zh-cn/ZIP_(文件格式)），这种格式的作者Phil Katz发明了算法Deflate（http://zh.wikipedia.org/zh-cn/DEFLATE）。zlib（http://zh.wikipedia.org/wiki/Zlib）库作为最为流行的Deflate算法的实现而存在，gzip（http://zh.wikipedia.org/zh-cn/Gzip）使用Deflate来实现文件压缩功能（它定义了一个gzip头）。Info-zip也提供了Deflate算法的高效实现。zip和7z格式兼容很多算法，例如zip格式除了兼容默认的Deflate算法，也支持Deflate64，Bzip2（http://zh.wikipedia.org/zh-cn/Bzip2）和LZMA算法。

        网上有一牛人基于Info-zip库整了一个XUNZIP和XZIP，通过它程序员可以” Add zip and/or unzip to your app with no extra .lib or .dll ”  （http://www.codeproject.com/KB/cpp/xzipunzip.aspx），不过该代码虽然支持zip和unzip，不过经测试只支持使用Deflate算法的压缩包和使用Deflate算法创建zip压缩包。

       另一个不错简单实现的是http://www.codeproject.com/KB/files/zip_utils.aspx?fid=68674&tid=2493665。这里除了实现基本的zip和unzip意外，还增加到对resource（windows）和内存的操作。

zip学习–部分资料汇总

三 26

邱金武数据压缩 2 Comments

文件格式规范

http://www.pkware.com/documents/casestudies/APPNOTE.TXT

 

网络上的中文翻译

一个 ZIP 文件由三个部分组成：

压缩源文件数据区+压缩源文件目录区+压缩源文件目录结束标志

1、压缩源文件数据区

    在这个数据区中每一个压缩的源文件/目录都是一条记录，记录的格式如下：

       [文件头+ 文件数据 + 数据描述符]
       a、文件头结构

          组成                     长度
       文件头标记                  4 bytes (0×04034b50)
       解压文件所需 pkware 版本    2 bytes
      全局方式位标记              2 bytes
   压缩方式                     2 bytes
最后修改文件时间             2 bytes
最后修改文件日期             2 bytes
CRC-32校验                 4 bytes
压缩后尺寸                   4 bytes
未压缩尺寸                   4 bytes
文件名长度                   2 bytes

      扩展记录长度 2 bytes
文件名                     （不定长度）
扩展字段                    （不定长度）

        b、文件数据

        c、数据描述符

组成     长度
   CRC-32校验                  4 bytes
压缩后尺寸                   4 bytes
未压缩尺寸                   4 bytes

这 个数据描述符只在全局方式位标记的第３位设为１时才存在（见后详解），紧接在压缩数据的最后一个字节后。这个数据描述符只用在不能对输出的 ZIP 文件进行检索时使用。例如：在一个不能检索的驱动器（如：磁带机上）上的 ZIP 文件中。如果是磁盘上的ZIP文件一般没有这个数据描述符。

2、压缩源文件目录区

     在这个数据区中每一条纪录对应在压缩源文件数据区中的一条数据

组成             长度

目录中文件文件头标记    4 bytes (0×02014b50)

压缩使用的 pkware 版本 2 bytes

解压文件所需 pkware 版本 2 bytes

全局方式位标记 2 bytes

压缩方式 2 bytes

最后修改文件时间 2 bytes

最后修改文件日期 2 bytes

ＣＲＣ－３２校验 4 bytes

压缩后尺寸 4 bytes

未压缩尺寸 4 bytes

文件名长度 2 bytes

扩展字段长度 2 bytes

文件注释长度 2 bytes

磁盘开始号 2 bytes

内部文件属性 2 bytes

外部文件属性 4 bytes

局部头部偏移量 4 bytes

文件名 （不定长度）

扩展字段 （不定长度）

文件注释 （不定长度）

     3、压缩源文件目录结束标志

组成           长度

目录结束标记 4 bytes (0×02014b50)

    当前磁盘编号 2 bytes

目录区开始磁盘编号 2 bytes

本磁盘上纪录总数    2 bytes

目录区中纪录总数 2 bytes

目录区尺寸大小 4 bytes

目录区对第一张磁盘的偏移量 4 bytes

ZIP 文件注释长度 2 bytes

ZIP 文件注释 （不定长度）

 

乱谈zip、rar文件格式

http://www.comicer.com/stronghorse/water/software/ZipRar.htm

作者：马健
邮箱：stronghorse@tom.com
主页：http://stronghorse.yeah.net
发布：2006.11.21
最近更新：2006.11.25

目录
一、目录表（TOC）与分卷（Volume）
二、固实（solid）压缩方式
三、安全性
四、开放性
五、结论
声明：本文并非学术论文，所述内容仅为我个人的看法和体会，不具任何权威性，仅供有兴趣的人参考，但是如果您不具有足够的鉴别能力，建议勿看，以免误导。

一、目录表（TOC）与分卷（Volume）

抛开压缩算法不谈，我认为zip、rar在文件格式上最大的差异就在目录表（Table of Contents，TOC）：zip有TOC，而rar没有。

TOC这个词其实是从出版界借用过来的，指的就是每一本书正文前面的“目录”，它的作用地球人都知道：如果想快速找到书中某一内容，可以先查TOC，然后按照TOC指明的页码直接翻即可。

在纸质书里TOC是印刷出来的一张表，而在电子文件里则是由结构化数据构成的一张表，它的目的同样是为了快速定位：如果想找文件中的某一内容，可以先查TOC，知道感兴趣的内容在文件的什么位置，直接跳过去就行了。最常见的运用就是avi、rm等多媒体文件：播放的时候经常有人在播放条上点来点去跳着看（即“随机访问”），如果没有TOC，在长达几百兆的文件里来回定位会慢死。

具体到zip文件里，TOC是放在文件尾部的一张表，里面列出了zip包中每一个文件的属性（文件名、长度等）和在zip包中的存放位置。如果需要随机访问zip包中的某一个文件，只需在TOC里找到这个文件的存放位置，直接跳过去即可。

而RAR文件里则没有TOC，在文件头之后所有文件按顺序连续存放。

这种差异造成的结果就是：随机访问时zip比rar快，而顺序访问时rar比zip快。

所谓随机访问，就是前面说过的随机访问压缩包中某个指定的文件。举一个简单的例子：一本反编译或下载到的网页电子书，有大量HTML、图像、css、js，然后打成压缩包。现在要求在不解包的情况下访问其中的页面：可以想象，打开每个HTML页面的时候，它所附带的图像、css、js等文件可能随机分布在整个压缩包里，如果没有TOC，查找每个文件的时候都要从头开始找，将会有多慢。 所以各位可以理解为什么jar包就是标准zip包，而我也只用zip格式保存反编译出来的电子书、漫画、PDG书等一切可能需要随机访问的东西。

所谓顺序访问，就是将整个压缩包从头解到尾。在这方面RAR具有天然的优势。而且为了节省WinRAR列文件的时间，对于单个RAR我一般都直接通过右键菜单解压缩，很少双击压缩包打开再解压。解多个RAR时当然都用BatchUnRar。

由于rar的原作者已经去世，造成这种差异的确切原因我相信已不可考，但我个人猜测可能与DOS时代的备份软件之争有关：在DOS时代，电脑硬盘不像现在这样奢侈，20MB就算很大了。这样的容量用两盒软盘 即可备份，备份成本相对数据本身的价值来说非常低廉。因此在DOS时代，很多公司和机构都制定有定期硬盘备份政策，以免因为人为或非人为的因素 （早期硬盘可没有如今可靠）而造成不可挽回的数据损失。在备份软件方面，虽然微软已经随DOS提供了Backup/Restore工具，但是他们基本不具备数据压缩能力，因此在压缩软件中提供备份功能，就成为DOS时代的一个时尚。由于DOS时代的备份介质多为软盘，因此压缩 软件的备份功能其实就转化成如今很常见的一个功能：分卷压缩功能，即按照软盘容量进行分卷压缩，然后将分卷压缩文件备份（Backup）到软盘，需要的时候再解压，或恢复（Restore）到硬盘。

DOS时代最有名的zip工具是pkzip，出现得比DOS版的RAR早。在分卷压缩时，pkzip按照zip文件规范，将TOC存放在最后，即存储在最后一卷，由此带来如下问题：

1、恢复时，每解压一张盘，都要先将最后一张盘插进去一次，读一次TOC。
2、只要最后一张盘上的TOC坏了，就算其它盘都是好的，也不能正常解压。

这两个缺点，尤其是第一个缺点实在是太臭名昭著了，因此当时出现了非常强烈的改革呼声。在这个关键时刻，DOS版的RAR出现了：不仅压缩率比pkzip高（这点在DOS时代非常重要，毕竟软盘又贵容量又小），而且由于吸取了当时对zip格式的批评，取消了TOC，因此：

1、在恢复分卷压缩的备份文件时，不需要频繁插入带有TOC的分卷，按顺序换盘即可。
2、即使某个分卷损坏，也可以跳过，从完好的分卷再开始解压。

由于这些原因（当然还有其它原因），RAR推出后迅速取得了成功，pkzip在DOS时代就开始流失用户，到Windows时代基本消声匿迹。在Windows时代推出的Winzip，则彻底放弃了分卷压缩功能（zip格式永远的痛？）。 而从我看到的源自WinRAR的UnRAR源代码来看，现在WinRAR的解压思路明显还是把文件按顺序从头解到尾，看来当年备份/恢复工具之争的影响，还真是深远。

二、固实（solid）压缩方式

在压缩算法方面，我觉得rar格式最特色的是固实（solid）压缩方式。WinRAR v3.42的帮助文件中对固实压缩的说明如下：
固实压缩文件是 RAR 的一种特殊压缩方式存储的压缩文件，它把压缩文件中的全部文件都当成一个连续数据流来看待。
这段说明其实揭示了固实压缩格式能够提高压缩比的奥秘：数据压缩的基础是“重复”，例如aaaabbb这个字符串，里面就有重复，如果表示为a4b3，看起来是不是变短了？这就是“数据压缩”。“重复”是一个具有相对意义的概念，在某一范围内看起来没有重复，或重复不多的数据，把范围扩大，说不定就能找到更多重复的数据了，这就是固实压缩的奥秘。

举一个简单的例子：用zip和普通rar压缩一堆jpg文件，很难压下去，但是用固实压缩方式的rar就可以，其原因就在于：jpg文件本身已经是压缩格式了，单个jpg文件里很难再 找到可利用的重复数据，因此不论是用zip还是普通的rar都很难再压缩，因为他们都将需要压缩的文件分隔开来一个一个处理。但是对于固实rar来说，是将 所有需要压缩的jpg文件当作一个整体来压缩，这些jpg之间就存在重复的数据，如他们都有相同的文件头（其中包括各种数据表）等，这就出现了可压缩的空间。从我看到的资料来看，Flash文件也采用了类似的技术对jpg进行压缩：如果在Flash文件中使用了多个jpg文件，它们可以共用一个文件头。
当然天下不会有白吃的午餐，固实压缩方式在提高压缩比的同时，也有一些限制，在WinRAR v3.42帮助文件中的说法是：

固实压缩可增加压缩性能，特别是在添加大量的小文件的时候，但它也有一些重要的不利因素:

  • 对已存在的固实压缩文件更新时较慢；
  • 要从固实的压缩文件解压单个文件时，它之前的文件都需先经过分析。这造成当从固实的压缩文件内取出文件时会比一般压缩文件取出文件慢一些。但是，当从固实的压缩文件解压全部的文件时，解压速度并没有影响。
  • 如果在固实压缩文件中的任何文件损坏了，要从损坏的范围中解压全部的文件是不可能的。因此，如果固实压缩文件是保存在例如软盘等媒介时，推荐你在制作时使用“恢复记录”。

固实压缩的适用场合为:

  • 压缩文件很少更新的时候;
  • 不需要经常从压缩文件中解压一个文件或是部分文件的时候;
  • 压缩效率比压缩速度更为重要的时候。

与前面说的“随机访问”对应，固实压缩的RAR文件可能是世界上最不适合随机访问的：如果需要访问固实RAR包中的某个文件，就要从文件头开始解压，一直解到这个文件。

三、安全性

这里的安全性包含几个方面的含义：文件系统安全性、密码保护安全性和文件数据安全性。

由于制订zip格式规范的时候操作系统本身的文件安全性还没有引起足够的重视，因此zip格式只记录最基本的文件属性，包括只读属性等，没有其它附加的安全属性。

rar格式刚推出的时候，文件系统的安全性只能参照DOS，和zip差不多。但是rar毕竟是一种封闭的格式，想怎么改作者一个人说了就算，因此当Windows中出现NTFS，并且引入扩展的文件系统安全属性时，rar也积极跟进，所以现在应该说rar格式在这方面比zip强 。

在zip和rar格式中均提供了密码保护功能，但是密码保护的安全强度不同。

zip由于格式开放、代码开源，因此zip密码破解软件出现得比较早，也比较多。初期以暴力破解为主，威胁不大，真正对zip密码安全的致命一击是known plain text（已知明文）攻击法：如果知道加密zip文件中某段内容（密文，ciphertext）解密后的真正内容（明文，plain text），就可以反推出zip加密口令。在这种攻击方法的威胁，及某些国家的法律对密码技术的限制下， 著名开源组织zlib宣布永久放弃对加密zip的支持，详见zlib网站上的相关说明（不过在zlib发行的源代码里仔细找找，还是能找到原来的加/解密相关代码）。

记得rar刚推出的时候也和zip一样，虽然不能列出加密文件中的文件内容，但可以列出加密文件中的文件名。后来大概也是被known plain text攻击法吓到了，增加了一个“加密文件名”选项，干脆连加密rar文件里有哪些文件都看不见，让攻击者想猜明文都无从猜起。

rar格式比zip晚推出，在安全方面吸取了足够的教训，因此采用的是美国国家标准与技术局（National Institute of Standard and Technology, NIST）推荐的、目前公认安全程度比较高的AES对称加密算法 ，密钥长度128位。在ASE被攻破以前（NIST认为30年内无法攻破），大家都只能在暴力法上兜圈子，所以密码安全性应该说比zip高。对此WinRAR 3.42的帮助文件是这样描述的：

ZIP 格式使用私有加密算法。 RAR 压缩文件使用更强大的 AES-128 标准加密。如果你需要加密重要的信息，选择 RAR 压缩文件格式会比较好一些。为了确实的安全性，密码长度请最少要 8 个字符。不要使用任何语言的单词作为密码，最好是任意的随机组合字符和数字，并且要注意密码的大小写。请记住，如果你遗失你的密码，你将无法取出加密的文件，就算是 WinRAR 的作者本身也无法解压加密过的文件。

在数据安全性方面，RAR格式本身支持一种特殊的附加信息类型，叫做“恢复记录”。如果RAR文件有恢复记录，在介质物理损坏或其它原因造成数据丢失时，WinRAR可以按照“恢复记录”尝试对数据进行修复。而zip格式无恢复记录，因此在数据安全性方面应该说比RAR弱。

虽然RAR文件本身支持恢复记录，但是在WinRAR里此选项缺省是关闭的，而打开后会导致压缩出来的RAR文件体积增加（增加的百分比与设置有关），可能会令某些人感到不习惯（我就亲眼见到有人在论坛上抱怨为什么压出来的RAR文件会如此庞大），所以这个功能基本上形同虚设。

四、开放性

开放性的对比很明显：zip格式不仅文件格式完全公开，而且有专门的开源组织提供操作源代码，跨平台使用也没有多大限制；rar格式完全保密，作者只提供解压所需源代码，不提供压缩所需源代码 ，跨平台使用有点麻烦。

zip开源组织中，最出名的是zlib和InfoZip，二者各有侧重：zlib偏重对内存缓冲区的压缩，因此被png等开源组织用做内部压缩算法，连java的jar程序内核都来自zlib，打出来的jar包自然也是一个标准的zip文件；InfoZip偏重对文件的操作 （包括口令保护），应用似乎不如zlib广泛，但我个人觉得其实它还是满好用的，前提是需要对它的源代码进行一些必要的修改。

在png组织的网页中有说到png格式的来历，我觉得也很有意思：做png的一班人，其实原来都是做gif格式的，但是由于Unisys公司开始对gif格式的核心——LZW压缩算法征收专利费，这帮人怒了，干脆提出png格式：大结构方面还是采用分段结构，但是核心压缩算法采用开源的zlib，压缩 效果在多数情况下比gif的LZW更强。由于没有版权限制，在静态图形领域png得到广泛应用，如果不是及时提出动画支持并因此在web上大行其道，我估计gif早就死掉了。

RAR的解压源代码在其官方网站www.rarlab.com上提供，通常比WinRAR的正式版本晚一点，不过据说是直接从WinRAR的源代码中抠出来的，所以兼容性应该没有什么问题。

五、结论

以下观点纯属个人观点，仅供参考，不具有如何指导意义：

  • 如果经常需要对压缩包进行随机访问，应该选zip而不是rar。虽然将下载到的rar重新压缩成zip会麻烦一次，但是以后会减少无数的麻烦。
  • 如果需要分卷压缩（如某些网站对上传文件大小有限制），则只能用rar。事实上，这也是我唯一会使用rar格式的场合，其它时候一律zip没商量。

 

【zlib、gzip、zip的区别】

http://blog.csdn.net/wyingquan/archive/2008/06/14/2547664.aspx

【zlib、gzip、zip的区别】

zlib是一种数据压缩程序库，它的设计目标是处理单纯的数据（而不管数据的来源是什么）。

gzip是一种文件压缩工具（或该压缩工具产生的压缩文件格式），它的设计目标是处理单个的文件。gzip在压缩文件中的数据时使用的就是zlib。为了保存与文件属性有关的信息，gzip需要在压缩文件（*.gz）中保存更多的头信息内容，而zlib不用考虑这一点。但gzip只适用于单个文件，所以我们在UNIX/Linux上经常看到的压缩包后缀都是*.tar.gz或*.tgz，也就是先用tar把多个文件打包成单个文件，再用gzip压缩的结果。

zip是适用于压缩多个文件的格式（相应的工具有PkZip和WinZip等），因此，zip文件还要进一步包含文件目录结构的信息，比gzip的头信息更多。但需要注意，zip格式可采用多种压缩算法，我们常见的zip文件大多不是用zlib的算法压缩的，其压缩数据的格式与gzip大不一样。

Java SDK提供了对上述三种压缩技术的支持：Inflater类和Deflater类直接用zlib库对数据压缩/解压缩，GZIPInputStream类和GZIPOutputStream类提供了对gzip格式的支持，ZipFile、ZipInputStream、ZipOutputStream则用于处理zip格式的文件。

所以，你应当根据你的具体需求，选择不同的压缩技术：如果只需要压缩/解压缩数据，你可以直接用zlib实现，如果需要生成gzip格式的文件或解压其他工具的压缩结果，你就必须用gzip或zip等相关的类来处理了。

【DEFLATE】

DEFLATE 是同时使用了 LZ77 算法与哈夫曼编码的一个无损数据压缩算法。它最初是由 Phil Katz 为他的 PKZIP 归档工具第二版所定义的，后来定义在 RFC1951 规范中。

人们普遍认为 DEFLATE 不受任何专利所制约，并且在 LZW（GIF 文件格式使用）相关的专利失效之前，这种格式除了在ZIP文件格式中得到应用之外也在 gzip 压缩文件以及 PNG 图像文件中得到了应用。

DEFLATE 压缩与解压的源代码可以在自由、通用的压缩库 zlib 上找到。

更高压缩率的 DEFLATE 是 7-zip 所实现的。AdvanceCOMP 也使用这种实现，它可以对 gzip、PNG、MNG 以及 ZIP 文件进行压缩从而得到比 zlib 更小的文件大小。在 Ken Silverman 的 KZIP 与 PNGOUT 中使用了一种更加高效同时要求更多用户输入的 DEFLATE 程序。

【INFLATE】

inflate是GZip, PNG等广泛使用的解压算法,linux也使用inflate对内核进行解压.inflate的解压算法使用的第3种快速解压法的一个子集,它不考虑LONG_CODE,同时把SAME_LENGTH合并到MEDIUM_CODE。而对于规则的SAME_LENGTH编码，比如length和distance编码，inflate则使用额外的base和extra表示。这是因为在构造一般的查找表时，虽然对于SAME_LENGTH前缀可以不构造副表，但我们需要另外一个表格来保存符号的顺序，而这个表格的空间可能更大。但对于length和distance编码，他们的顺序是递增的，所以无需额外的表格来保存符号的顺序。

inflate使用root表示上述的b,查找表的数据结构为code.主表和副同时保存在inflate_state结构中的大数组codes[ENOUGH]中.表的构造函数位于inftrees.c文件的inflate_table中.

【7z】

7z 是一种新的压缩格式，它拥有目前最高的压缩比。

7z 已公开了结构编辑功能，所以它可以支持任何一种新的压缩算法。到目前为止，下列压缩算法已被整合到了 7z 中：

压缩算法  备注 LZMA  LZ77 改良和优化算法后的最新版本 PPMD  基于 Dmitry Shkarin 之上的算法 PPMdH 并加以优化 BCJ  32-位 x86 可执行文件转换程序 BCJ2  32-位 x86 可执行文件转换程序 BZip2  标准 BWT 算法 Deflate  标准 LZ77-based 算法