算術(shù)編碼，是圖像壓縮的主要算法之一。
編碼方法
若有一個a、b、c、d四種符號的單符號信源，待編序列為，已知：
符號a b c d
符號概率Pi 0．100 0．010 0．001 0．001
（以二進位小數(shù)表示）
累積概率∑pi 0．000 0．100 0．110 0．111
按照一定精度的數(shù)值作為序列的算術(shù)編碼，實質(zhì)上是分割單位區(qū)間的過程。實現(xiàn)它，必須完成兩個遞推過程：一個代表碼字C（·），另一個代表區(qū)間寬度為A（·）。若記SXi表示S的增長（即S后增加一個符號Xi）序列。則有圖1 。
若記λ為空序列，有則有如圖2 。
并依次求得：
該編碼過程可以用圖3所示的單位區(qū)間劃分的過程來描述。
譯碼為逆遞推過程，可以通過對編碼后的數(shù)值進行比較來實現(xiàn)。即判斷落入哪一個區(qū)間，最后得出一個相應(yīng)的符號序列。
實際的編譯碼過程比較復(fù)雜，但原理相同，算術(shù)編碼的理論性能也可使平均符號代碼長度接近符號，而且對二元信源的編碼實現(xiàn)比較簡單，故受重視。中國將它應(yīng)用于報紙傳真的壓縮設(shè)備中，獲得了良好的效果。
工作原理
在給定符號集和符號概率的情況下，算術(shù)編碼可以給出接近最優(yōu)的編碼結(jié)果。使用算術(shù)編碼的壓縮算法通常先要對輸入符號的概率進行估計，然后再編碼。這個估計越準，編碼結(jié)果就越接近最優(yōu)的結(jié)果。
例: 對一個簡單的信號源進行觀察，得到的統(tǒng)計模型如下:
的機會出現(xiàn)符號 中性
的機會出現(xiàn)符號 陽性
的機會出現(xiàn)符號 陰性
的機會出現(xiàn)符號 數(shù)據(jù)結(jié)束符. (出現(xiàn)這個符號的意思是該信號源'內(nèi)部中止'，在進行數(shù)據(jù)壓縮時這樣的情況是很常見的。當?shù)谝淮我彩俏ㄒ坏囊淮慰吹竭@個符號時，解碼器就知道整個信號流都被解碼完成了。)
算術(shù)編碼可以處理的例子不止是這種只有四種符號的情況，更復(fù)雜的情況也可以處理，包括高階的情況。所謂高階的情況是指當前符號出現(xiàn)的概率受之前出現(xiàn)符號的影響，這時候之前出現(xiàn)的符號，也被稱為上下文。比如在英文文檔編碼的時候，例如，在字母Q或者q出現(xiàn)之后，字母u出現(xiàn)的概率就大大提高了。這種模型還可以進行自適應(yīng)的變化，即在某種上下文下出現(xiàn)的概率分布的估計隨著每次這種上下文出現(xiàn)時的符號而自適應(yīng)更新，從而更加符合實際的概率分布。不管編碼器使用怎樣的模型，解碼器也必須使用同樣的模型。
編碼過程的每一步，除了最后一步，都是相同的。編碼器通常需要考慮下面三種數(shù)據(jù):
下一個要編碼的符號
當前的區(qū)間(在編第一個符號之前，這個區(qū)間是[0,1), 但是之后每次編碼區(qū)間都會變化)
編碼器將當前的區(qū)間分成若干子區(qū)間，每個子區(qū)間的長度與當前上下文下可能出現(xiàn)的對應(yīng)符號的概率成正比。當前要編碼的符號對應(yīng)的子區(qū)間成為在下一步編碼中的初始區(qū)間。
例: 對于前面提出的4符號模型:
中性對應(yīng)的區(qū)間是
陽性對應(yīng)的區(qū)間是
陰性對應(yīng)的區(qū)間是
數(shù)據(jù)結(jié)束符對應(yīng)的區(qū)間是
當所有的符號都編碼完畢，最終得到的結(jié)果區(qū)間即唯一的確定了已編碼的符號序列。任何人使用該區(qū)間和使用的模型參數(shù)即可以解碼重建得到該符號序列。
實際上我們并不需要傳輸最后的結(jié)果區(qū)間，實際上，我們只需要傳輸該區(qū)間中的一個小數(shù)即可。在實用中，只要傳輸足夠的該小數(shù)足夠的位數(shù)(不論幾進制)，以保證以這些位數(shù)開頭的所有小數(shù)都位于結(jié)果區(qū)間就可以了。
例: 下面對使用前面提到的4符號模型進行編碼的一段信息進行解碼。編碼的結(jié)果是(為了容易理解，這里使用十進制而不是二進制；我們也假設(shè)我們得到的結(jié)果的位數(shù)恰好夠我們解碼。下面會討論這兩個問題)。
像編碼器所作的那樣我們從區(qū)間[0,1)開始，使用相同的模型，我們將它分成編碼器所必需的四個子區(qū)間。分數(shù)0.538落在NEUTRAL坐在的子區(qū)間[0,0.6);這向我們提示編碼器所讀的第一個符號必然是NEUTRAL，這樣我們就可以將它作為消息的第一個符號記下來。
然后我們將區(qū)間分成子區(qū)間:
中性 的區(qū)間是
陽性 的區(qū)間是
陰性 的區(qū)間是
數(shù)據(jù)結(jié)束符 的區(qū)間是
我們的分數(shù) .538 在 區(qū)間；所以消息的第二個符號一定是NEGATIVE。
我們再一次將當前區(qū)間劃分成子區(qū)間:
中性 的區(qū)間是
陽性 的區(qū)間是
陰性 的區(qū)間是
數(shù)據(jù)結(jié)束符 的區(qū)間是
我們的分數(shù) .538 落在符號 END-OF-DATA 的區(qū)間；所以，這一定是下一個符號。由于它也是內(nèi)部的結(jié)束符號，這也就意味著編碼已經(jīng)結(jié)束。(如果數(shù)據(jù)流沒有內(nèi)部結(jié)束，我們需要從其它的途徑知道數(shù)據(jù)流在何處結(jié)束--否則我們將永遠將解碼進行下去，錯誤地將不屬于實際編碼生成的數(shù)據(jù)讀進來。)
同樣的消息能夠使用同樣短的分數(shù)來編碼實現(xiàn)如 .534、.535、.536、.537或者是.539，這表明使用十進制而不是二進制會帶來效率的降低。這是正確的是因為三位十進制數(shù)據(jù)能夠表達的信息內(nèi)容大約是9.966位；我們也能夠?qū)⑼瑯拥男畔⑹褂枚M制分數(shù)表示為.10001010(等同于0.5390625)，它僅需8位。這稍稍大于信息內(nèi)容本身或者消息的信息熵，大概是概率為0.6%的 7.361位信息熵。(注意最后一個0必須在二進制分數(shù)中表示，否則消息將會變得不確定起來。)
編碼過程
算術(shù)編碼是用符號的概率和它的編碼間隔兩倆個基本參數(shù)來描述的（見下文教程）。算術(shù)編碼可以是靜態(tài)的或是自適應(yīng)的。在靜態(tài)算術(shù)編碼中，信源符號的概率是固定的。在自適應(yīng)算術(shù)編碼中，信源符號的概率根據(jù)編碼時符號出現(xiàn)的頻繁程度動態(tài)地進行修改。
在編碼期間估算信源符號概率的過程叫建模。需要開發(fā)動態(tài)算術(shù)編碼的原因，是因為事先知道精確的信源符號概率是很難的，而且是不切實際的。動態(tài)建模是確定編碼器壓縮效率的關(guān)鍵。
概述
算術(shù)編碼 是一種無損數(shù)據(jù)壓縮方法，也是一種熵編碼的方法。和其它熵編碼方法不同的地方在于，其他的熵編碼方法通常是把輸入的消息分割為符號，然后對每個符號進行編碼，而算術(shù)編碼是直接把整個輸入的消息編碼為一個數(shù)，一個滿足()的小數(shù)n。
例如
算術(shù)編碼對某條信息的輸出為 1010001111，那么它表示小數(shù) 0.1010001111，也即十進制數(shù) 0.64。
暫時使用十進制表示算法中出現(xiàn)的小數(shù)，這絲毫不會影響算法的可行性。
考慮某條信息中可能出現(xiàn)的字符僅有 a b c 三種，要壓縮保存的信息為 bccb。
采用的是自適應(yīng)模型，開始時暫時認為三者的出現(xiàn)概率相等，也就是都為 1/3，將 0 - 1 區(qū)間按照概率的比例分配給三個字符，即 a 從 0.0000 到 0.3333，b 從 0.3333 到 0.6667，c 從 0.6667 到 1.0000。用圖形表示就是：
+-- 1.0000
|
Pc = 1/3 |
|
+-- 0.6667
|
Pb = 1/3 |
|
+-- 0.3333
|
Pa = 1/3 |
|
+-- 0.0000
現(xiàn)在拿到第一個字符 b，把目光投向 b 對應(yīng)的區(qū)間 。這時由于多了字符 b，三個字符的概率分布變成。好，按照新的概率分布比例劃分 0.3333 - 0.6667 這一區(qū)間，劃分的結(jié)果可以用圖形表示為：
+-- 0.6667
Pc = 1/4 |
+-- 0.5834
|
|
Pb = 2/4 |
|
|
+-- 0.4167
Pa = 1/4 |
+-- 0.3333
接著拿到字符 c，現(xiàn)在要關(guān)注上一步中得到的 c 的區(qū)間。新添了 c 以后，三個字符的概率分布變成 。用這個概率分布劃分區(qū)間 ：
+-- 0.6667
|
Pc = 2/5 |
|
+-- 0.6334
|
Pb = 2/5 |
|
+-- 0.6001
Pa = 1/5 |
+-- 0.5834
現(xiàn)在輸入下一個字符 c，三個字符的概率分布為：來劃分 c 的區(qū)間 ：
+-- 0.6667
|
|
Pc = 3/6 |
|
|
+-- 0.6501
|
Pb = 2/6 |
|
+-- 0.6390
Pa = 1/6 |
+-- 0.6334
輸入最后一個字符 b，因為是最后一個字符，不用再做進一步的劃分了，上一步中得到的 b 的區(qū)間為 ，好，在這個區(qū)間內(nèi)隨便選擇一個容易變成二進制的數(shù)，例如 0.64，將它變成二進制 0.1010001111，去掉前面沒有太多意義的 0 和小數(shù)點，我們可以輸出 1010001111，這就是信息被壓縮后的結(jié)果，就完成了一次最簡單的算術(shù)壓縮過程。
相關(guān)介紹
精度和再歸一化
上面對算術(shù)編碼的解釋進行了一些簡化。尤其是，這種寫法看起來好像算術(shù)編碼首先使用無限精度精度的數(shù)值計算總體上表示最后節(jié)點的分數(shù)，然后在編碼結(jié)束的時候?qū)⑦@個分數(shù)轉(zhuǎn)換成最終的形式。許多算術(shù)編碼器使用優(yōu)先精度的數(shù)值計算，而不是盡量去模擬無限精度，因為它們知道解碼器能夠匹配、并且將所計算的分數(shù)在那個精度四舍五入到對應(yīng)值。一個例子能夠說明一個模型要將間隔分成三份并且使用8位的精度來實現(xiàn)。注意既然精度已經(jīng)知道，我們能用的二進制數(shù)值的范圍也已經(jīng)知道。
一個稱為再歸一化的過程使有限精度不再是能夠編碼的字符數(shù)目的限制。當范圍減小到范圍內(nèi)的所有數(shù)值共享特定的數(shù)字時，那些數(shù)字就送到輸出數(shù)據(jù)中。盡管計算機能夠處理許多位數(shù)的精度，編碼所用位數(shù)少于它們的精度，這樣現(xiàn)存的數(shù)據(jù)進行左移，在右面添加新的數(shù)據(jù)位以盡量擴展能用的數(shù)據(jù)范圍。注意這樣的結(jié)果出現(xiàn)在前面三個例子中的兩個里面。
美國專利
許多算術(shù)編碼所用的不同方法受美國專利的保護。其中一些專利對于實現(xiàn)一些國際標準中定義的算術(shù)編碼算法是很關(guān)鍵的。在這種情況下，這些專利通常按照一種合理和非歧視（RAND）授權(quán)協(xié)議使用（至少是作為標準委員會的一種策略）。在一些著名的案例中（包括一些涉及 IBM的專利）這些授權(quán)是免費的，而在另外一些案例中，則收取一定的授權(quán)費用。RAND條款的授權(quán)協(xié)議不一定能夠滿足所有打算使用這項技術(shù)的用戶，因為對于一個打算生產(chǎn)擁有所有權(quán)軟件的公司來說這項費用是“合理的”，而對于自由軟件和開源軟件項目來說它是不合理的。
在算術(shù)編碼領(lǐng)域做了很多開創(chuàng)性工作并擁有很多專利的一個著名公司是IBM。一些分析人士感到那種認為沒有一種實用并且有效的算術(shù)編碼能夠在不觸犯IBM和其它公司擁有的專利條件下實現(xiàn)只是數(shù)據(jù)壓縮界中的一種持續(xù)的urban legend（尤其是當看到有效的算術(shù)編碼已經(jīng)使用了很長時間最初的專利開始到期）。然而，由于專利法沒有提供“明確界線”測試所以一種威懾心理總讓人擔(dān)憂法庭將會找到觸犯專利的特殊應(yīng)用，并且隨著對于專利范圍的詳細審查將會發(fā)現(xiàn)一個不好的裁決將帶來很大的損失，這些技術(shù)的專利保護然而對它們的應(yīng)用產(chǎn)生了一種阻止的效果。至少一種重要的壓縮軟件bzip2，出于對于專利狀況的擔(dān)心，故意停止了算術(shù)編碼的使用而轉(zhuǎn)向Huffman編碼。
關(guān)于算術(shù)編碼的美國專利列在下面。
Patent 4,122,440 — (IBM) 提交日期 March 4, 1977, 批準日期 Oct 24, 1978 （現(xiàn)在已經(jīng)到期）
Patent 4,286,256 — (IBM) 批準日期 Aug 25, 1981 （大概已經(jīng)到期）
Patent 4,467,317 — (IBM) 批準日期 Aug 21, 1984 （大概已經(jīng)到期）
Patent 4,652,856 — (IBM) 批準日期 Feb 4, 1986 （大概已經(jīng)到期）
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 — (理光)
注意：這個列表沒有囊括所有的專利。關(guān)于更多的專利信息請參見后面的鏈接。
算術(shù)編碼的專利可能在其它國家司法領(lǐng)域存在，參見軟件專利中關(guān)于軟件在世界各地專利性的討論。
參考
數(shù)據(jù)壓縮
區(qū)間編碼
哈夫曼編碼
熵編碼
參考資料 >