jjj.txt

数据压缩技术的原理

              题目-----数据压缩技术
  目的：通过数据压缩技术减少计算机中存储数据或是通信传播中数据的冗余度，从而增大数据密度，
        使数据的存储空间减少。
  数据压缩和编码技术：
         数据压缩和编码技术联系紧密，压缩的实质就是根据数据的内在联系将数据从一种编码映射为
         另一种编码。压缩前的数据要被划分为一个一个的基本单元，成为原消息。原消息集映射的结
         果为码子集。压缩前的数据是原消息序列。压缩后的数据是码子序列。
   编码算法：1：Huffman编码：有些致命弱点
             2：算术编码：更接近信息论中"熵"极限的算法        
             3：LZ77,LZ78编码技术：2位以色列人提出的
             4：高性能数据压缩技术。
    熵的定义：
             熵是用来表示一条信息中真正需要编码的信息量。
             用 0 和 1 组成的二进制数码为含有 n 个符号的某条信息编码，假设符号 Fn 在整条信息
            中重复出现的概率为 Pn，则该符号的熵也即表示该符号所需的位数位为：En = - log2( Pn )
             ，整条信息的熵也即表示整条信息所需的位数为：E = ∑En
             举个例子，对下面这条只出现了 a b c 三个字符的字符串：aabbaccbaa
             字符串长度为 10，字符 a b c 分别出现了 5 3 2 次，则 a b c 在信息中出现的概率分别为
              0.5 0.3 0.2，他们的熵分别为：
              Ea = -log2(0.5) = 1
              Eb = -log2(0.3) = 1.737
              Ec = -log2(0.2) = 2.322
            整条信息的熵也即表达整个字符串需要的位数为：E = Ea * 5 + Eb * 3 + Ec * 2 = 14.855 位
数据压缩的基本准则：
             现在知道信息为什么能被压缩而不丢失原有的信息内容了吧。简单地讲，用较少的位数表
             示较频繁出现的符号，这就是数据压缩的基本准则。
 模型：
       要压缩一条信息，首先要分析清楚信息中每个符号出现的概率。
       不同的压缩程序通过不同的方法确定符号的出现概率，对符号
       的概率计算得越准确，也就越容易得到好的压缩效果。
       在压缩程序中，用来处理输入信息，计算符号的概率并决定输出哪个或哪些代码的模块叫做模型。
  困难（模型）：
             难道对信息中字符的出现概率这么难以估计以至于有各种不同的压缩模型吗？对上面的字符
             串我们不是很容易就知道每个字符的概率了吗？是的是的，不过上面的字符串仅有 10 个字
             符长呀，那只是例子而已。考虑我们现实中要压缩的文件，大多数可是有几十 K 甚至几
             百 K 长，几 M 字节的文件不是也屡见不鲜吗？
  静态统计模型：
             是的，我们可以预先扫描文件中的所有字符，统计出每个字符出现的概率，这种方法在压缩
             术语里叫做“静态统计模型”。
             但是，不同的文件中，字符有不同的分布概率，我们要么先花上大量的时间统计我们要压缩
             的所有文件中的字符概率，要么为每一个单独的文件保存一份概率表以备解压缩时需要。糟
             糕的是，不但扫描文件要消耗大量时间，而且保存一份概率表也使压缩后的文件增大了不少。
             所以，在实际应用中，“静态统计模型”应用的很少。
 自适应模型：
             真正的压缩程序中使用的大多是一种叫“自适应模型”的东西。自适应模型可以说是一台具有
             学习功能的自动机。他在信息被输入之前对信息内容一无所知并假定每个字符的出现概率均
             等，随着字符不断被输入和编码，他统计并纪录已经出现过的字符的概率并将这些概率应用
             于对后续字符的编码。也就是说，自适应模型在压缩开始时压缩效果并不理想，但随着压缩
             的进行，他会越来越接近字符概率的准确值，并达到理想的压缩效果。自适应模型还可以适
             应输入信息中字符分布的突然变化，可以适应不同的文件中的字符分布而不需要保存概率表。
上面提到的模型可以统称为“统计模型”。
   编码：
      通过模型，我们已经确定了对某一个符号该用多少位二进制数进行编码。现在的问题是，如何设计一
      种编码方案，使其尽量精确地用模型计算出来的位数表示某个符号。
前缀编码：
        该技术的主导思想是，任何一个字符的编码，都不是另一个字符编码的前缀。反过来说就是，任何
        一个字符的编码，都不是由另一个字符的编码加上若干位 0 或 1 组成。看一下前缀编码的一个最
        简单的例子：
        符号        编码
         A           0
         B           10
         C           110
         D           1110
         E           11110
有了上面的码表，你一定可以轻松地从下面这串二进制流中分辨出真正的信息内容了：
1110010101110110111100010 - DABBDCEAAB
下一个问题是：象上面这样的前缀编码只能表示整数位的符号，对几点几位的符号只能用近似的整数位
输出，那么怎样输出小数位数呢？科学家们用算术编码解决了这个问题，我们将在第四章对算术编码作
详细的讨论。
总结：
      不同的模型使用不同的方法计算字符的出现概率，由此概率可以得出字符的熵；然后使用不同的
      编码方法，尽量接近我们期望得到的熵值。所以，压缩效果的好坏一方面取决于模型能否准确地
      得到字符概率，另一方面也取决于编码方法能否准确地用期望的位数输出字符代码。换句话说，
      压缩 = 模型 + 编码。
 如下图所示：
  ---------  符号   ----------  概率   ----------  代码   ----------
|  输入 |-------->|  模型  |-------->|  编码  |-------->|  输出  |
---------         ----------         ----------         ---------- 
 Shannon-Fano 编码原理：
 讨论之前，我们假定要编码字符的出现概率已经由某一模型统计出来，例如，对下面这串出现了五种字
 符的信息( 40 个字符长 ):
 cabcedeacacdeddaaabaababaaabbacdebaceada
五种字符的出现次数分别：a - 16，b - 7，c - 6，d - 6，e - 5。
Shannon-Fano 编码的核心仍然是构造二叉树，构造的方式非常简单：
1) 将给定符号按照其频率从大到小排序。对上面的例子，应该得到：
    a - 16
    b - 7
    c - 6
    d - 6
    e - 5
2) 将序列分成上下两部分，使得上部频率总和尽可能接近下部频率总和。我们有：
    a - 16
    b - 7
-----------------
    c - 6
    d - 6
    e - 5
3) 我们把第二步中划分出的上部作为二叉树的左子树，记 0，下部作为二叉树的右子树，记 1
4) 分别对左右子树重复 2 3 两步，直到所有的符号都成为二叉树的树叶为止。现在我们有如下的二叉树：
 根(root)
            0     |     1
           +------+------+
      0    |    1     0  |   1
     +-----+-----+   +---+----+
     |           |   |        |
     a           b   c        |
                         0    |    1
                        +-----+-----+
                        |           |
                        d           e
 于是我们得到了此信息的编码表：
 a - 00  b - 01  c - 10  d - 110  e - 111
可以将例子中的信息编码为：
cabcedeacacdeddaaabaababaaabbacdebaceada
10 00 01 10 111 110 111 00 10 00 10 ......
码长共 91 位。考虑用 ASCII 码表示上述信息需要 8 * 40 = 240 位，我们确实实现了数据压缩。

 Haffman编码原理：
  二叉树和二进制编码 
  为什么压缩领域中的编码方法总和二叉树联系在一起呢？原因非常简单，回忆一下我们介绍过的“前缀编
  码”：为了使用不固定的码长表示单个字符，编码必须符合“前缀编码”的要求，即较短的编码决不能是较
  长编码的前缀。要构造符合这一要求的二进制编码体系，二叉树是最理想的选择。
  Huffman 编码构造二叉树的方法和 Shannon-Fano 正好相反，不是自上而下，而是从树叶到树根生成二叉
  树。现在，我们仍然使用上面的例子来学习 Huffman 编码方法。
  1) 将各个符号及其出现频率分别作为不同的小二叉树（目前每棵树只有根节点）。
   a(16)     b(7)    c(6)    d(6)    e(5)
2) 在 1 中得到的树林里找出频率值最小的两棵树，将他们分别作为左、右子树连成一棵大一些的二叉树，
该二叉树的频率值为两棵子树频率值之和。对上面的例子，我们得到一个新的树林：
                                     | (11)
   a(16)     b(7)     c(6)       +---+---+        
                                 |       |
                                 d       e
 3) 对上面得到的树林重复 2 的做法，直到所有符号都连入树中为止。这一步完成后，我们有这样的二叉
 树：
 根(root)
            0     |     1
           +------+----------------+
           |              0        |          1
           |             +---------+-----------+
           |      0      |     1        0      |      1
           a     +-------+------+      +-------+-------+
                 |              |      |               |
                 b              c      d               e 
 由此，我们可以建立和 Shannon-Fano 编码略微不同的编码表：
  a - 0    b - 100    c - 101    d - 110    e - 111
  对例子中信息的编码为：
cabcedeacacdeddaaabaababaaabbacdebaceada
101 0 100 101 111 110 111 0 101 0 101 ......
码长共 88 位。这比使用 Shannon-Fano 编码要更短一点。
让我们回顾一下熵的知识，使用我们在第二章学到的计算方法，上面的例子中，每个字符的熵为：
Ea = - log2(16 / 40) = 1.322
Eb = - log2( 7 / 40) = 2.515
Ec = - log2( 6 / 40) = 2.737
Ed = - log2( 6 / 40) = 2.737
Ee = - log2( 5 / 40) = 3.000
信息的熵为：
E = Ea * 16 + Eb * 7 + Ec * 6 + Ed * 6 + Ee * 5 = 86.601
也就是说，表示该条信息最少需要 86.601 位。我们看到，Shannon-Fano 编码和 Huffman 编码都已经
比较接近该信息的熵值了。同时，我们也看出，无论是 Shannon-Fano 还是 Huffman，都只能用近似的
整数位来表示单个符号，而不是理想的小数位。我们可以将它们做一个对比：
 符号      理想位数     S-F 编码    Huffman 编码
             ( 熵 )       需要位数    需要位数
 ----------------------------------------------------
    a         1.322         2           1
    b         2.515         2           3
    c         2.737         2           3
    d         2.737         3           3
    e         3.000         3           3
 ----------------------------------------------------
  总 计      86。601        91          88                
这就是象 Huffman 这样的整数位编码方式无法达到最理想的压缩效果的原因。
为 Huffman 编码选择模型（附范式 Huffman 编码）：
最简单，最容易被 Huffman 编码利用的模型是“静态统计模型”，也就是说在编码前统计要编码的信息中
所有字符的出现频率，让后根据统计出的信息建立编码树，进行编码。这种模型的缺点是显而易见的：首
先，对数据量较大的信息，静态统计要消耗大量的时间；
构造范式 Huffman 编码的方法大致是：
1) 统计每个要编码符号的频率。
2) 根据这些频率信息求出该符号在传统 Huffman 编码树中的深度（也就是表示该符号所需要的位数 - 编
码长度）。因为我们关心的仅仅是该符号在树中的深度，我们完全没有必要构造二叉树
3) 分别统计从最大编码长度 maxlength 到 1 的每个长度对应了多少个符号。
4) 编码输出压缩信息，并保存按照频率顺序排列的符号表，然后保存每组同样长度编码中的最前一个编
 码以及该组中的编码个数。
最后要提到的是，Huffman 编码可以采用自适应模型，根据已经编码的符号频率决定下一个符号的编码。
这时，我们无需为解压缩预先保存任何信息，整个编码是在压缩和解压缩过程中动态创建的，而且自适应
编码由于其符号频率是根据信息内容的变化动态得到的，更符合符号的局部分布规律，因此在压缩效果上
比静态模型好许多。但是，采用自适应模型必须考虑编码表的动态特性，即编码表必须可以随时更新以适
应符号频率的变化。对于 Huffman 编码来说，我们很难建立能够随时更新的二叉树，使用范式 Huffman 
编码是个不错的选择，但依然存在不少技术上的难题。
算术编码：