動態馬可夫壓縮

動態馬可夫壓縮是一種無損壓縮演算法,由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)

外部連結

编辑