半静态模型

 

做压缩算法前，最好还是先弄明白现有的主要算法实例的实现方法，看别人的代码其实是最好的学习过程。有关概率模型的知识是数据压缩的核心内容，你可以参考《数据压缩技术原理与范例》、《数据压缩原理与应用》等书籍上的相关介绍。抄一段我以前给网友的回复：

 

从原理上讲，任何压缩算法都是由两个基本步骤组成的：

 

1、选择特定的概率模型，统计符号的出现概率

2、用特定的编码方法对符号进行编码

 

所以，Mark Nelson才说，压缩＝模型＋编码。我们讨论的变长编码问题，属于“编码”的范畴。至于如何在压缩过程中对该编码体系进行调整，就属于“模型”的范畴了。常用的概率模型包括以下几类：

 

* 静态模型：一旦固定下来，就不再改变的模型。每个符号对应固定的编码。

* 半静态模型：首先对全部待压缩数据进行统计，根据统计结果制定编码表。编码表在压缩过程中不变。

* 自适应模型：一边压缩，一边统计符号概率，一边调整编码表。编码表在压缩过程中不断变化。根据统计时上下文大小的不同，自适应模型又可以分为0阶、1阶、2阶、n阶自适应模型等等。

* 马尔可夫模型：自适应模型的一种，由马尔可夫状态机得来。

* PPM模型：部分匹配预测模型，阶次可变，适应能力最强的自适应模型之一。

* 字典模型：LZ77、LZW等算法采用的是字典模型，表面上看，没有统计概率的过程，但从根本上讲，这些算法输出编码时采用的仍然是一种考虑了字符概率因素的自适应模型（这一点可以从数学角度证明，但比较复杂）。

  ……

我们一般说的Huffman编码、算术编码等，都是编码方法，某种编码方法和某种概率模型相结合，就可以得到一种完整的压缩算法。例如，PPM+算术编码就是现在压缩效果最好的通用算法之一。