算術編碼

算術編碼是一種無失真數據壓縮方法，也是一種熵編碼的方法。和其它熵編碼方法不同的地方在於，其他的熵編碼方法通常是把輸入的訊息分割為符號，然後對每個符號進行編碼，而算術編碼是直接把整個輸入的訊息編碼為一個數，一個滿足（0.0 ≤ n < 1.0）的小數n。

算術編碼工作原理[編輯]

在給定符號集和符號概率的情況下，算術編碼可以給出接近最佳的編碼結果。使用算術編碼的壓縮演算法通常先要對輸入符號的概率進行估計，然後再編碼。這個估計越准，編碼結果就越接近最佳的結果。

例: 對一個簡單的訊號源進行觀察，得到的統計模型如下：

60%的機會出現符號中性
20%的機會出現符號陽性
10%的機會出現符號陰性
10%的機會出現符號數據結束符. (出現這個符號的意思是該訊號源'內部中止'，在進行數據壓縮時這樣的情況是很常見的。當第一次也是唯一的一次看到這個符號時，解碼器就知道整個訊號流都被解碼完成了)。

算術編碼可以處理的例子不止是這種只有四種符號的情況，更複雜的情況也可以處理，包括高階的情況。所謂高階的情況是指當前符號出現的概率受之前出現符號的影響，這時候之前出現的符號，也被稱為上下文。比如在英文文件編碼的時候，例如，在字母Q或者q出現之後，字母u出現的概率就大大提高了。這種模型還可以進行自適應的變化，即在某種上下文下出現的概率分佈的估計隨着每次這種上下文出現時的符號而自適應更新，從而更加符合實際的概率分佈。不管編碼器使用怎樣的模型，解碼器也必須使用同樣的模型。

一個簡單的例子以下用一個符號序列怎樣被編碼來作一個例子：假如有一個以A、B、C三個出現機會均等的符號組成的序列。若以簡單的分組編碼會十分浪費地用2 bits來表示一個符號：其中一個符號是可以不用傳的（下面可以見到符號B正是如此）。為此，這個序列可以三進制的0和2之間的有理數表示，而且每位數表示一個符號。例如，「ABBCAB」這個序列可以變成0.011201（base3，即0為A, 1為B, 2為C）。用一個定點二進制數字去對這個數編碼使之在恢復符號表示時有足夠的精度，譬如0.001011001(base2) –只用了9個bit，比起簡單的分組編碼少（1 – 9/12）x100% = 25%。這對於長序列是可行的因為有高效的、適當的演算法去精確地轉換任意進制的數字。

編碼過程的每一步，除了最後一步，都是相同的。編碼器通常需要考慮下面三種數據：

下一個要編碼的符號
當前的區間（在編第一個符號之前，這個區間是[0,1）,但是之後每次編碼區間都會變化)
模型中在這一步可能出現的各個符號的概率分佈（像前面提到的一樣，高階或者自適應的模型中，每一步的概率並不必須一樣）

編碼器將當前的區間分成若干子區間，每個子區間的長度與當前上下文下可能出現的對應符號的概率成正比。當前要編碼的符號對應的子區間成為在下一步編碼中的初始區間。

例:對於前面提出的4符號模型：

中性對應的區間是[0, 0.6)
陽性對應的區間是[0.6, 0.8)
陰性對應的區間是[0.8, 0.9)
數據結束符對應的區間是[0.9, 1)

當所有的符號都編碼完畢，最終得到的結果區間即唯一的確定了已編碼的符號序列。任何人使用該區間和使用的模型參數即可以解碼重建得到該符號序列。

實際上我們並不需要傳輸最後的結果區間，實際上，我們只需要傳輸該區間中的一個小數即可。在實用中，只要傳輸足夠的該小數足夠的位數（不論幾進制），以保證以這些位數開頭的所有小數都位於結果區間就可以了。

例:下面對使用前面提到的4符號模型進行編碼的一段資訊進行解碼。編碼的結果是0.538（為了容易理解，這裏使用十進制而不是二進制；我們也假設我們得到的結果的位數恰好夠我們解碼。下面會討論這兩個問題）。

像編碼器所作的那樣我們從區間[0,1)開始，使用相同的模型，我們將它分成編碼器所必需的四個子區間。分數0.538落在NEUTRAL坐在的子區間[0,0.6)；這向我們提示編碼器所讀的第一個符號必然是NEUTRAL，這樣我們就可以將它作為訊息的第一個符號記下來。

然後我們將區間[0,0.6)分成子區間：

中性的區間是[0, 0.36) -- [0, 0.6)的60%
陽性的區間是[0.36, 0.48) -- [0, 0.6)的20%
陰性的區間是[0.48, 0.54) -- [0, 0.6)的10%
數據結束符的區間是[0.54, 0.6). -- [0, 0.6)的10%

我們的分數.538在[0.48, 0.54)區間；所以訊息的第二個符號一定是NEGATIVE。

我們再一次將當前區間劃分成子區間：

中性的區間是[0.48, 0.516)
陽性的區間是[0.516, 0.528)
陰性的區間是[0.528, 0.534)
數據結束符的區間是[0.534, 0.540).

我們的分數.538落在符號END-OF-DATA的區間；所以，這一定是下一個符號。由於它也是內部的結束符號，這也就意味着編碼已經結束。（如果數據流沒有內部結束，我們需要從其它的途徑知道數據流在何處結束——否則我們將永遠將解碼進行下去，錯誤地將不屬於實際編碼生成的數據讀進來。）

效率低下的來源[編輯]

前一個例子中的訊息0.538可能已經由同樣短的分數 0.534, 0.535, 0.536, 0.537, 0.539 編碼。這表明使用十進製而不是二進制引入了一些低效率。這是對的;三位十進制的資訊內容是 $3*\log _{2}(10)\approx 9.966$ 個位元;相同的訊息可以在二進制分數 0.10001010 （相當於 0.5390625 十進制）中編碼，僅花費 8 個位元。（最後的零必須在二進制小數中指定，否則訊息將是不明確的，沒有外部資訊，如壓縮流大小。）

該 8 位元輸出大於資訊內容或訊息的熵，也就是：

\sum -\log _{2}(p_{i})=-\log _{2}(0.6)-\log _{2}(0.1)-\log _{2}(0.1)=7.381{\text{ bits}}

但是在二進制編碼中必須使用整數碼，因此該訊息的編碼器將使用至少8位元，從而產生比熵內容大 8.4％的訊息。隨着訊息大小的增加，這種至多 1 位的低效率導致相對較少的開銷。

此外，要求保護的符號概率為 [0.6, 0.2, 0.1, 0.1) ，但本例中的實際頻率為 [0.33, 0, 0.33, 0.33) 。如果為這些頻率重新調整間隔，則訊息的熵將是 4.755 位元，並且相同的中性負數據結束訊息可以被編碼為間隔 [0, 1/3) ; [1/9, 2/9) ; [5/27, 6/27) ; 和二進制間隔 [0.00101111011, 0.00111000111) 。這也是算術編碼等統計編碼方法如何產生大於輸入訊息的輸出訊息的範例，尤其是在概率模型關閉的情況下。

編碼[編輯]

若dataX有M個可能的值 $(X[i]=1,2,...orM)$ ,使用k進位的編碼，且

  $P_{n}$ :the probability of x = n(from prediction)

  $S_{0}=0,S_{n}=\sum _{j=1}^{n}P_{j}$ 

現在要對dataX做編碼，假設length(X) = N

算術編碼的運算方式

initiation: lower =  $S_{X[1]-1}$   upper =  $S_{X[1]}$ 

for i=2:N

     lower =  $S_{X[i]-1}\times (upper-lower)$ 

     upper =  $S_{X[i]}\times (upper-lower$ )

end

假設 lower $\leq C\cdot k^{-b}<(C+1)\cdot k^{-b}\leq upper$
且C和b為整數(b越小越理想)，則dataX可以被編碼成 $C_{(k,b)}$
且 $C_{(k,b)}$
為k進為何b bits來表示C
ex = 01110
ans = b=5,C=14

範例

1.假設要對X來做二進位(k=2)的編碼且經由事先的估計，X[i] = a 的概率為0.8,X[i] = b 的概率為0.2
$\Rightarrow P_{1}=0.8,P_{2}=0.2,S_{0}=0,S_{1}=0.8,S_{2}=1$
若實際上輸入的資料為X = a a a b a a initial (X[1] = a): lower = 0, upper = 0.8
When i=2, (X[2] = a): lower = 0, upper = 0.64
When i=3, (X[3] = a): lower = 0, upper = 0.512
When i=4, (X[4] = b): lower = 0.4096, upper = 0.512
When i=5, (X[5] = a): lower = 0.4096, upper = 0.49152
When i=6, (X[6] = a): lower = 0.4096, upper = 0.475136
由於 lower = 0.4096, upper = 0.475136
lower $\leq 14\cdot 2^{-5}<15\cdot 2^{-5}\leq$ upper
所以編碼結果為 $14_{(2,5)}=01110$ ,2進位,5bits

解碼[編輯]

假設編碼的結果為Y,length(Y) = b,其他的假設和編碼相同(k進位)

算術解碼的運算方式

initiation: lower = 0, upper = 1, lower1 = 1, upper1 = 1

for i=1:N

     check = 1;
     while check =1
       if there exists an n such that 
           $lower+(upper-lower)S_{n-1}\leq lower1$  and 

           $lower+(upper-lower)S_{n}\leq upper1$  are both satisfied,

          then check = 0;
       else
           $upper1=lower1+(Y[j]+1)k^{-j}$ 

           $lower1=lower1+(Y[j])k^{-j}$ 

          j = j+1
       end
       X(i) = n;
        $lower=lower+(upper-lower)S_{n-1}$ 

        $upper=lower+(upper-lower)S_{n}$ 

end

資料長度[編輯]

假設 $P_{n}$ 是預測的X[i] = n的概率, $Q_{n}$ 是實際上的X[i] = n的概率
也就是說,若length(X) = N,當中會有 $Q_{n}$ N個elements等於n 則 $upper-lower=\prod _{m=1}^{M}P_{m}^{Q_{m}N}$
另一方面，由於編碼的假設
$k^{-b}\leq upper-lower<(2k)k^{-b}$
$-log_{k}(upper-lower)\leq b<-log_{k}(upper-lower)+1+log_{k}2$
$ceil(-N\sum _{m=1}^{M}Q_{m}log_{k}P_{m})\leq b\leq floor(-N\sum _{m=1}^{M}Q_{m}log_{k}P_{m}+log2)+1$
在概率的預測完全準確的情況下, $Q_{m}=P_{m}$
Totoal coding length b 的範圍是
$ceil(-N\sum _{m=1}^{M}P_{m}log_{k}P_{m})\leq b\leq floor(-N\sum _{m=1}^{M}P_{m}log_{k}P_{m}+log2)+1$
$\Rightarrow ceil(-N{\frac {entropy}{logk}})\leq b\leq floor(-N{\frac {entropy}{logk}}+log2)+1$
算術編碼的總資料長度的上限比霍夫曼編碼更低

自適應算術編碼[編輯]

與其他類似的數據壓縮方法相比，算術編碼的一個優點是適應的便利性。適應是在處理數據時改變頻率（或概率）表。只要解碼中的頻率表以與編碼相同的方式和相同的步驟被替換，解碼的數據就匹配原始數據。通常，同步基於在編碼和解碼過程期間出現的符號的組合。

精度和再正規化[編輯]

上面對算術編碼的解釋進行了一些簡化。尤其是，這種寫法看起來好像算術編碼首先使用無限精度精度的數值計算總體上表示最後節點的分數，然後在編碼結束的時候將這個分數轉換成最終的形式。許多算術編碼器使用有限精度的數值計算，而不是儘量去模擬無限精度，因為它們知道解碼器能夠匹配、並且將所計算的分數在那個精度四捨五入到對應值。一個例子能夠說明一個模型要將間隔[0,1]分成三份並且使用8位元的精度來實現。注意既然精度已經知道，我們能用的二進制數值的範圍也已經知道。

符號	概率（使用分數表示）	減到8位元精度的間隔（用分數表示）	減到8位元精度的間隔（用二進制表示）	二進制範圍
A	1/3	[0, 85/256)	[0.00000000, 0.01010101)	00000000 – 01010100
B	1/3	[85/256, 171/256)	[0.01010101, 0.10101011)	01010101 – 10101010
C	1/3	[171/256, 1)	[0.10101011, 1.00000000)	10101011 – 11111111

一個稱為再歸一化的過程使有限精度不再是能夠編碼的字元數目的限制。當範圍減小到範圍內的所有數值共用特定的數字時，那些數字就送到輸出數據中。儘管電腦能夠處理許多位數的精度，編碼所用位數少於它們的精度，這樣現存的數據進行左移，在右面添加新的數據位以儘量擴充能用的數據範圍。注意這樣的結果出現在前面三個例子中的兩個裏面。

符號	概率	範圍	能夠輸出的數據位	再歸一化後的範圍
A	1/3	00000000 – 01010100	0	00000000 – 10101001
B	1/3	01010101 – 10101010	None	01010101 – 10101010
C	1/3	10101011 – 11111111	1	01010110 – 11111111

算術編碼和其他壓縮方法的關係[編輯]

霍夫曼編碼[編輯]

算術編碼和哈夫曼編碼的相似程度很高——事實上，哈夫曼編碼只是算術編碼的一個特例。但是，算術編碼將整個訊息翻譯成一個表示為基數 b，而不是將訊息中的每個符號翻譯成一系列的以 b 為基數的數字，因此通常比哈夫曼編碼更能達到最佳熵編碼。

因為算術編碼不能一次壓縮一個數據，所以在壓縮iid字串時它可以任意接近熵。相反，使用霍夫曼編碼（到字串）的擴展不會達到熵，除非字母符號的所有概率都是 2 的冪，在這種情況下，霍夫曼和算術編碼都實現熵。

當霍夫曼編碼二進製字串時，即使熵低（例如（{0, 1}）具有概率{0.95, 0.05}），也不可能進行壓縮。霍夫曼編碼為每個值分配 1 位元，產生與輸入長度相同的代碼。相比之下，算術編碼可以更加地壓縮位元，接近最佳壓縮比

1-[-0.95\log _{2}(0.95)+-0.05\log _{2}(0.05)]\approx 71.4\%.

解決霍夫曼編碼次優性的一種簡單方法是連接符號（阻塞）以形成新的字母表，其中每個新符號表示來自原始字母表的原始符號序列（在這種情況下是位元）。在上面的例子中，在編碼之前對三個符號的序列進行分組將產生具有以下頻率的新「超符號」：

000: 85.7%
001, 010, 100: 4.5% each
011, 101, 110: 0.24% each
111: 0.0125%

通過這種分組，霍夫曼編碼每三個符號平均為 1.3 位元，或每符號 0.433 位元，而原始編碼中每符號一位元，即 $56.7\%$ 壓縮。允許任意大的序列隨意接近熵（就像算術編碼一樣），但需要大量代碼才能這樣做，因此不如算術編碼那麼實用。

另一種方法是通過基於霍夫曼的 Golomb-Rice 編碼編碼遊程長度。這種方法允許比算術編碼或甚至霍夫曼編碼更簡單和更快的編碼/解碼，因為後者需要表尋找。在 {0.95, 0.05} 範例中，具有四位餘數的 Golomb-Rice 代碼實現了壓縮率 $71.1\%$ ，遠遠低於使用三位塊的壓縮率。 Golomb-Rice 代碼僅適用於伯努利輸入，例如本例中的輸入，因此它不能代替所有情況下的阻塞。

區間編碼[編輯]

算術編碼與區間編碼有很深的相似淵源，以至於人們通常認為兩者的效能是相同的，如果確實有什麼不同的話也只是區間編碼僅僅落後幾個位的值而已。區間編碼與算術編碼不同，通常認為它不被任何公司的專利所約束。

區間編碼的原理是這樣的，它沒有像算術編碼那樣從 [0,1] 開始並根據每個字元出現的概率把它分成相應的不同的小區間，它從如 000,000,000,000 到 999,999,999,999 這樣一個很大的非負整數區間開始，並且根據每個字元的概率劃分成小的子區間。當子區間小到一定程度最後結果的開頭數字出現的時候，那些數字就能夠「左移」出整個運算，並且用「右邊」的數字替換——每次出現移位時，就大體相當於最初區間的一個回歸放大（retroactive multiplication）。

關於算術編碼的美國專利[編輯]

許多算術編碼所用的不同方法受美國專利的保護。其中一些專利對於實現一些國際標準中定義的算術編碼演算法是很關鍵的。在這種情況下，這些專利通常按照一種合理和非歧視（RAND）授權協定使用（至少是作為標準委員會的一種策略）。在一些著名的案例中（包括一些涉及IBM的專利）這些授權是免費的，而在另外一些案例中，則收取一定的授權費用。RAND條款的授權協定不一定能夠滿足所有打算使用這項技術的用戶，因為對於一個打算生產擁有所有權軟件的公司來說這項費用是「合理的」，而對於自由軟件和開源軟件專案來說它是不合理的。

在算術編碼領域做了很多開創性工作並擁有很多專利的一個著名公司是IBM。一些分析人士感到那種認為沒有一種實用並且有效的算術編碼能夠在不觸犯IBM和其它公司擁有的專利條件下實現只是數據壓縮界中的一種持續的都會傳奇（尤其是當看到有效的算術編碼已經使用了很長時間最初的專利開始到期）。然而，由於專利法沒有提供「明確界線」測試所以一種威懾心理總讓人擔憂法庭將會找到觸犯專利的特殊應用，並且隨着對於專利範圍的詳細審查將會發現一個不好的裁決將帶來很大的損失，這些技術的專利保護然而對它們的應用產生了一種阻止的效果。至少一種重要的壓縮軟件bzip2，出於對於專利狀況的擔心，故意停止了算術編碼的使用而轉向Huffman編碼。

關於算術編碼的美國專利列在下面。

Patent 4,122,440—（IBM）提交日期March 4, 1977,批准日期Oct 24, 1978（現在已經到期）
Patent 4,286,256—（IBM）批准日期Aug 25, 1981（大概已經到期）
Patent 4,467,317—（IBM）批准日期Aug 21, 1984（大概已經到期）
Patent 4,652,856—（IBM）批准日期Feb 4, 1986（大概已經到期）
Patent 4,891,643—（IBM）提交時間1986/09/15,批准日期1990/01/02
Patent 4,905,297—（IBM）批准日期Feb 27, 1990
Patent 4,933,883—（IBM）批准日期Jun 12, 1990
Patent 4,935,882—（IBM）批准日期Jun 19, 1990
Patent 4,989,000—（???）提交時間1989/06/19,批准日期1991/01/29
Patent 5,099,440
Patent 5,272,478—（Ricoh）

注意：這個列表沒有囊括所有的專利。關於更多的專利資訊請參見後面的連結。[1] （頁面存檔備份，存於互聯網檔案館）

算術編碼的專利可能在其它國家司法領域存在，參見軟件專利中關於軟件在世界各地專利性的討論。

參考[編輯]

上面文章的一個早期版本（公開內容）張貼在PlanetMath （頁面存檔備份，存於互聯網檔案館）.

外部連結[編輯]

The on-line textbook: Information Theory, Inference, and Learning Algorithms （頁面存檔備份，存於互聯網檔案館）, by David J.C. MacKay, explains arithmetic coding in Chapter 6.
本條目參照的公有領域材料。材料來自NIST的文件：Black, Paul E. arithmetic coding. 演算法與資料結構辭典（英語：Dictionary of Algorithms and Data Structures）.
"Arithmetic Coding" site on Compression-links.info (free open version of DataCompression.info) （頁面存檔備份，存於互聯網檔案館） - collection of links pertaining to arithmetic coding
Newsgroup posting （頁面存檔備份，存於互聯網檔案館） with a short worked example of arithmetic encoding (integer-only).
AIC-Context Adaptive Binary Arithmetic Coding （頁面存檔備份，存於互聯網檔案館） very clear concept and demonstration for fresher.