返回首页
当前位置: 主页 > 互联网技术 > 网络安全 >

zip 的压缩原理与实现(2)

时间:2014-12-01 13:19来源:电脑教程学习网 www.etwiki.cn 编辑:admin

压缩文件无法再次压缩是因为:
1. 短语式压缩去掉了三个字节以上的重复,压缩后的结果中包含的是未匹配的单双字节,和匹配距离、长度的组合。这个结果当然仍然可能包含三个字节以上的重复,但是概率极低。因为三个字节有 256 * 256 * 256 共一千六百多万种可能的情况。
所以只要把原始文件中“自然存在”的短语式重复倾向压掉就可以了,一千六百万分之一的概率再去压缩没有必要。
2.编码式压缩利用各个单字节使用频率不一样的倾向,使定长编码变为不定长编码,给使用频率高的字节更短的编码,使用频率低的字节更长的编码,起到压缩的效果。如果把编码式压缩的“结果”按照8位作为1字节,重新统计各字节的使用频率,应该是大致相等的。因为新的字节使用频率是随机的。相等的频率再去变换字节长短是没有意义的,因为变短的字节没有比变长的字节更多。
所以压掉了原始文件中“自然存在”的单字节使用频率不均匀的倾向后,随机的使用频率再去压缩也失去了意义。

首先,为了使用不定长的编码表示单个字符,编码必须符合“前缀编码”的要求,即较短的编码决不能是较长编码的前缀,反过来说就是,任何一个字符的编码,都不是由另一个字符的编码加上若干位 0 或 1 组成,否则解压缩程序将无法解码。
看一下前缀编码的一个最简单的例子:


符号 编码
A 0
B 10
C 110
D 1110
E 11110

有了上面的码表,你一定可以轻松地从下面这串二进制流中分辨出真正的信息内容了:

1110010101110110111100010 - DABBDCEAAB

要构造符合这一要求的二进制编码体系,二叉树是最理想的选择。考察下面这棵二叉树:

        根(root)
       0  |   1
       +-------+--------+
    0  | 1   0  |  1
    +-----+------+ +----+----+
    |     | |     |
    a      | d     e
     0  |  1
     +-----+-----+
     |     |
     b     c

要编码的字符总是出现在树叶上,假定从根向树叶行走的过程中,左转为0,右转为1,则一个字符的编码就是从根走到该字符所在树叶的路径。正因为字符只能出现在树叶上,任何一个字符的路径都不会是另一字符路径的前缀路径,符合要求的前缀编码也就构造成功了:

a - 00 b - 010 c - 011 d - 10 e - 11


接下来来看编码式压缩的过程:
为了简化问题,假定一个文件中只出现了 a,b,c,d ,e四种字符,它们的出现次数分别是
a : 6次
b : 15次
c : 2次
d : 9次
e : 1次
如果用定长的编码方式为这四种字符编码: a : 000 b : 001 c : 010 d : 011 e : 100
那么整个文件的长度是 3*6 + 3*15 + 3*2 + 3*9 + 3*1 = 99

用二叉树表示这四种编码(其中叶子节点上的数字是其使用次数,非叶子节点上的数字是其左右孩子使用次数之和):

          根
           |
      +---------33---------+
      |        |
   +----32---+     +----1---+
   |    |     |    |
+-21-+   +-11-+    +--1--+  
|   |   |   |    |   |
6  15  2  9    1   

(如果某个节点只有一个子节点,可以去掉这个子节点。)

         根
         |
        +------33------+
       |     |
    +-----32----+     1
    |      |
  +--21--+  +--11--+
  |   |  |   |
  6   15 2    9

现在的编码是: a : 000 b : 001 c : 010 d : 011 e : 1 仍然符合“前缀编码”的要求。

第一步:如果发现下层节点的数字大于上层节点的数字,就交换它们的位置,并重新计算非叶子节点的值。
先交换11和1,由于11个字节缩短了一位,1个字节增长了一位,总文件缩短了10位。

           根
            |
       +----------33---------+
       |        |
   +-----22----+     +----11----+
   |      |     |     |
+--21--+    1      2     9
|     |
6   15

再交换15和1、6和2,最终得到这样的树:

           根
            |
       +----------33---------+
       |        |
     +-----18----+    +----15----+
    |      |    |     |
  +--3--+    15   6     9
  |   |
  2   1

这时所有上层节点的数值都大于下层节点的数值,似乎无法再进一步压缩了。但是我们把每一层的最小的两个节点结合起来,常会发现仍有压缩余地。

第二步:把每一层的最小的两个节点结合起来,重新计算相关节点的值。

在上面的树中,第一、二、四三层都只有一或二个节点,无法重新组合,但第三层上有四个节点,我们把最小的3和6结合起来,并重新计算相关节点的值,成为下面这棵树。

           根
            |
       +----------33---------+
       |         |
    +------9-----+    +----24----+
    |      |    |     |
   +--3--+    6   15    9
   |   |
  2  1

然后,再重复做第一步。
这时第二层的9小于第三层的15,于是可以互换,有9个字节增长了一位,15个字节缩短了一位,文件总长度又缩短了6位。然后重新计算相关节点的值。

           根

------分隔线----------------------------
标签(Tag):电脑知识 电脑教程 电脑技巧
------分隔线----------------------------
推荐内容
猜你感兴趣