动态马可夫压缩

动态马可夫压缩是一种无损压缩演算法,由Gordan CormackNigel Horspool发明。该演算法类似预测性算术编码,不同的是输入资料预测是以位元为单位,而非位元组。动态马可夫压缩具有良好的压缩比以及中等的运算速率,但是需求较高的记忆体

演算法

编辑

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

算术编码

编辑

动态马可夫压缩使用的位元编码器具有两部分:预测器位元编码器。预测器接受n位元输入字串x = x1x2...xn,其发生机率可写作 p(x) = p(x1)p(x2|x1)p(x3|x1x2)... p(xn|x1x2...xn–1)。算术编码器中有两二进位高精准度参数phighplow,分别代表该模型发生的机率之区间上限与下限。x之编码记作px,为在phighplow之间长度最短的数。我们永远可以找到不比夏农极限,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),依p0p1之比例分割成二新区间。下一个位元xi的子机率区间就成为新的机率区间,如此周而复始。

在解压缩的时候,预测器会对于已解出的位元做出一样的预测串。算术编码器接著做出一样的区间分割,然后输出对应到每个px的位元xi

在实作上,phighplow并非一定要维持在很高的精准度

动态马可夫压缩之模型

编辑

动态马可夫压缩之预测器是一个将位元对应到一对正整数n0n1之表。n0n1分别代表0和1的累计个数。因此,预测下一个位元为0的机率可以写作p0 = n0/n = n0/(n0 + n1),而下一个位元为1的机率可以写作p1 = 1 − p0 = n1/n

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

压缩和解压缩的模型是雷同的。对于每一个位元,p0p1先被计算,接著对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)

外部链接

编辑