chapter3.htm

数据压缩教程！

<pre>   a - 0    b - 100    c - 101    d - 110    e - 111</pre>

<p>对例子中信息的编码为：</p>

<pre>cabcedeacacdeddaaabaababaaabbacdebaceada</pre>

<pre>101 0 100 101 111 110 111 0 101 0 101 ......</pre>

<p>码长共 88 位。这比使用 Shannon-Fano
编码要更短一点。</p>

<p>让我们回顾一下熵的知识，使用我们在第二章学到的计算方法，上面的例子中，每个字符的熵为：</p>

<pre>Ea = - log<font size="3"><sub>2</sub></font>(16 / 40) = 1.322
Eb = - log<font size="3"><sub>2</sub></font>( 7 / 40) = 2.515
Ec = - log<font size="3"><sub>2</sub></font>( 6 / 40) = 2.737
Ed = - log<font size="3"><sub>2</sub></font>( 6 / 40) = 2.737
Ee = - log<font size="3"><sub>2</sub></font>( 5 / 40) = 3.000</pre>

<p align="left">信息的熵为：</p>
<div align="left">

<pre>E = Ea * 16 + Eb * 7 + Ec * 6 + Ed * 6 + Ee * 5 = 86.601</pre>
</div>

<p align="left">也就是说，表示该条信息最少需要
86.601 位。我们看到，Shannon-Fano 编码和 Huffman
编码都已经比较接近该信息的熵值了。同时，我们也看出，无论是
Shannon-Fano 还是 Huffman，都只能用近似的整数位来表示单个符号，而不是理想的小数位。我们可以将它们做一个对比：</p>
<div align="left">

<pre>   符号      理想位数     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</pre>
</div>

<p align="left">这就是象 Huffman
这样的整数位编码方式无法达到最理想的压缩效果的原因。</p>

<p align="left"><strong>为 Huffman
编码选择模型（附范式 Huffman 编码）</strong></p>

<p align="left">最简单，最容易被 Huffman
编码利用的模型是“静态统计模型”，也就是说在编码前统计要编码的信息中所有字符的出现频率，让后根据统计出的信息建立编码树，进行编码。这种模型的缺点是显而易见的：首先，对数据量较大的信息，静态统计要消耗大量的时间；其次，必须保存统计出的结果以便解码时构造相同的编码树，或者直接保存编码树本身，而且，对于每次静态统计，都有不同的结果，必须分别予以保存，这要消耗大量的空间（这意味着压缩效率的下降）；再次，事实上，即使不将编码树计算在内，对通常含有
0 - 255 字符集的计算机文件来说，静态统计模型统计出的频率是字符在整个文件中的出现频率，往往反映不出字符在文件中不同局部出现频率的变化情况，使用这一频率进行压缩，大多数情况下得不到太好压缩效果，文件有时甚至在压缩后反而增大了。所以，“静态统计模型”一般仅作为复杂算法的某一部分出现，在信息的某一局部完成压缩功能。我们很难将其用于独立的压缩系统。</p>

<p align="left">有一种有效的“静态统计模型”的替代方案，如果我们要压缩的所有信息具有某些共同的特性，也即在分布上存在着共同的特征，比如我们要压缩的是普通的英文文本，那么，字母
a 或者字母 e 的出现频率应当是大致稳定的。使用语言学家事先已经建立好的字母频率表来进行压缩和解压缩，不但不用保存多份统计信息，而且一般说来对该类文件有着较好的压缩效果。这种方案除了适应性不太强以外，偶尔还会有一些尴尬的时候。读一遍下面这段话：</p>

<p align="left">If Youth，throughout all history， had had a
champion to stand up for it； to show a doubting world that a
child can think；and， possibly， do it practically； you
wouldn't constantly run across folks today who claim that &quot;a
child don't know anything.&quot; - <em>Gadsby</em> by <em>E.V.Wright,
1939.</em></p>

<p align="left">发现什么问题了吗？哦，整段话中竟没有出现一次英文中出现频率最高的字母
e ！真让人惊讶，但没有办法，事先拟定的频率分布总有意外的时候。</p>

<p align="left">对英文或中文文本，有一种比较实用的静态模型：不是把字符而是把英文单词或中文词语作为统计频率和编码的单位进行压缩。也就是说，每次编码的不再是
a b c 这样的单个符号，而是 the look flower
这样的单词。这种压缩方式可以达到相当不错的压缩效果，并被广泛地用于全文检索系统。</p>

<p align="left">对基于词的编码方式，需要解决几个技术难点。首先是分词的问题，英文单词可以由词间空格分隔，但中文怎么办呢？其实，有很多中文分词算法可以解决这个问题，本书就不再详细介绍了。王笨笨就曾开发过一个不错的分词模块，但希望通过收取一定报酬的方式提供该模块，如有需要，请和王笨笨
E-Mail 联系。一旦我们将词语分离出来，我们就可以对每个词进行频率统计，然后建立
Huffman 编码树，输出编码时，一个编码将代替一个词语。但要注意，英文和汉语的单词数量都在几万到十几万左右，也就是说，我们的
Huffman
编码树将拥有十几万个叶子节点，这对于一棵树来说太大太大了，系统将无力承担所需要的资源，这怎么办呢？我们可以暂时抛开树结构，采用另一种构造
Huffman 编码的方式——范式 Huffman 编码。</p>

<p align="left">范式 Huffman 编码(Canonical Huffman Code)的基本思路是：并非只有使用二叉树建立的前缀编码才是
Huffman 编码，只要符合(1)是前缀编码(2)某一字符编码长度和使用二叉树建立的该字符的编码长度相同这两个条件的编码都可以叫做
Huffman 编码。考虑对下面六个单词的编码：</p>
<div align="left">

<pre>  符号   出现次数   传统 Huffman 编码    范式 Huffman 编码
------------------------------------------------------------
  单词1     10           000                 000
  单词2     11           001                 001
  单词3     12           100                 010
  单词4     13           101                 011
  单词5     22           01                  10
  单词6     23           11                  11</pre>
</div>

<p align="left">注意到范式 Huffman
编码的独特之处了吗？你无法使用二叉树来建立这组编码，但这组编码确实能起到和
Huffman 编码相同的作用。而且，范式 Huffman
编码具有一个明显的特点：当我们把要编码的符号按照其频率从小到大排列时，如果把范式
Huffman
编码本身作为单词的话，也呈现出从小到大的字典顺序。</p>

<p align="left">构造范式 Huffman 编码的方法大致是：</p>

<p align="left">1) 统计每个要编码符号的频率。</p>

<p align="left">2)
根据这些频率信息求出该符号在传统 Huffman
编码树中的深度（也就是表示该符号所需要的位数
-
编码长度）。因为我们关心的仅仅是该符号在树中的深度，我们完全没有必要构造二叉树，仅用一个数组就可以模拟二叉树的创建过程并得到符号的深度，具体方法这里就不详述了。</p>

<p align="left">3) 分别统计从最大编码长度 maxlength
到 1 的每个长度对应了多少个符号。根据这一信息从
maxlength 个 0
开始以递增顺序为每个符号分配编码。例如，编码长度为
5 的符号有 4 个，长度为 3 的有 1 个，长度为 2
的有 3 个，则分配的编码依次为： 00000 00001 00010
00011 001 01 10 11</p>

<p align="left">4)
编码输出压缩信息，并保存按照频率顺序排列的符号表，然后保存每组同样长度编码中的最前一个编码以及该组中的编码个数。</p>

<p align="left">现在完全可以不依赖任何树结构进行高速解压缩了。而且在整个压缩、解压缩过程中需要的空间比传统
Huffman 编码少得多。</p>

<p align="left">最后要提到的是，Huffman
编码可以采用自适应模型，根据已经编码的符号频率决定下一个符号的编码。这时，我们无需为解压缩预先保存任何信息，整个编码是在压缩和解压缩过程中动态创建的，而且自适应编码由于其符号频率是根据信息内容的变化动态得到的，更符合符号的局部分布规律，因此在压缩效果上比静态模型好许多。但是，采用自适应模型必须考虑编码表的动态特性，即编码表必须可以随时更新以适应符号频率的变化。对于
Huffman
编码来说，我们很难建立能够随时更新的二叉树，使用范式
Huffman
编码是个不错的选择，但依然存在不少技术上的难题。幸好，如果愿意的话，我们可以暂时不考虑自适应模型的
Huffman 编码，因为对于自适应模型我们还有许多更好的选择，下面几章将要谈到的算术编码、字典编码等更为适合采用自适应模型，我们将在其中深入探讨自适应模型的各种实现方法。</p>
<div align="center"><center>

<address>
    <a href="Chapter2.htm">第二章</a> <a href="Chapter4.htm">第四章</a>
</address>
</center></div>

<p align="center">　</p>
<div align="right">

<address>
    <a href="mailto:[e-mail]">有问题吗？有建议吗？快给王笨笨写信</a>
</address>
</div><div align="right">

<address>
    <strong>章节书签：</strong><a href="default.htm">前言</a>
    <a href="content.htm">目录</a> <a href="Chapter1.htm">1</a>
    <a href="Chapter2.htm">2</a> <a href="Chapter3.htm">3</a> <a
    href="Chapter4.htm">4</a> <a href="Chapter5.htm">5</a> <a
    href="Chapter6.htm">6</a> <a href="Chapter7.htm">7</a> <a
    href="Chapter8.htm">8</a> <a href="Chapter9.htm">9</a> <a
    href="Chapter10.htm">10</a> <a href="Chapter11.htm">11</a> <a
    href="Chapter12.htm">12</a> 
</address>
</div>
</body>
</html>