[科普中國]-動態(tài)馬爾科夫壓縮

動態(tài)馬爾可夫壓縮是一種無損壓縮算法，由Gordan Cormack和Nigel Horspool發(fā)明。該算法類似預(yù)測性算術(shù)編碼，不同的是輸入數(shù)據(jù)預(yù)測是以比特為單位，而非字節(jié)。動態(tài)馬爾可夫壓縮具有良好的壓縮比以及中等的運算速率，但是需求較高的存儲器。

算法動態(tài)馬爾可夫壓縮的預(yù)測以及編碼以比特為單位，并使用算術(shù)編碼作為編碼方式。

算術(shù)編碼動態(tài)馬爾可夫壓縮使用的比特編碼器具有兩部分：預(yù)測器和比特編碼器。預(yù)測器接受n比特輸入字符串x=x1x2...xn，其發(fā)生概率可寫作p(x) =p(x1)p(x2|x1)p(x3|x1x2)...p(xn|x1x2...xn–1)。算術(shù)編碼器中有兩二進(jìn)制高精準(zhǔn)度參數(shù)phigh和plow，分別代表該模型發(fā)生的概率之區(qū)間上限與下限。x之編碼記作px，為在phigh和plow之間長度最短的數(shù)。我們永遠(yuǎn)可以找到不比夏農(nóng)極限，log21/p(x')，長超過一個比特的px。要找到這樣的px，只需要把phigh在第一個和phigh相異比特之后的比特全數(shù)舍棄即可。

接下來的壓縮步驟如下。初始phigh設(shè)為1，plow設(shè)為0。對于每個比特，預(yù)測器預(yù)測p0=p(xi= 0|x1x2...xi–1)和p1= 1?p0，這里p0代表該比特為0的概率，p1代表該比特為1的概率。接著，算術(shù)編碼器將當(dāng)前的概率范圍，也就是(plow,phigh)，依p0和p1之比例分區(qū)成二新區(qū)間。下一個比特xi的子概率區(qū)間就成為新的概率區(qū)間，如此周而復(fù)始。

在解壓縮的時候，預(yù)測器會對于已解出的比特做出一樣的預(yù)測串。算術(shù)編碼器接著做出一樣的區(qū)間分區(qū)，然后輸出對應(yīng)到每個px的比特xi。

在實現(xiàn)上，phigh和plow并非一定要維持在很高的精準(zhǔn)度。1

動態(tài)馬爾可夫壓縮之模型動態(tài)馬爾可夫壓縮之預(yù)測器是一個將比特對應(yīng)到一對正整數(shù)n0和n1之表。n0和n1分別代表0和1的累計個數(shù)。因此，預(yù)測下一個比特為0的概率可以寫作p0=n0/n=n0/(n0+n1)，而下一個比特為1的概率可以寫作p1= 1?p0=n1/n。

在原始的動態(tài)馬爾可夫壓縮中，初始的表為長度為八到十五個比特的二進(jìn)制數(shù)所成集合，而初始態(tài)設(shè)為任一長度為八的二進(jìn)制數(shù)。計數(shù)被初始化為一接近零的小數(shù)而非零，這是為了維持解碼出未曾出現(xiàn)過比特的可能。

壓縮和解壓縮的模型是雷同的。對于每一個比特，p0和p1先被計算，接著對xi編碼或解碼。

增加新的數(shù)據(jù)上述之動態(tài)馬爾可夫模型等價于一次環(huán)境模型。然而，使用時可能加入更長的待壓內(nèi)容以增進(jìn)壓縮。舉例來說，如果當(dāng)前數(shù)據(jù)為A，增加數(shù)據(jù)為B，則B有可能需要舍棄左邊的某些比特，接著編碼器必須增加一個B的復(fù)制C。C的代表數(shù)據(jù)可視為A在右側(cè)增加一個新比特但未舍棄左邊數(shù)個比特。A的鏈接會從B改成C。B和C會進(jìn)行同樣的預(yù)測，也會指向一樣的一對狀態(tài)。C之總比特計數(shù)n=n0+n1等于A對輸入比特x之計數(shù)nx，而B之計數(shù)會減掉該數(shù)。

舉個例子，假設(shè)狀態(tài)A代表的數(shù)據(jù)是11111，當(dāng)輸入比特為0，狀態(tài)轉(zhuǎn)變?yōu)锽，其代表數(shù)據(jù)為110，等于是舍棄了最左邊的三個比特并在右邊加入一個新的比特。狀態(tài)A所計零比特之?dāng)?shù)目為4。狀態(tài)B計有3個零比特和7個一比特，故其p1= 0.7。

|| ||

狀態(tài)C為B的復(fù)制。C代表的數(shù)據(jù)為111110。B和C都預(yù)測一比特出現(xiàn)的概率為0.7，并且都轉(zhuǎn)為一樣的狀態(tài)，E和F。2

|| ||

本詞條內(nèi)容貢獻(xiàn)者為:

王慧維 - 副研究員 - 西南大學(xué)