htm1.htm

LZ77算法与模式匹配KMP算法的结合及算法实现

<P>你一定已经想到，如果信息内容特别丰富，我们要输出的小数将会很长很长，我们该如何在内存中表示如此长的小数呢？</P>
<P>其实，没有任何必要在内存中存储要输出的整个小数。我们从上面的例子可以知道，在编码的进行中，我们会不断地得到有关要输出小数的各种信息。具体地讲，当我们将区间限定在 
0.6390 - 0.6501 之间时，我们已经知道要输出的小数第一位（十进制）一定是 6，那么我们完全可以将 6 从内存中拿掉，接着在区间 0.390 - 
0.501 之间继续我们的压缩进程。内存中始终不会有非常长的小数存在。使用二进制时也是一样的，我们会随着压缩的进行不断决定下一个要输出的二进制位是 0 还是 
1，然后输出该位并减小内存中小数的长度。</P>
<P><STRONG>静态模型如何实现？</STRONG></P>
<P>我们知道上面的简单例子采用的是自适应模型，那么如何实现静态模型呢？其实很简单。对信息 bccb 我们统计出其中只有两个字符，概率分布为 Pb = 
0.5，Pc = 
0.5。我们在压缩过程中不必再更新此概率分布，每次对区间的划分都依照此分布即可，对上例也就是每次都平分区间。这样，我们的压缩过程可以简单表示为：</P><PRE>               输出区间的下限      输出区间的上限
--------------------------------------------------
 压缩前           0.0                1.0
 输入 b           0.0                0.5
 输入 c           0.25               0.5
 输入 c           0.375              0.5
 输入 b           0.375              0.4375</PRE>
<P>我们看出，最后的输出区间在 0.375 - 0.4375 
之间，甚至连一个十进制位都没有确定，也就是说，整个信息根本用不了一个十进制位。如果我们改用二进制来表示上述过程的话，我们会发现我们可以非常接近该信息的熵值（有的读者可能已经算出来了，该信息的熵值为 
4 个二进制位）。</P>
<P><STRONG>为什么用自适应模型？</STRONG></P>
<P>既然我们使用静态模型可以很好地接近熵值，为什么还要采用自适应模型呢？</P>
<P>要知道，静态模型无法适应信息的多样性，例如，我们上面得出的概率分布没法在所有待压缩信息上使用，为了能正确解压缩，我们必须再消耗一定的空间保存静态模型统计出的概率分布，保存模型所用的空间将使我们重新远离熵值。其次，静态模型需要在压缩前对信息内字符的分布进行统计，这一统计过程将消耗大量的时间，使得本来就比较慢的算术编码压缩更加缓慢。</P>
<P>另外还有最重要的一点，对较长的信息，静态模型统计出的符号概率是该符号在整个信息中的出现概率，而自适应模型可以统计出某个符号在某一局部的出现概率或某个符号相对于某一上下文的出现概率，换句话说，自适应模型得到的概率分布将有利于对信息的压缩（可以说结合上下文的自适应模型的信息熵建立在更高的概率层次上，其总熵值更小），好的基于上下文的自适应模型得到的压缩结果将远远超过静态模型。</P>
<P><STRONG>自适应模型的阶</STRONG></P>
<P>我们通常用“阶”(order)这一术语区分不同的自适应模型。本章开头的例子中采用的是 0 
阶自适应模型，也就是说，该例子中统计的是符号在已输入信息中的出现概率，没有考虑任何上下文信息。</P>
<P>如果我们将模型变成统计符号在某个特定符号后的出现概率，那么，模型就成为了 1 阶上下文自适应模型。举例来说，我们要对一篇英文文本进行编码，我们已经编码了 
10000 个英文字符，刚刚编码的字符是 t，下一个要编码的字符是 h。我们在前面的编码过程中已经统计出前 10000 个字符中出现了 113 次字母 
t，其中有 47 个 t 后面跟着字母 h。我们得出字符 h 在字符 t 后的出现频率是 47/113，我们使用这一频率对字符 h 进行编码，需要 
-log<SUB>2</SUB>(47/113) = 1.266 位。</P>
<P>对比 0 阶自适应模型，如果前 10000 个字符中 h 的出现次数为 82 次，则字符 h 的概率是 82/10000，我们用此概率对 h 
进行编码，需要 -log<SUB>2</SUB>(82/10000) = 6.930 位。考虑上下文因素的优势显而易见。</P>
<P>我们还可以进一步扩大这一优势，例如要编码字符 h 的前两个字符是 gt，而在已经编码的文本中 gt 后面出现 h 的概率是 80%，那么我们只需要 
0.322 位就可以编码输出字符 h。此时，我们使用的模型叫做 2 阶上下文自适应模型。</P>
<P>最理想的情况是采用 3 
阶自适应模型。此时，如果结合算术编码，对信息的压缩效果将达到惊人的程度。采用更高阶的模型需要消耗的系统空间和时间至少在目前还无法让人接受，使用算术压缩的应用程序大多数采用 
2 阶或 3 阶的自适应模型。</P>
<P><STRONG>转义码的作用</STRONG></P>
<P>使用自适应模型的算术编码算法必须考虑如何为从未出现过的上下文编码。例如，在 1 阶上下文模型中，需要统计出现概率的上下文可能有 256 * 256 = 
65536 种，因为 0 - 255 的所有字符都有可能出现在 0 - 255 个字符中任何一个之后。当我们面对一个从未出现过的上下文时（比如刚编码过字符 
b，要编码字符 d，而在此之前，d 从未出现在 b 的后面），该怎样确定字符的概率呢？</P>
<P>比较简单的办法是在压缩开始之前，为所有可能的上下文分配计数为 1 的出现次数，如果在压缩中碰到从未出现的 bd 组合，我们认为 d 出现在 b 
之后的次数为 1，并可由此得到概率进行正确的编码。使用这种方法的问题是，在压缩开始之前，在某上下文中的字符已经具有了一个比较小的频率。例如对 1 
阶上下文模型，压缩前，任意字符的频率都被人为地设定为 1/65536，按照这个频率，压缩开始时每个字符要用 16 
位编码，只有随着压缩的进行，出现较频繁的字符在频率分布图上占据了较大的空间后，压缩效果才会逐渐好起来。对于 2 阶或 3 
阶上下文模型，情况就更糟糕，我们要为几乎从不出现的大多数上下文浪费大量的空间。</P>
<P>我们通过引入“转义码”来解决这一问题。“转义码”是混在压缩数据流中的特殊的记号，用于通知解压缩程序下一个上下文在此之前从未出现过，需要使用低阶的上下文进行编码。</P>
<P>举例来讲，在 3 阶上下文模型中，我们刚编码过 ght，下一个要编码的字符是 a，而在此之前，ght 后面从未出现过字符 
a，这时，压缩程序输出转义码，然后检查 2 阶的上下文表，看在此之前 ht 后面出现 a 的次数；如果 ht 后面曾经出现过 a，那么就使用 2 
阶上下文表中的概率为 a 编码，否则再输出转义码，检查 1 阶上下文表；如果仍未能查到，则输出转义码，转入最低的 0 阶上下文表，看以前是否出现过字符 
a；如果以前根本没有出现过 a，那么我们转到一个特殊的“转义”上下文表，该表内包含 0 - 255 所有符号，每个符号的计数都为 
1，并且永远不会被更新，任何在高阶上下文中没有出现的符号都可以退到这里按照 1/256 的频率进行编码。</P>
<P>“转义码”的引入使我们摆脱了从未出现过的上下文的困扰，可以使模型根据输入数据的变化快速调整到最佳位置，并迅速减少对高概率符号编码所需要的位数。</P>
<P><STRONG>存储空间问题</STRONG></P>
<P>在算术编码高阶上下文模型的实现中，对内存的需求量是一个十分棘手的问题。因为我们必须保持对已出现的上下文的计数，而高阶上下文模型中可能出现的上下文种类又是如此之多，数据结构的设计将直接影响到算法实现的成功与否。</P>
<P>在 1 阶上下文模型中，使用数组来进行出现次数的统计是可行的，但对于 2 阶或 3 
阶上下文模型，数组大小将依照指数规律增长，现有计算机的内存满足不了我们的要求。</P>
<P>比较聪明的办法是采用树结构存储所有出现过的上下文。利用高阶上下文总是建立在低阶上下文的基础上这一规律，我们将 0 
阶上下文表存储在数组中，每个数组元素包含了指向相应的 1 阶上下文表的指针，1 阶上下文表中又包含了指向 2 
阶上下文表的指针……由此构成整个上下文树。树中只有出现过的上下文才拥有已分配的节点，没有出现过的上下文不必占用内存空间。在每个上下文表中，也无需保存所有 256 
个字符的计数，只有在该上下文后面出现过的字符才拥有计数值。由此，我们可以最大限度地减少空间消耗。</P>
<P><STRONG>资源</STRONG></P>
<P>关于算术压缩具体的设计和实现请参考下面给出的示例程序。</P>
<P>程序 Arith-N 由 League for Programming Freedom 的 Mark Nelson 提供，由王笨笨在 Visual C++ 
5.0 环境下编译、调试通过。</P>
<P>Arith-N 包含 Visual C++ 工程 ArithN.dsp 和 ArithNExpand.dsp，分别对应了压缩和解压缩程序 an.exe 与 
ane.exe。</P>
<P>Arith-N 是可以在命令行指定阶数的 N 
阶上下文自适应算术编码通用压缩、解压缩程序，由于是用作教程示例，为清晰起见，在某些地方并没有刻意进行效率上的优化。</P>
<P>所有源程序包装在文件 <A 
href="http://www.contextfree.net/wangyg/tech/benben/src/arith-n.zip">Arith-N.zip</A> 
中。</P>
<P>　</P>
<DIV align=center>
<CENTER>
<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></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="http://www.contextfree.net/wangyg/tech/benben/default.htm">前言</A> <A 
href="http://www.contextfree.net/wangyg/tech/benben/content.htm">目录</A> <A 
href="http://www.contextfree.net/wangyg/tech/benben/Chapter1.htm">1</A> <A 
href="http://www.contextfree.net/wangyg/tech/benben/Chapter2.htm">2</A> <A 
href="http://www.contextfree.net/wangyg/tech/benben/Chapter3.htm">3</A> <A 
href="http://www.contextfree.net/wangyg/tech/benben/Chapter4.htm">4</A> <A 
href="http://www.contextfree.net/wangyg/tech/benben/Chapter5.htm">5</A> <A 
href="http://www.contextfree.net/wangyg/tech/benben/Chapter6.htm">6</A> <A 
href="http://www.contextfree.net/wangyg/tech/benben/Chapter7.htm">7</A> <A 
href="http://www.contextfree.net/wangyg/tech/benben/Chapter8.htm">8</A> <A 
href="http://www.contextfree.net/wangyg/tech/benben/Chapter9.htm">9</A> <A 
href="http://www.contextfree.net/wangyg/tech/benben/Chapter10.htm">10</A> <A 
href="http://www.contextfree.net/wangyg/tech/benben/Chapter11.htm">11</A> <A 
href="http://www.contextfree.net/wangyg/tech/benben/Chapter12.htm">12</A> 
</ADDRESS>
<P align=right><A 
href="http://www.contextfree.net/index.html">返回断章取义堂</A>&nbsp;&nbsp;<A 
href="http://www.contextfree.net/wangyg/index.html">返回咏刚的家</A></P></DIV></BODY></HTML>