动态马尔可夫压缩

动态马尔可夫压缩的预测以及编码以比特为单位，并使用算术编码作为编码方式。

算术编码

动态马尔可夫压缩使用的比特编码器具有两部分：预测器和比特编码器。预测器接受n比特输入字符串x = x₁x₂...x_n，其发生概率可写作 p(x) = p(x₁)p(x₂|x₁)p(x₃|x₁x₂)... p(x_n|x₁x₂...x_n–1)。算术编码器中有两二进制高精准度参数p_high和p_low，分别代表该模型发生的概率之区间上限与下限。x之编码记作p_x，为在p_high和p_low之间长度最短的数。我们永远可以找到不比夏农极限，log₂ 1/p(x')，长超过一个比特的p_x。要找到这样的p_x，只需要把p_high在第一个和p_high相异比特之后的比特全数舍弃即可。

接下来的压缩步骤如下。初始p_high设为1，p_low设为0。对于每个比特，预测器预测p₀ = p(x_i = 0|x₁x₂...x_i–1)和p₁ = 1 − p₀，这里p₀代表该比特为0的概率，p₁代表该比特为1的概率。接着，算术编码器将当前的概率范围，也就是(p_low, p_high)，依p₀和p₁之比例分割成二新区间。下一个比特x_i的子概率区间就成为新的概率区间，如此周而复始。

在解压缩的时候，预测器会对于已解出的比特做出一样的预测串。算术编码器接着做出一样的区间分割，然后输出对应到每个p_x的比特x_i。

在实现上，p_high和p_low并非一定要维持在很高的精准度。

动态马尔可夫压缩之模型

动态马尔可夫压缩之预测器是一个将比特对应到一对正整数n₀和n₁之表。n₀和n₁分别代表0和1的累计个数。因此，预测下一个比特为0的概率可以写作p₀ = n₀/n = n₀/(n₀ + n₁)，而下一个比特为1的概率可以写作p₁ = 1 − p₀ = n₁/n。

在原始的动态马尔可夫压缩中，初始的表为长度为八到十五个比特的二进制数所成集合，而初始态设为任一长度为八的二进制数。计数被初始化为一接近零的小数而非零，这是为了维持解码出未曾出现过比特的可能。

压缩和解压缩的模型是雷同的。对于每一个比特，p₀和p₁先被计算，接着对x_i编码或解码。

增加新的资料

上述之动态马尔可夫模型等价于一次环境模型。然而，使用时可能加入更长的待压内容以增进压缩。举例来说，如果当前资料为A，增加资料为B，则B有可能需要舍弃左边的某些比特，接着编码器必须增加一个B的复制C。C的代表资料可视为A在右侧增加一个新比特但未舍弃左边数个比特。A的链接会从B改成C。B和C会进行同样的预测，也会指向一样的一对状态。C之总比特计数n = n₀ + n₁等于A对输入比特x之计数n_x，而B之计数会减掉该数。

举个例子，假设状态A代表的资料是11111，当输入比特为0，状态转变为B，其代表资料为110，等于是舍弃了最左边的三个比特并在右边加入一个新的比特。状态A所计零比特之数目为4。状态B计有3个零比特和7个一比特，故其p₁ = 0.7。

状态C为B的复制。C代表的资料为111110。B和C都预测一比特出现的概率为0.7，并且都转为一样的状态，E和F。

1. Gordon Cormack and Nigel Horspool, "Data Compression using Dynamic Markov Modelling", Computer Journal 30:6（December 1987）

• Data Compression Using Dynamic Markov Modelling （页面存档备份，存于互联网档案馆）