動態馬可夫壓縮
 |
動態馬可夫壓縮是一種無損壓縮演算法，由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）
外部連結