算術編碼簡單研究

算術編碼 是一種無損數據壓縮方法，也是一種熵編碼的方法。和其它熵編碼方法不同的地方在于，其他的熵編碼方法通常是把輸入的消息分割為符號，然后對每個符號進行編碼，而算術編碼是直接把整個輸入的消息編碼為一個數，一個滿足(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 的區間；所以，這一定是下一個符號。由于它也是內部的結束符號，這也就意味著編碼已經結束。（如果數據流沒有內部結束，我們需要從其它的途徑知道數據流在何處結束——否則我們將永遠將解碼進行下去，錯誤地將不屬于實際編碼生成的數據讀進來。）

同樣的消息能夠使用同樣短的分數來編碼實現如 .534、.535、.536、.537或者是.539，這表明使用十進制而不是二進制會帶來效率的降低。這是正確的是因為三位十進制數據能夠表達的信息內容大約是9.966位；我們也能夠將同樣的信息使用二進制分數表示為.10001010（等同于0.5390625），它僅需8位。這稍稍大于信息內容本身或者消息的信息熵，大概是概率為0.6%的 7.361位信息熵。（注意最后一個0必須在二進制分數中表示，否則消息將會變得不確定起來。）

[編輯] 精度和再正規化

上面對算術編碼的解釋進行了一些簡化。尤其是，這種寫法看起來好像算術編碼首先使用無限精度精度的數值計算總體上表示最后節點的分數，然后在編碼結束的時候將這個分數轉換成最終的形式。許多算術編碼器使用優先精度的數值計算，而不是盡量去模擬無限精度，因為它們知道解碼器能夠匹配、并且將所計算的分數在那個精度四舍五入到對應值。一個例子能夠說明一個模型要將間隔[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	00101010 - 11010101
C	1/3	10101011 - 11111111	1	01010110 - 11111111

[編輯] 算術編碼和其他壓縮方法的聯系

[編輯] 哈夫曼編碼

在算術編碼和哈夫曼編碼之間有很大的相似性 -- 實際上，哈夫曼編碼只是算術編碼的一個特例 -- 但是由于算術編碼將整個消息翻譯成一個表示為基數 b,而不是將消息中的每個符號翻譯成一系列的以b為基數的數字，它通常比哈夫曼編碼更能達到最優熵編碼。

[編輯] 區間編碼

算術編碼與區間編碼有很深的相似淵源，它們如此相似以至于通常認為它們的性能是相同的，如果確實有什么不同的話也只是區間編碼僅僅落后幾個位的值而已。區間編碼與算術編碼不同，通常認為它不被任何公司的專利所涵蓋。

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

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

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

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

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