區間編碼

區間編碼是一種算術編碼形式的數據壓縮方法，但是人們認為這種方法不受與算術編碼相關的專利約束。正是基於這一點，才激起了人們尤其是開放源碼社區對於區間編碼的興趣。但是，人們經常認為區間編碼與算術編碼之間只有細微的區別，實際上二者是一樣的。關於這個問題，需要注意的是 G. Nigel N. Martin 在 1979 年的論文中定義為「區間編碼：去除數字信息中冗餘的算法（參見[1]（頁面存檔備份，存於網際網路檔案館））」的區間編碼儘管本質上與算術編碼相同，但是區間編碼經常使用基於Martin論文的特殊實現方法，根據Martin論文的年代，人們通常認為這些實現不受算術編碼相關的專利的約束。

區間編碼是如何工作的

區間編碼概念上要把所有的消息符號都編碼成一個數字，這與哈夫曼編碼為每個符號賦予一個位組合格式並且將所有這些位組合格式連接到一起不同。這樣區間編碼能夠實現比哈夫曼編碼一個符號一位這個上限還要高的壓縮率，並且它沒有哈夫曼編碼處理概率不為2的倍數時的效率問題。

區間編碼的核心概念是：對於給定的一個範圍足夠大的整數區間以及符號的概率估計，最初的區間很容易切分成與所表示的符號概率成比例的子區間。將當前區間切分成與下一個待編碼符號的概率對應的子區間，通過這種方法就可以對消息中的每個符號進行編碼。解碼器必須與編碼器有同樣的概率估計，這種概率估計可以事先發送過去、從已經發送的數據導出或者作為壓縮器或者解壓器的一部分。

當所有的符號已經編碼完成後，僅僅用子區間就可以表示整個信息（當然我們假定解碼器提取了整個消息之後通過某種方式得到）。單個的整數實際上已經足夠表示子區間，並且可能不需要傳輸整個的整數；如果有這樣一個數字序列，即每個整數的前綴都落在某個子區間，那麼前綴本身就已經足夠標識字區間並且傳輸消息。

例子

假設我們打算編碼消息「AABA<EOM>」，其中<EOM>是消息結束符。對於這個例子來說，假設編碼器知道我們打算用十進制數表示，也知道最初的區間是[0, 100000)並且頻率是{A: .60; B: .20; <EOM>: .20}，第一個符號將[0, 100000)分成三個子區間：

A:     [     0,  60000)
B:     [ 60000,  80000)
<EOM>: [ 80000, 100000)

由於第一符號是A，所以最初的區間縮減為[0, 60000)。第二個符號再次將這個區間分成三個子區間，跟在已經編碼的'A'後面表示：

AA:     [     0,  36000)
AB:     [ 36000,  48000)
A<EOM>: [ 48000,  60000)

兩個符號編碼之後，區間變成[000000, 036000)，第三個符號得到下面的結果：

AAA:     [     0,  21600)
AAB:     [ 21600,  28800)
AA<EOM>: [ 28800,  36000)

這一次第二段表示我們要編碼的消息，這樣區間就變成了[21600, 28800)。在這種情況下看起來確定子區間變得困難了一些，實際上並非如此：我們可以直接用上限減去下限得到7200，它最前面的4320區間是它的.60，後面的1440區間表示隨後的.20，剩餘的1440表示剩餘的.20，然後加上下限得到區間：

AABA:     [21600, 25920)
AABB:     [25920, 27360)
AAB<EOM>: [27360, 28800)

最後，區間縮小到[21600, 25920)，我們還有一個符號要進行編碼。與前面一樣我們區間進行切分得到：

AABAA:     [21600, 24192)
AABAB:     [24192, 25056)
AABA<EOM>: [25056, 25920)

由於<EOM>是最後一個符號，所以最後的區間就是[25056, 25920)。因為以「251」開頭的五位整數都落在最後的區間內，這樣任何一個三位前綴在這個範圍的整數都能夠明確地傳達原始信息。存在八個這樣的前綴這個事實暗示效率仍然不是最高的，這是由於我們使用十進制而不是二進制整數引起的。

這樣看起來主要問題就是我們要選擇一個足夠大的區間，這樣不管需要編碼多少符號我們都有足夠大的區間使得子區間不為0。但是，實際上這不是一個問題，因為編碼器不是從一個非常大的區間開始不斷減小這個區間，編碼器在任何時刻都只在一個更小的區間工作。在編碼一定數量的數位之後，最左面的數位不再變化。在這個例子中編碼三個符號之後，我們就已經知道結果將以「2」開始。隨著更多數位從右側進來，左側的數位將不斷發送出去。

與算術編碼的關係

算術編碼與區間編碼一模一樣，但是它用分數取代了整數。這些分數有一個隱含的公分母，這樣所有的分數都落在[0,1)區間。因此，算術編碼結果都解釋為以一個隱含的「0」開始。由於這是同樣的編碼方法的不同解釋，並且由於算術編碼與區間編碼的結果相同，所以算術編碼器都是與之對應的區間編碼器，反之亦然。換句話說就是，算術編碼與區間編碼是對於同一事物稍微不同的兩種理解方法。

但是，實際應用中區間編碼器傾向於使用Martin論文（參見[2]（頁面存檔備份，存於網際網路檔案館））中描述的實現方法，然而算術編碼通常也不叫作區間編碼。類似的區間編碼器經常提及的一個特性是每次正規化（renormalization）一個字節，而不是每次一位。換句話說，區間編碼傾向於使用字節而不是位作為編碼數碼。儘管這會稍微地減小壓縮的比率，但是比每次正規化一位的速度要快很多。

參見

外部連結