📄 htm1.htm
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0058)http://www.contextfree.net/wangyg/tech/benben/Chapter4.htm -->
<HTML><HEAD><TITLE>笨笨数据压缩教程</TITLE>
<META http-equiv=Content-Type content="text/html; charset=gb_2312-80">
<META content="MSHTML 6.00.2600.0" name=GENERATOR></HEAD>
<BODY bgColor=#ffffff>
<P align=right><A
href="http://www.contextfree.net/index.html">返回断章取义堂</A> <A
href="http://www.contextfree.net/wangyg/index.html">返回咏刚的家</A></P>
<P><IMG height=129 alt="笨笨数据压缩教程(Benben's Data Compression Guide)"
src="Chapter4_files/benben.jpg" width=370></P>
<H2>第四章 向极限挑战：算术编码</H2>
<DIV align=right>
<ADDRESS><A
href="http://www.contextfree.net/wangyg/tech/benben/Chapter3.htm">第三章</A> <A
href="http://www.contextfree.net/wangyg/tech/benben/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 + -