2014年1月13日 星期一

Arithmetic Coding by Matlab (1)

跟Huffman Coding比起來,Arithmetic Coding(以下譯成算數編碼)真是非常特別的一種壓縮方式。機率低編碼長、機率高編碼短是Huffman Coding的主要原理,簡單而明瞭。可是算數編碼利用介於0,1之間的實數區間來編碼一長串的資料,而不是每一個字元給予不同的編碼,這種編碼的好處與特性可在後面的敘述中呈現出來。


先來講講算數編碼的流程:假設S={A,B,C},三個字元出現的機率分別為p(A)=0.7, p(B)=0.1, p(C)=0.2。現在有一字串為BAAC,它的算數編碼為何?

一開始的實數區間是[0,1),喔!先複習一下高中數學:x∈[a,b)⇔a≤x<b。所以這個區間的下界為0(lbound=0),上界為1(ubound=1),區間長度為range=ubound-lbound=1。假設BAAC的編碼順序為B→A→A→C。

後續的作法皆是將目前區間長度(range),依A, B, C三字元機率比率切成三等份,也就是各占range的7:1:2。


處理第一個字元B:

  • 此時區間為[0,1),range=1。A:B:C=7:1:2,所以
  • A=[lbound,lbound+range×0.7), 
  • B=[lbound+range×0.7,lbound+range×0.7+range×0.1), 
  • C=[lbound+range×0.7+range×0.1,ubound)。
  • B=[0+1×0.7,0+1×0.7+1×0.1)=[0.7,0.8), 所以輸出[0.7,0.8)


處理第二個字元A:

  • 此時區間為[0.7,0.8),range=0.8-0.7=0.1。A:B:C=7:1:2,所以
  • A=[lbound,lbound+range×0.7), 
  • B=[lbound+range×0.7,lbound+range×0.7+range×0.1), 
  • C=[lbound+range×0.7+range×0.1,ubound)。
  • A=[0.7,0.7+0.1×0.7)=[0.7,0.77), 所以輸出[0.7,0.77)


處理第三個字元A:

  • 此時區間為[0.7,0.77),range=0.77-0.7=0.07。A:B:C=7:1:2,所以
  • A=[lbound,lbound+range×0.7), 
  • B=[lbound+range×0.7,lbound+range×0.7+range×0.1), 
  • C=[lbound+range×0.7+range×0.1,ubound)。
  • A=[0.7,0.7+0.07×0.7)=[0.7,0.749), 所以輸出[0.7,0.749)


處理第四個字元C:

  • 此時區間為[0.7,0.749),range=0.749-0.7=0.049。A:B:C=7:1:2,所以
  • A=[lbound,lbound+range×0.7), 
  • B=[lbound+range×0.7,lbound+range×0.7+range×0.1), 
  • C=[lbound+range×0.7+range×0.1,ubound)。
  • C=[0.7+0.049×(0.7+0.1),0.749)=[0.7392,0.749), 所以輸出[0.7392,0.749)

因此算數編碼法將BAAC編碼成[0.7392,0.749)

將以上的作法以簡短的話來說,『將擬編碼字元依其機率比例切割目前區間』。所以字串越長,所得的區間就越小,將上述例子以下圖表示。



因此算數編碼的演算法可以簡單表示成

input: str[1..n] /* 擬編碼的字串, 共有n個字元 */
         p[ ] /* 每個字元的機率值 */
output: lbound, ubound  
begin
    lbound=0, ubound=1;
    for i=1 to n do
    begin
         range = ubound-lbound;
         ch ← str[i];
         pp ← p[ch];
         new_lbound = lbound + (p[1]+p[2]+...+p[ch-1])*range;
         new_uboud = lbound+(p[1]+p[2]+...+p[ch])*range;
    end
    lbound←new_lbound;
    ubound←new_ubound;
    range=ubound-lbound;
end

現在來用Matlab來寫這個程式吧!


執行看看!

在程式中第24-25行,故意將過程印出來,結果與講解的過程完全相同。

↓同樣的程式在Octave執行看看,結果相同!

--- end ---

還沒啦!那有壓縮的結果是一個區間,應該是一長串的0與1才對!?
所以還有續集.....

沒有留言:

張貼留言