熵編碼 之 2. Arithmetic coding

算術編碼是将被編碼的信源表示成實數0~1之間的一個間隔。信源符号序列越長，通過編碼表示它的間隔就越短，需要的二進制比特數就越多。

舉例說明，例如符号a1,a2,a3出現的機率分别為0.4, 0.5, 0.1。則将[0,1)區間配置設定給三個符号，分别為：

a1: [0, 0.4)

a2: [0.4, 0.9)

a3: [0.9, 1)

在編碼之前，完整的資訊間隔是[0, 1)，然後根據輸入的符号，依次将這個區間按照相應的比例變窄。例如，對”a2a2a2a3”進行編碼：

low high

開始編碼前： 0 1

a2 0.4 0.9

a2 0.6 0.85

a2 0.7 0.825

a3 0.8125 0.825

新的low和high的計算方法如下：

NewHigh = OldLow + Range * HighRange(X);

NewLow = OldLow + Range * LowRange(X);

其中Range是指OldHigh-OldLow；HighRange(X)表示取得符号X的被配置設定到區間的上限，例如a2被配置設定的區間為[0.4, 0.9)，其HighRange(a2)=0.9。

通過上面的計算可得到，”a2a2a2a3”所處的區間是[0.8125, 0.825)，在該區間中的任意一個數都可以用來表示該字元串。

解碼過程如下，以”a2a2a2a3”編碼為code = 0.82為例：

0.82所處的區間為[0.4, 0.9)，與a2的區間相符，則該字元串的第一個字元為a2。

然後計算新的code: NewCode = (OldCode - LowRange(x))/Range

code = (0.82-0.4)/0.5 = 0.84

0.84所處的區間仍是[0.4, 0.9)，故第二個字元是a2。

code = (0.84 - 0.4)/0.5 = 0.88

0.88所處的區間仍是[0.4, 0.9)，故第三個字元是a2。

code = (0.88 - 0.4)/0.5 = 0.96

0.96所處區間為[0.9, 1)，故第四個字元為a3。

即字元序列為”a2a2a2a3”