動態馬爾科夫壓縮

動態馬爾可夫壓縮是一種無損壓縮算法,由Gordan Cormack和Nigel Horspool發明。該算法類似預測性算術編碼,不同的是輸入數據預測是以比特為單位,而非位元組。動態馬爾可夫壓縮具有良好的壓縮比以及中等的運算速率,但是需求較高的存儲器。

算法

動態馬爾可夫壓縮的預測以及編碼以比特為單位,並使用算術編碼作為編碼方式。

算術編碼

動態馬爾可夫壓縮使用的比特編碼器具有兩部分:預測器和比特編碼器。預測器接受 n比特輸入字元串 x= x x... x,其發生機率可寫作 p( x) = p( x) p( x| x) p( x| x x)... p( x| x x... x)。算術編碼器中有兩二進制高精準度參數 p和 p,分別代表該模型發生的機率之區間上限與下限。 x之編碼記作 p,為在 p和 p之間長度最短的數。我們永遠可以找到不比夏農極限,log1/ p( x'),長超過一個比特的 p。要找到這樣的 p,只需要把 p在第一個和 p相異比特之後的比特全數捨棄即可。

接下來的壓縮步驟如下。初始 p設為1, p設為0。對於每個比特,預測器預測 p= p( x= 0| x x... x)和 p= 1− p,這裡 p代表該比特為0的機率, p代表該比特為1的機率。接著,算術編碼器將當前的機率範圍,也就是( p, p),依 p和 p之比例分區成二新區間。下一個比特 x的子機率區間就成為新的機率區間,如此周而復始。

在解壓縮的時候,預測器會對於已解出的比特做出一樣的預測串。算術編碼器接著做出一樣的區間分區,然後輸出對應到每個 p的比特 x。

在實現上, p和 p並非一定要維持在很高的精準度。

動態馬爾可夫壓縮之模型

動態馬爾可夫壓縮之預測器是一個將比特對應到一對正整數 n和 n之表。 n和 n分別代表0和1的累計個數。因此,預測下一個比特為0的機率可以寫作 p= n/ n= n/( n+ n),而下一個比特為1的機率可以寫作 p= 1− p= n/ n。

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

壓縮和解壓縮的模型是雷同的。對於每一個比特, p和 p先被計算,接著對 x編碼或解碼。

增加新的數據

上述之動態馬爾可夫模型等價於一次環境模型。然而,使用時可能加入更長的待壓內容以增進壓縮。舉例來說,如果當前數據為A,增加數據為B,則B有可能需要捨棄左邊的某些比特,接著編碼器必須增加一個B的複製C。C的代表數據可視為A在右側增加一個新比特但未捨棄左邊數個比特。A的連結會從B改成C。B和C會進行同樣的預測,也會指向一樣的一對狀態。C之總比特計數 n= n+ n等於A對輸入比特 x之計數 n,而B之計數會減掉該數。

舉個例子,假設狀態A代表的數據是11111,當輸入比特為0,狀態轉變為B,其代表數據為110,等於是捨棄了最左邊的三個比特並在右邊加入一個新的比特。狀態A所計零比特之數目為4。狀態B計有3個零比特和7個一比特,故其 p= 0.7。

狀態nnnextnext
A = 111114B
B = 11037EF

狀態C為B的複製。C代表的數據為111110。B和C都預測一比特出現的機率為0.7,並且都轉為一樣的狀態,E和F。

狀態nnnextnext
A = 111114C
B = 1101.84.2EF
C = 1111101.22.8EF

相關詞條

熱門詞條

聯絡我們