数据压缩/马尔可夫模型
马尔可夫算法是数据压缩算法，其具有马尔可夫假设：明文是由可以被马尔可夫模型近似的东西生成的——即马尔可夫链、隐马尔可夫模型、变阶马尔可夫模型或类似的东西。
字典算法总是可以被马尔可夫算法模拟，但反过来则不行。 [1]
完全通用的马尔可夫模型被用于一些最复杂的算法，这些算法具有已知的最佳压缩率——可惜的是，它们也是使用中最慢的算法。
也许最简单的马尔可夫算法是 PPP 预测压缩协议，由 Timo Raita 实现并由 RFC 1978 标准化。 [2]
它查看（大约）最近解码的 3 或 4 个字节，找到该序列最后一次出现的时间，并猜测下一个字节将与上次相同的后续字节相同。
预测解压缩器的内部循环类似于这样
- 预测解码器读取一个标志字节，其中包含 8 个标志。每个标志位对应一个重建的解压缩数据字节。
- 对于 8 个标志位中的每一个
- 如果标志位为 0，则猜测错误。预测解码器从压缩数据中读取一个字面字节，并将其直接传递到解压缩文本中。同时将该字面字节存储在 GuessTable[context] 中，这样下次可能发生这种情况时，我们就会猜对了。
- 如果标志位为 1，则猜测正确。从 GuessTable[context] 读取猜测并将其写入解压缩文本中。
- 从我们刚刚写入解压缩文本的字节更新上下文。
- 重复直到没有更多压缩字节可读取。
在任何给定的上下文中，一个字节值是最有可能的下一个字节。预测器将该最有可能的下一个字节压缩为 1 位。当出现任何其他字节时，预测器将其扩展为 9 位。即使预测器有一半的时间猜错，它也可以获得相当好的压缩效果。
一阶马尔可夫解压缩算法比预测算法更复杂一些。
解压缩某个字节后，一阶马尔可夫解压缩器会查看该字节之前出现过的所有时间。 [3] 在任何给定的 1 字节上下文中，一个字节值是最有可能的下一个字节；某个其他字节值是下一个最有可能的下一个字节......等等；通常有几个字节在该上下文中只出现过一次——这些是最不可能的下一个字节值；通常有几个字节从未在该上下文中出现过——这些是最不可能的下一个字节值。
一阶马尔可夫解压缩器使用一些熵编码器为每个可能的下一个字节值分配一个唯一的代码前缀，使得更可能的字节被分配一个较短的代码字，不太可能的字节被分配一个较长的代码字（可能为 8 位），最不可能的字节被分配一个更长的代码字（超过 8 位）。
在某些情况下，下一个字节极有可能是一个特定字节（例如，在英文文本中，'q' 之后的字节几乎总是 'u'），一阶马尔可夫压缩这些情况与预测算法一样好。在其他情况下，马尔可夫压缩比预测算法好得多，因为它即使在字节不完全是最有可能的字节时也能压缩“可能”的字节。
更高阶的字母级和单词级马尔可夫链更擅长预测“可能”的英语短语。有些人通过允许他们构建马尔可夫链来创建“模仿生成器”，但他们不是将特定压缩代码字馈送到解码器以使马尔可夫解码器有足够的线索来重建某个特定明文，而是将随机生成的位馈送到马尔可夫解码器。 [4]
具有最佳压缩率的解压缩算法通常使用几种不同的模型，每个模型都对下一个位或字节进行预测，然后以某种方式将这些预测混合在一起，以获得最终预测并将其馈送到熵编码器。只要最终预测不为零或一（永不发生或总是发生），解压缩器就可以无错误地解码所有文件（有关详细信息，请参阅 零频率问题）。
可惜的是，到目前为止，我们还没有找到将这些预测组合在一起的“最佳”方法。人们已经开发了几种临时方法来混合预测。一些混合技术似乎“更好”，因为它们产生的压缩文件比其他混合技术更小（并且比单独使用任何一个底层预测更好）。
在我们进入实际的“上下文混合”算法之前，让我们看一下 PPM 和 DMC，它们直接使用一个或另一个上下文的预测（而不是混合预测）
部分匹配预测 [5] 也许是最容易理解的混合技术。PPM 保持着不同阶数的马尔可夫模型。PPM(5) 解码器尽可能使用 5 阶马尔可夫模型。如果无法基于所有 5 个上下文符号进行预测——即最近解码的 5 个字节以前从未以该顺序出现过——则它会回退到 4 阶马尔可夫模型。如果 4 阶模型无法进行预测——即最近解码的 4 个字节以前从未以该顺序出现过——则它会回退到 3 阶马尔可夫模型。PPM 解码器最终会找到可以用来压缩文本的马尔可夫模型，即使它不得不一直回退到默认的零阶马尔可夫模型。
动态马尔可夫压缩是由 Gordon Cormack 和 Nigel Horspool 开发的。 [6] Gordon Cormack 在 1993 年发布了他用 C 语言编写的 DMC 实现，并使用非商业许可证。 [7] 动态马尔可夫压缩是一种无损数据压缩算法，与 PPM 非常相似，但它一次预测一位，而不是一次预测一个字节。这使其速度变慢，但可以实现略微更好的压缩。它被用作几种高度实验性实现中的模型或子模型。
预测被馈送到算术编码器中。（因为预测是逐位进行的，所以简单的霍夫曼编码而不是算术编码将不会产生任何压缩）。
一些模型混合/上下文混合方法包括
上下文树加权 [8] 是另一种混合技术。
- ↑ Ross Williams. "LZRW4: ZIV AND LEMPEL MEET MARKOV". 1991.
- ↑ RFC 1978
- ↑ 与其逐字节扫描整个明文，大多数程序员使用一种速度快得多的方法，得到相同的结果：程序在解压缩每个字节时更新内部哈希表或二维数组，然后从该数据结构中直接获取下一个字节所需的数据。
- ↑ Jon Bentley. "Generating Text" (Programming Pearls 的第 15.3 节) 2000.
- ↑ 维基百科：部分匹配预测
- ↑ 维基百科：动态马尔可夫压缩
- ↑ Gordon V. Cormack. "Dynamic Markov Compression. (DMC) Version 0.0.0". 1993. dmc.c
- ↑ 维基百科：上下文树加权