动态马尔可夫压缩

动态马尔可夫压缩是一种无损压缩算法,由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)

外部链接

编辑