动态马尔可夫压缩
 |
动态马尔可夫压缩是一种无损压缩算法，由Gordan Cormack和Nigel Horspool发明。该算法类似预测性算术编码，不同的是输入资料预测是以位元为单位，而非字节。动态马尔可夫压缩具有良好的压缩比以及中等的运算速率，但是需求较高的存储器。
算法[编辑]
动态马尔可夫压缩的预测以及编码以位元为单位，并使用算术编码作为编码方式。
算术编码[编辑]
动态马尔可夫压缩使用的位元编码器具有两部分：预测器和位元编码器。预测器接受n位元输入字符串x = x1x2...xn，其发生概率可写作 p(x) = p(x1)p(x2|x1)p(x3|x1x2)... p(xn|x1x2...xn–1)。算术编码器中有两二进制高精准度参数phigh和plow，分别代表该模型发生的概率之区间上限与下限。x之编码记作px，为在phigh和plow之间长度最短的数。我们永远可以找到不比夏农极限，log2 1/p(x')，长超过一个位元的px。要找到这样的px，只需要把phigh在第一个和phigh相异位元之后的位元全数舍弃即可。
接下来的压缩步骤如下。初始phigh设为1，plow设为0。对于每个位元，预测器预测p0 = p(xi = 0|x1x2...xi–1)和p1 = 1 − p0，这里p0代表该位元为0的概率，p1代表该位元为1的概率。接着，算术编码器将当前的概率范围，也就是(plow, phigh)，依p0和p1之比例分割成二新区间。下一个位元xi的子概率区间就成为新的概率区间，如此周而复始。
在解压缩的时候，预测器会对于已解出的位元做出一样的预测串。算术编码器接着做出一样的区间分割，然后输出对应到每个px的位元xi。
在实现上，phigh和plow并非一定要维持在很高的精准度。
动态马尔可夫压缩之模型[编辑]
动态马尔可夫压缩之预测器是一个将位元对应到一对正整数n0和n1之表。n0和n1分别代表0和1的累计个数。因此，预测下一个位元为0的概率可以写作p0 = n0/n = n0/(n0 + n1)，而下一个位元为1的概率可以写作p1 = 1 − p0 = n1/n。
在原始的动态马尔可夫压缩中，初始的表为长度为八到十五个位元的二进制数所成集合，而初始态设为任一长度为八的二进制数。计数被初始化为一接近零的小数而非零，这是为了维持解码出未曾出现过位元的可能。
压缩和解压缩的模型是雷同的。对于每一个位元，p0和p1先被计算，接着对xi编码或解码。
增加新的资料[编辑]
上述之动态马尔可夫模型等价于一次环境模型。然而，使用时可能加入更长的待压内容以增进压缩。举例来说，如果当前资料为A，增加资料为B，则B有可能需要舍弃左边的某些位元，接着编码器必须增加一个B的复制C。C的代表资料可视为A在右侧增加一个新位元但未舍弃左边数个位元。A的链接会从B改成C。B和C会进行同样的预测，也会指向一样的一对状态。C之总位元计数n = n0 + n1等于A对输入位元x之计数nx，而B之计数会减掉该数。
举个例子，假设状态A代表的资料是11111，当输入位元为0，状态转变为B，其代表资料为110，等于是舍弃了最左边的三个位元并在右边加入一个新的位元。状态A所计零位元之数目为4。状态B计有3个零位元和7个一位元，故其p1 = 0.7。
| 状态 | n0 | n1 | next0 | next1 |
|---|---|---|---|---|
| A = 11111 | 4 | B | ||
| B = 110 | 3 | 7 | E | F |
状态C为B的复制。C代表的资料为111110。B和C都预测一位元出现的概率为0.7，并且都转为一样的状态，E和F。
| 状态 | n0 | n1 | next0 | next1 |
|---|---|---|---|---|
| A = 11111 | 4 | C | ||
| B = 110 | 1.8 | 4.2 | E | F |
| C = 111110 | 1.2 | 2.8 | E | F |
参考项目[编辑]
1. Gordon Cormack and Nigel Horspool, "Data Compression using Dynamic Markov Modelling", Computer Journal 30:6（December 1987）
外部链接[编辑]
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||