📄 chapter4.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="Chapter3.htm">第三章</a> <a href="Chapter5.htm">第五章</a></address></div><p>我们在上一章中已经明白，Huffman编码使用整数个二进制位对符号进行编码，这种方法在许多情况下无法得到最优的压缩效果。假设某个字符的出现概率为80%，该字符事实上只需要 -log<sub>2</sub>(0.8) = 0.322位编码，但 Huffman 编码一定会为其分配一位 0或一位 1 的编码。可以想象，整个信息的 80%在压缩后都几乎相当于理想长度的 3倍左右，压缩效果可想而知。</p><p>难道真的能只输出 0.322 个 0 或 0.322 个 1吗？是用剪刀把计算机存储器中的二进制位剪开吗？计算机真有这样的特异功能吗？慢着慢着，我们不要被表面现象所迷惑，其实，在这一问题上，我们只要换一换脑筋，从另一个角度……哎呀，还是想不通，怎么能是半个呢？好了，不用费心了，数学家们也不过是在十几年前才想到了算术编码这种神奇的方法，还是让我们虚心地研究一下他们究竟是从哪个角度找到突破口的吧。</p><p><strong>输出：一个小数</strong></p><p>更神奇的事情发生了，算术编码对整条信息（无论信息有多么长），其输出仅仅是一个数，而且是一个介于0 和 1之间的二进制小数。例如算术编码对某条信息的输出为1010001111，那么它表示小数 0.1010001111，也即十进制数0.64。</p><p>咦？怎么一会儿是表示半个二进制位，一会儿又是输出一个小数，算术编码怎么这么古怪呀？不要着急，我们借助下面一个简单的例子来阐释算术编码的基本原理。为了表示上的清晰，我们暂时使用十进制表示算法中出现的小数，这丝毫不会影响算法的可行性。</p><p>考虑某条信息中可能出现的字符仅有 a b c三种，我们要压缩保存的信息为 bccb。</p><p>在没有开始压缩进程之前，假设我们对 a b c三者在信息中的出现概率一无所知（我们采用的是自适应模型），没办法，我们暂时认为三者的出现概率相等，也就是都为1/3，我们将 0 - 1区间按照概率的比例分配给三个字符，即 a 从0.0000 到 0.3333，b 从 0.3333 到 0.6667，c 从 0.6667 到1.0000。用图形表示就是：</p><pre> +-- 1.0000 | Pc = 1/3 | | +-- 0.6667 | Pb = 1/3 | | +-- 0.3333 | Pa = 1/3 | | +-- 0.0000</pre><p>现在我们拿到第一个字符 b，让我们把目光投向b 对应的区间 0.3333 - 0.6667。这时由于多了字符 b，三个字符的概率分布变成：Pa= 1/4，Pb = 2/4，Pc = 1/4。好，让我们按照新的概率分布比例划分0.3333 - 0.6667 这一区间，划分的结果可以用图形表示为：</p><pre> +-- 0.6667 Pc = 1/4 | +-- 0.5834 | | Pb = 2/4 | | | +-- 0.4167 Pa = 1/4 | +-- 0.3333</pre><p>接着我们拿到字符 c，我们现在要关注上一步中得到的c 的区间 0.5834 - 0.6667。新添了 c以后，三个字符的概率分布变成 Pa = 1/5，Pb = 2/5，Pc= 2/5。我们用这个概率分布划分区间 0.5834 - 0.6667：</p><pre> +-- 0.6667 | Pc = 2/5 | | +-- 0.6334 | Pb = 2/5 | | +-- 0.6001 Pa = 1/5 | +-- 0.5834</pre><p>现在输入下一个字符 c，三个字符的概率分布为：Pa= 1/6，Pb = 2/6，Pc = 3/6。我们来划分 c 的区间 0.6334- 0.6667：</p><pre> +-- 0.6667 | | Pc = 3/6 | | | +-- 0.6501 | Pb = 2/6 | | +-- 0.6390 Pa = 1/6 | +-- 0.6334</pre><p>输入最后一个字符 b，因为是最后一个字符，不用再做进一步的划分了，上一步中得到的b 的区间为 0.6390 - 0.6501，好，让我们在这个区间内随便选择一个容易变成二进制的数，例如0.64，将它变成二进制 0.1010001111，去掉前面没有太多意义的0 和小数点，我们可以输出 1010001111，这就是信息被压缩后的结果，我们完成了一次最简单的算术压缩过程。</p><p>怎么样，不算很难吧？可如何解压缩呢？那就更简单了。解压缩之前我们仍然假定三个字符的概率相等，并得出上面的第一幅分布图。解压缩时我们面对的是二进制流1010001111，我们先在前面加上 0和小数点把它变成小数 0.1010001111，也就是十进制0.64。这时我们发现 0.64 在分布图中落入字符 b的区间内，我们立即输出字符 b，并得出三个字符新的概率分布。类似压缩时采用的方法，我们按照新的概率分布划分字符b 的区间。在新的划分中，我们发现 0.64落入了字符 c 的区间，我们可以输出字符 c。同理，我们可以继续输出所有的字符，完成全部解压缩过程（注意，为了叙述方便，我们暂时回避了如何判断解压缩结束的问题，实际应用中，这个问题并不难解决）。</p><p><font color="#FF8000">现在把教程抛开，仔细回想一下，直到你理解了算术压缩的基本原理，并产生了许多新的问题为止。</font></p><p><strong>真的能接近极限吗？</strong></p><p>现在你一定明白了一些东西，也一定有了不少新问题，没有关系，让我们一个一个解决。</p><p>首先，我们曾反复强调，算术压缩可以表示小数个二进制位，并由此可以接近无损压缩的熵极限，怎么从上面的描述中没有看出来呢？</p><p>算术编码实际上采用了化零为整的思想来表示小数个二进制位，我们确实无法精确表示单个小数位字符，但我们可以将许多字符集中起来表示，仅仅允许在最后一位有些许的误差。</p><p>结合上面的简单例子考虑，我们每输入一个符号，都对概率的分布表做一下调整，并将要输出的小数限定在某个越来越小的区间范围内。对输出区间的限定是问题的关键所在，例如，我们输入第一个字符b 时，输出区间被限定在 0.3333 - 0.6667 之间，我们无法决定输出值得第一位是3、4、5 还是 6，也就是说，b 的编码长度小于一个十进制位（注意我们用十进制讲解，和二进制不完全相同），那么我们暂时不决定输出信息的任何位，继续输入下面的字符。直到输入了第三个字符c 以后，我们的输出区间被限定在 0.6334 - 0.6667之间，我们终于知道输出小数的第一位（十进制）是6，但仍然无法知道第二位是多少，也即前三个字符的编码长度在1 和 2 之间。等到我们输入了所有字符之后，我们的输出区间为0.6390 - 0.6501，我们始终没有得到关于第二位的确切信息，现在我们明白，输出所有的4 个字符，我们只需要 1点几个十进制位，我们唯一的选择是输出 2个十进制位 0.64。这样，我们在误差不超过 1个十进制位的情况下相当精确地输出了所有信息，很好地接近了熵值（需要注明的是，为了更好地和下面的课程接轨，上面的例子采用的是0 阶自适应模型，其结果和真正的熵值还有一定的差距）。</p><p><strong>小数有多长？</strong></p>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -