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才對！？
所以還有續集.....