PPM Prediction with partial string matching PPM PPM是一种复杂而巧妙的压缩方法，最初由J.Cleary 和 I.Witten 开发，随后由 A.Moffat 加以扩展和实现。其编码器保持着一个统计模型：每输入下一个符号S，就给它分配一个概率P，然后把S送给自适应算术编码器，按概率P编码。 简单统计模型 最简单的统计模型，就是根据符号已出现的次数给它赋予一个概率。假设已经输入和编码了1217个符号，其中字母q出现了34次。如果下一个符号是q，那么其概率就是34/1217，然后q的计数值加1。下一次q再出现时的概率就是35/t，其中t是已输入符号的总数。 基于上下文的统计模型 另一个是基于上下文的统计模型。其想法是给某符号分配概率时不仅根据它的出现频率，而且根据它已经出现过的上下文。例如在典型的英文文本中u出现的概率约为2%，然而一旦出现了一个q，则下一个字母是u的概率就超过了99%。 基于上下文的静态模型 基于上下文的静态模型始终使用相同的概率，它包含一个静态表，表中有字母表的所有可能的双字母(或3，或更多字母组合)的概率，并利用该表生成当上下文是C时符号S的概率P(S|C)，可以将这个表看作是行列分别为S，C的一个静态频率表。 问题是： N阶自适应的模型 一个自适应的基于上下文的模型也维持着一个概率表，表中存放着字母表中所有可能的N+1字母组合的概率。随着更多符号的输入，该表不断更新，使得概率能与压缩中的特定数据相适应。 这种模型比静态模型更慢更复杂。 N阶模型 理论上N越大，概率估计越准确。然而N大有以下缺点： 一个3阶模型的问题 假设使用3阶上下文，单词here出现过几次，单词there未出现过，假定现在出现的是there中的r，而3阶上下文the后r的概率为0，3阶上下文模型的做法自然是可以直接把r不经压缩地写入压缩流。 然而，如果利用前面的2阶上下文he后面r已经出现多次，可以获得更好的效果。 PPM原理 PPM的中心思想是利用有效的短上下文知识：如果一个长上下文出现了0概率，就切换到一个较短的上下文。 PPM先从N阶上下文开始，搜索已出现过的上下文C(N个符号)后跟符号S，如果没有，就切换到N-1阶再试，…。 一个例子 假设：当前的3阶上下文串the，已经出现了27次，后跟r(11)，s(9)，n(6)，m(1次)。编码器给它们分配的概率分别为：11/27， 9/27， 6/27， 1/27。 另一个例子：xyzzxyxyzzx 后z ，4阶模型。 PPM解码器 编码器根据下一个符号是什么决定是否转向较短的上下文，但解码器不知道。 PPM的做法是引入转义符号，当编码器决定转向较短上下文时，先输出转义符号(算术编码)，这样，解码器解码出转义符号时，也知道了使用较短的上下文。 所以最坏的情形：{dy}次遇见S，编码器需连续发出N+1个转义符号，一直切换到-1阶上下文。 assanissimassa 二阶以下的上下文和计数 assanissimassa 当前上下文为sa，有以下4种典型情况： 排除 当从2阶上下文切换到一阶时，可以利用2阶上下文中的信息来排除一阶关系中的一些不可能的情形，从而增加1阶上下文的概率，因而改善了压缩。
|
