動態馬可夫壓縮

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

基本介紹

• 中文名：動態馬可夫壓縮
• 學科：電子工程

算法

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

算術編碼

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

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

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

在實現上，p_high和p_low並非一定要維持在很高的精準度。

動態馬爾可夫壓縮之模型

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

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

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

增加新的數據

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