📄 chapter2.htm
字号:
<html><head><meta http-equiv="Content-Type"content="text/html; charset=gb_2312-80"><meta name="GENERATOR" content="Microsoft FrontPage Express 2.0"><title>笨笨数据压缩教程</title></head><body bgcolor="#FFFFFF"><p align="right"><a href="../../../index.html">返回断章取义堂</a> <a href="../../index.html">返回咏刚的家</a></p><p style="background-color:#AAEEFF;font-size:14px;color:#0000AA">《笨笨数据压缩教程》是我在1998年因工作需要研究压缩算法时写的文章（算是一种工作笔记吧，其中难免有许多疏漏），1999年初随着项目变迁，就把压缩技术的研究暂时搁置了。从那以后，一是工作太忙，二是自己懒惰，总之是没能把半部压缩教程补全。非常对不住大家。——王咏刚，2003年3月</p><p><img src="benben.jpg"alt="笨笨数据压缩教程(Benben's Data Compression Guide)"width="370" height="129"></p><h2>第二章 技术准备：概率、模型和编码</h2><div align="right"><address> <a href="Chapter1.htm">第一章</a> <a href="Chapter3.htm">第三章</a></address></div><p align="left"><strong>什么是熵</strong></p><p align="left">数据压缩不仅起源于 40 年代由 ClaudeShannon 首创的信息论，而且其基本原理即信息究竟能被压缩到多小，至今依然遵循信息论中的一条定理，这条定理借用了热力学中的名词“熵”(Entropy )来表示一条信息中真正需要编码的信息量：</p><p align="left">考虑用 0 和 1组成的二进制数码为含有 n 个符号的某条信息编码，假设符号Fn <font size="3">在整条信息中重复出现的概率为 Pn，则该符号的熵也即表示该符号所需的位数位为：</font></p><div align="left"><pre><font size="3">En = - log<sub>2</sub>( Pn )</font></pre></div><p align="left"><font size="3">整条信息的熵也即表示整条信息所需的位数为：E= ∑En</font></p><p align="left"><font size="3">举个例子，对下面这条只出现了a b c 三个字符的字符串：</font></p><p align="left"><font size="3">aabbaccbaa</font></p><p align="left"><font size="3">字符串长度为 10，字符 a bc 分别出现了 5 3 2 次，则 a b c 在信息中出现的概率分别为0.5 0.3 0.2，他们的熵分别为：</font></p><div align="left"><pre><font size="3">Ea = -log<sub>2</sub>(0.5) = 1</font></pre></div><div align="left"><pre><font size="3">Eb = -log<sub>2</sub>(0.3) = 1.737</font></pre></div><div align="left"><pre><font size="3">Ec = -log<sub>2</sub>(0.2) = 2.322</font></pre></div><p align="left"><font size="3">整条信息的熵也即表达整个字符串需要的位数为：</font></p><div align="left"><pre><font size="3">E = Ea * 5 + Eb * 3 + Ec * 2 = 14.855 位</font></pre></div><p align="left"><font size="3">回想一下如果用计算机中常用的ASCII 编码，表示上面的字符串我们需要整整 80 位呢！现在知道信息为什么能被压缩而不丢失原有的信息内容了吧。简单地讲，用较少的位数表示较频繁出现的符号，这就是数据压缩的基本准则。</font></p><p align="left"><font size="3">细心的读者马上会想到，我们该怎样用0 1 这样的二进制数码表示零点几个二进制位呢？确实很困难，但<strong>不是没有办法</strong>。一旦我们找到了准确表示零点几个二进制位的方法，我们就有权利向无损压缩的极限挑战了。不要着急，看到第四章就明白了。</font></p><p align="left"><font size="3"><strong>模型</strong></font></p><p align="left"><font size="3">从上面的描述，我们明白，要压缩一条信息，首先要分析清楚信息中每个符号出现的概率。不同的压缩程序通过不同的方法确定符号的出现概率，对符号的概率计算得越准确，也就越容易得到好的压缩效果。在压缩程序中，用来处理输入信息，计算符号的概率并决定输出哪个或哪些代码的模块叫做模型。</font></p><p align="left"><font size="3">难道对信息中字符的出现概率这么难以估计以至于有各种不同的压缩模型吗？对上面的字符串我们不是很容易就知道每个字符的概率了吗？是的是的，不过上面的字符串仅有10 个字符长呀，那只是例子而已。考虑我们现实中要压缩的文件，大多数可是有几十K 甚至几百 K 长，几 M字节的文件不是也屡见不鲜吗？</font></p><p align="left"><font size="3">是的，我们可以预先扫描文件中的所有字符，统计出每个字符出现的概率，这种方法在压缩术语里叫做“静态统计模型”。但是，不同的文件中，字符有不同的分布概率，我们要么先花上大量的时间统计我们要压缩的所有文件中的字符概率，要么为每一个单独的文件保存一份概率表以备解压缩时需要。糟糕的是，不但扫描文件要消耗大量时间，而且保存一份概率表也使压缩后的文件增大了不少。所以，在实际应用中，“静态统计模型”应用的很少。</font></p><p align="left"><font size="3">真正的压缩程序中使用的大多是一种叫“自适应模型”的东西。自适应模型可以说是一台具有学习功能的自动机。他在信息被输入之前对信息内容一无所知并假定每个字符的出现概率均等，随着字符不断被输入和编码，他统计并纪录已经出现过的字符的概率并将这些概率应用于对后续字符的编码。也就是说，自适应模型在压缩开始时压缩效果并不理想，但随着压缩的进行，他会越来越接近字符概率的准确值，并达到理想的压缩效果。自适应模型还可以适应输入信息中字符分布的突然变化，可以适应不同的文件中的字符分布而不需要保存概率表。</font></p><p align="left"><font size="3">上面提到的模型可以统称为“统计模型”，因为他们都是基于对每个字符出现次数的统计得到字符概率的。另一大类模型叫做“字典模型”。实际上，当我们在生活中提到“工行”这个词的时候，我们都知道其意思是指“中国工商银行”，类似的例子还有不少，但共同的前提是我们心中都有一本约定俗成的缩写字典。字典模型也是如此，他并不直接计算字符出现的概率，而是使用一本字典，随着输入信息的读入，模型找出输入信息在字典中匹配的最长的字符串，然后输出该字符串在字典中的索引信息。匹配越长，压缩效果越好。事实上，字典模型本质上仍然是基于对字符概率的计算的，只不过，字典模型使用整个字符串的匹配代替了对某一字符重复次数的统计。可以证明，字典模型得到的压缩效果仍然无法突破熵的极限。</font></p><p align="left"><font size="3">当然，对通用的压缩程序来说，保存一本大字典所需的空间仍然是无法让人忍受的，况且，任何一本预先定义的字典都无法适应不同文件中数据的变化情况。对了，字典模型也有相应的“自适应”方案。我们可以随着信息的不断输入，从已经输入的信息中建立合适的字典，并不断更新这本字典，以适应数据的不断变化。</font></p><p align="left"><font size="3">让我们从另一个角度理解一下自适应模型。CluadeShannon 曾试图通过一个“聚会游戏”(party game)来测定英语的真实信息容量。他每次向听众公布一条被他隐藏起一个字符的消息，让听众来猜下一个字符是什么，一次猜一个，直到猜对为止。然后，Shannon使用猜测次数来确定整个信息的熵。在这个实验中，一种根据前面出现过的字符估计下一个字符概率的模型就存在于听众的头脑中，比计算机中使用的自适应模型更为高级的是，听众除了根据字符出现过的次数外，还可以根据他们对语言的经验进行猜测。</font></p><p align="left"><font size="3"><strong>编码</strong></font></p><p align="left"><font size="3">通过模型，我们已经确定了对某一个符号该用多少位二进制数进行编码。现在的问题是，如何设计一种编码方案，使其尽量精确地用模型计算出来的位数表示某个符号。</font></p><p align="left"><font size="3">最先被考虑的问题是，如果对a 用 3 个二进制位就可以表示，而对 b 用 4 个二进制位就可以表示，那么，在解码时，面对一连串的二进制流，我怎么知道哪三个位是a，哪四个位是 b 呢？所以，必须设计出一种编码方式，使得解码程序可以方便地分离每个字符的编码部分。于是有了一种叫“前缀编码”的技术。该技术的主导思想是，任何一个字符的编码，都不是另一个字符编码的前缀。反过来说就是，任何一个字符的编码，都不是由另一个字符的编码加上若干位0 或 1 组成。看一下前缀编码的一个最简单的例子：</font></p><div align="left"><pre><font size="3"> 符号 编码 A 0 B 10 C 110 D 1110 E 11110</font></pre></div><p align="left">有了上面的码表，你一定可以轻松地从下面这串二进制流中分辨出真正的信息内容了：</p><div align="left"><pre>1110010101110110111100010 - DABBDCEAAB</pre></div><p align="left">下一个问题是：象上面这样的前缀编码只能表示整数位的符号，对几点几位的符号只能用近似的整数位输出，那么怎样输出小数位数呢？科学家们用算术编码解决了这个问题，我们将在第四章对算术编码作详细的讨论。</p><p align="left"><strong>总结一下</strong></p><p align="left">不同的模型使用不同的方法计算字符的出现概率，由此概率可以得出字符的熵；然后使用不同的编码方法，尽量接近我们期望得到的熵值。所以，压缩效果的好坏一方面取决于模型能否准确地得到字符概率，另一方面也取决于编码方法能否准确地用期望的位数输出字符代码。换句话说，压缩= 模型 + 编码。如下图所示：</p><div align="left"><pre><font size="3">--------- 符号 ---------- 概率 ---------- 代码 ----------| 输入 |-------->| 模型 |-------->| 编码 |-------->| 输出 |--------- ---------- ---------- ---------- </font></pre></div><p align="left"><font size="3"><strong>资源</strong></font></p><p align="left"><font size="3">我们已经知道，编写压缩程序往往不能对数据的整个字节进行处理，而是要按照二进制位来读写和处理数据，操作二进制位的函数也就成为了压缩程序中使用最为普遍的工具函数。我们在此提供两组函数集，使用它们可以有效的进行文件或内存中的二进制位操作。它们共有六个文件：</font></p><p align="left"><font size="3">bitio.h -用于文件中二进制位操作的函数说明。</font></p><p align="left"><font size="3">bitio.cpp -用于文件中二进制位操作的函数实现。</font></p><p align="left"><font size="3">errhand.h 和 errhand.cpp -bitio.cpp 中使用的错误处理函数。</font></p><p align="left"><font size="3">wm_bitio.h -用于内存中二进制位操作的函数说明。</font></p><p align="left"><font size="3">wm_bitio.cpp -用于内存中二进制位操作的函数实现。</font></p><p align="left"><font size="3">它们被共同包装在文件 </font><ahref="src/bitio.zip"><font size="3">bitio.zip</font></a><fontsize="3"> 中。</font></p><p align="left"><font size="3"></font> </p><div align="center"><center><address> <a href="Chapter1.htm">第一章</a> <a href="Chapter3.htm">第三章</a></address></center></div><p align="left"> </p><div align="right"><address> <a href="mailto:wangyg@contextfree.net">有问题吗？有建议吗？快给王笨笨写信</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>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -