先來講講算數編碼的流程:假設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)
- 此時區間為[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來寫這個程式吧!
執行看看!
沒有留言:
張貼留言