微机.docx

微机.docx

《微机.docx》由会员分享，可在线阅读，更多相关《微机.docx（30页珍藏版）》请在冰点文库上搜索。

微机

什么是熵

数据压缩不仅起源于40年代由ClaudeShannon首创的信息论，而且其基本原理即信息究竟能被压缩到多小，至今依然遵循信息论中的一条定理，这条定理借用了热力学中的名词“熵”（Entropy）来表示一条信息中真正需要编码的信息量：

考虑用0和1组成的二进制数码为含有n个符号的某条信息编码，假设符号Fn在整条信息中重复出现的概率为Pn，则该符号的熵也即表示该符号所需的位数位为：

En=-log2（Pn）

整条信息的熵也即表示整条信息所需的位数为：

E=∑En

举个例子，对下面这条只出现了abc三个字符的字符串：

aabbaccbaa

字符串长度为10，字符abc分别出现了532次，则abc在信息中出现的概率分别为0.50.30.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位

回想一下如果用计算机中常用的ASCII编码，表示上面的字符串我们需要整整80位呢！

现在知道信息为什么能被压缩而不丢失原有的信息内容了吧。

简单地讲，用较少的位数表示较频繁出现的符号，这就是数据压缩的基本准则。

细心的读者马上会想到，我们该怎样用01这样的二进制数码表示零点几个二进制位呢？

确实很困难，但不是没有办法。

一旦我们找到了准确表示零点几个二进制位的方法，我们就有权利向无损压缩的极限挑战了。

不要着急，看到第四章就明白了。

模型

从上面的描述，我们明白，要压缩一条信息，首先要分析清楚信息中每个符号出现的概率。

不同的压缩程序通过不同的方法确定符号的出现概率，对符号的概率计算得越准确，也就越容易得到好的压缩效果。

在压缩程序中，用来处理输入信息，计算符号的概率并决定输出哪个或哪些代码的模块叫做模型。

难道对信息中字符的出现概率这么难以估计以至于有各种不同的压缩模型吗？

对上面的字符串我们不是很容易就知道每个字符的概率了吗？

是的是的，不过上面的字符串仅有10个字符长呀，那只是例子而已。

考虑我们现实中要压缩的文件，大多数可是有几十K甚至几百K长，几M字节的文件不是也屡见不鲜吗？

是的，我们可以预先扫描文件中的所有字符，统计出每个字符出现的概率，这种方法在压缩术语里叫做“静态统计模型”。

但是，不同的文件中，字符有不同的分布概率，我们要么先花上大量的时间统计我们要压缩的所有文件中的字符概率，要么为每一个单独的文件保存一份概率表以备解压缩时需要。

糟糕的是，不但扫描文件要消耗大量时间，而且保存一份概率表也使压缩后的文件增大了不少。

所以，在实际应用中，“静态统计模型”应用的很少。

真正的压缩程序中使用的大多是一种叫“自适应模型”的东西。

自适应模型可以说是一台具有学习功能的自动机。

他在信息被输入之前对信息内容一无所知并假定每个字符的出现概率均等，随着字符不断被输入和编码，他统计并纪录已经出现过的字符的概率并将这些概率应用于对后续字符的编码。

也就是说，自适应模型在压缩开始时压缩效果并不理想，但随着压缩的进行，他会越来越接近字符概率的准确值，并达到理想的压缩效果。

自适应模型还可以适应输入信息中字符分布的突然变化，可以适应不同的文件中的字符分布而不需要保存概率表。

上面提到的模型可以统称为“统计模型”，因为他们都是基于对每个字符出现次数的统计得到字符概率的。

另一大类模型叫做“字典模型”。

实际上，当我们在生活中提到“工行”这个词的时候，我们都知道其意思是指“中国工商银行”，类似的例子还有不少，但共同的前提是我们心中都有一本约定俗成的缩写字典。

字典模型也是如此，他并不直接计算字符出现的概率，而是使用一本字典，随着输入信息的读入，模型找出输入信息在字典中匹配的最长的字符串，然后输出该字符串在字典中的索引信息。

匹配越长，压缩效果越好。

事实上，字典模型本质上仍然是基于对字符概率的计算的，只不过，字典模型使用整个字符串的匹配代替了对某一字符重复次数的统计。

可以证明，字典模型得到的压缩效果仍然无法突破熵的极限。

当然，对通用的压缩程序来说，保存一本大字典所需的空间仍然是无法让人忍受的，况且，任何一本预先定义的字典都无法适应不同文件中数据的变化情况。

对了，字典模型也有相应的“自适应”方案。

我们可以随着信息的不断输入，从已经输入的信息中建立合适的字典，并不断更新这本字典，以适应数据的不断变化。

让我们从另一个角度理解一下自适应模型。

CluadeShannon曾试图通过一个“聚会游戏”（partygame）来测定英语的真实信息容量。

他每次向听众公布一条被他隐藏起一个字符的消息，让听众来猜下一个字符是什么，一次猜一个，直到猜对为止。

然后，Shannon使用猜测次数来确定整个信息的熵。

在这个实验中，一种根据前面出现过的字符估计下一个字符概率的模型就存在于听众的头脑中，比计算机中使用的自适应模型更为高级的是，听众除了根据字符出现过的次数外，还可以根据他们对语言的经验进行猜测。

编码

通过模型，我们已经确定了对某一个符号该用多少位二进制数进行编码。

现在的问题是，如何设计一种编码方案，使其尽量精确地用模型计算出来的位数表示某个符号。

最先被考虑的问题是，如果对a用3个二进制位就可以表示，而对b用4个二进制位就可以表示，那么，在解码时，面对一连串的二进制流，我怎么知道哪三个位是a，哪四个位是b呢？

所以，必须设计出一种编码方式，使得解码程序可以方便地分离每个字符的编码部分。

于是有了一种叫“前缀编码”的技术。

该技术的主导思想是，任何一个字符的编码，都不是另一个字符编码的前缀。

反过来说就是，任何一个字符的编码，都不是由另一个字符的编码加上若干位0或1组成。

看一下前缀编码的一个最简单的例子：

 符号       编码

  A          0

  B          10

  C          110

  D          1110

  E          11110

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

1110010101110110111100010-DABBDCEAAB

下一个问题是：

象上面这样的前缀编码只能表示整数位的符号，对几点几位的符号只能用近似的整数位输出，那么怎样输出小数位数呢？

科学家们用算术编码解决了这个问题，我们将在第四章对算术编码作详细的讨论。

总结一下

不同的模型使用不同的方法计算字符的出现概率，由此概率可以得出字符的熵；然后使用不同的编码方法，尽量接近我们期望得到的熵值。

所以，压缩效果的好坏一方面取决于模型能否准确地得到字符概率，另一方面也取决于编码方法能否准确地用期望的位数输出字符代码。

换句话说，压缩=模型+编码。

如下图所示：

--------- 符号  ---------- 概率  ---------- 代码  ----------

│ 输入│-------->│ 模型 │-------->│ 编码 │-------->│ 输出 │

---------        ----------        ----------        ----------

资源

我们已经知道，编写压缩程序往往不能对数据的整个字节进行处理，而是要按照二进制位来读写和处理数据，操作二进制位的函数也就成为了压缩程序中使用最为普遍的工具函数。

第三章奇妙的二叉树：

Huffman的贡献

提起Huffman这个名字，程序员们至少会联想到二叉树和二进制编码。

的确，我们总以Huffman编码来概括D.A.Huffman个人对计算机领域特别是数据压缩领域的杰出贡献。

我们知道，压缩=模型+编码，作为一种压缩方法，我们必须全面考虑其模型和编码两个模块的功效；但同时，模型和编码两个模块又相互具有独立性。

举例来说，一个使用Huffman编码方法的程序，完全可以采用不同的模型来统计字符在信息中出现的概率。

因此，我们这一章将首先围绕Huffman先生最为重要的贡献——Huffman编码展开讨论，随后，我们再具体介绍可以和Huffman联合使用的概率模型。

为什么是二叉树

为什么压缩领域中的编码方法总和二叉树联系在一起呢？

原因非常简单，回忆一下我们介绍过的“前缀编码”：

为了使用不固定的码长表示单个字符，编码必须符合“前缀编码”的要求，即较短的编码决不能是较长编码的前缀。

要构造符合这一要求的二进制编码体系，二叉树是最理想的选择。

考察下面这棵二叉树：

               根（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

Shannon-Fano编码

进入Huffman先生构造的神奇二叉树之前，我们先来看一下它的前身，由ClaudeShannon和R.M.Fano两人提出的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）分别对左右子树重复23两步，直到所有的符号都成为二叉树的树叶为止。

现在我们有如下的二叉树：

               根（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

1000011011111011100100010......

码长共91位。

考虑用ASCII码表示上述信息需要8*40=240位，我们确实实现了数据压缩。

Huffman编码

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

101010010111111011101010101......

码长共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编码利用的模型是“静态统计模型”，也就是说在编码前统计要编码的信息中所有字符的出现频率，让后根据统计出的信息建立编码树，进行编码。

这种模型的缺点是显而易见的：

首先，对数据量较大的信息，静态统计要消耗大量的时间；其次，必须保存统计出的结果以便解码时构造相同的编码树，或者直接保存编码树本身，而且，对于每次静态统计，都有不同的结果，必须分别予以保存，这要消耗大量的空间（这意味着压缩效率的下降）；再次，事实上，即使不将编码树计算在内，对通常含有0-255字符集的计算机文件来说，静态统计模型统计出的频率是字符在整个文件中的出现频率，往往反映不出字符在文件中不同局部出现频率的变化情况，使用这一频率进行压缩，大多数情况下得不到太好压缩效果，文件有时甚至在压缩后反而增大了。

所以，“静态统计模型”一般仅作为复杂算法的某一部分出现，在信息的某一局部完成压缩功能。

我们很难将其用于独立的压缩系统。

有一种有效的“静态统计模型”的替代方案，如果我们要压缩的所有信息具有某些共同的特性，也即在分布上存在着共同的特征，比如我们要压缩的是普通的英文文本，那么，字母a或者字母e的出现频率应当是大致稳定的。

使用语言学家事先已经建立好的字母频率表来进行压缩和解压缩，不但不用保存多份统计信息，而且一般说来对该类文件有着较好的压缩效果。

这种方案除了适应性不太强以外，偶尔还会有一些尴尬的时候。

读一遍下面这段话：

IfYouth，throughoutallhistory，hadhadachampiontostandupforit；toshowadoubtingworldthatachildcanthink；and，possibly，doitpractically；youwouldn'tconstantlyrunacrossfolkstodaywhoclaimthat"achilddon'tknowanything."-GadsbybyE.V.Wright,1939.

发现什么问题了吗？

哦，整段话中竟没有出现一次英文中出现频率最高的字母e！

真让人惊讶，但没有办法，事先拟定的频率分布总有意外的时候。

对英文或中文文本，有一种比较实用的静态模型：

不是把字符而是把英文单词或中文词语作为统计频率和编码的单位进行压缩。

也就是说，每次编码的不再是abc这样的单个符号，而是thelookflower这样的单词。

这种压缩方式可以达到相当不错的压缩效果，并被广泛地用于全文检索系统。

对基于词的编码方式，需要解决几个技术难点。

首先是分词的问题，英文单词可以由词间空格分隔，但中文怎么办呢？

其实，有很多中文分词算法可以解决这个问题，本书就不再详细介绍了。

王笨笨就曾开发过一个不错的分词模块，但希望通过收取一定报酬的方式提供该模块，如有需要，请和王笨笨E-Mail联系。

一旦我们将词语分离出来，我们就可以对每个词进行频率统计，然后建立Huffman编码树，输出编码时，一个编码将代替一个词语。

但要注意，英文和汉语的单词数量都在几万到十几万左右，也就是说，我们的Huffman编码树将拥有十几万个叶子节点，这对于一棵树来说太大太大了，系统将无力承担所需要的资源，这怎么办呢？

我们可以暂时抛开树结构，采用另一种构造Huffman编码的方式——范式Huffman编码。

范式Huffman编码（CanonicalHuffmanCode）的基本思路是：

并非只有使用二叉树建立的前缀编码才是Huffman编码，只要符合

（1）是前缀编码

（2）某一字符编码长度和使用二叉树建立的该字符的编码长度相同这两个条件的编码都可以叫做Huffman编码。

考虑对下面六个单词的编码：

 符号  出现次数  传统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

注意到范式Huffman编码的独特之处了吗？

你无法使用二叉树来建立这组编码，但这组编码确实能起到和Huffman编码相同的作用。

而且，范式Huffman编码具有一个明显的特点：

当我们把要编码的符号按照其频率从小到大排列时，如果把范式Huffman编码本身作为单词的话，也呈现出从小到大的字典顺序。

构造范式Huffman编码的方法大致是：

1）统计每个要编码符号的频率。

2）根据这些频率信息求出该符号在传统Huffman编码树中的深度（也就是表示该符号所需要的位数-编码长度）。

因为我们关心的仅仅是该符号在树中的深度，我们完全没有必要构造二叉树，仅用一个数组就可以模拟二叉树的创建过程并得到符号的深度，具体方法这里就不详述了。

3）分别统计从最大编码长度maxlength到1的每个长度对应了多少个符号。