|
現(xiàn)在通用的大多數(shù)數(shù)據(jù)壓縮方法都屬于兩大陣營(yíng)之一：基于字典的方案和統(tǒng)計(jì)方法。 在小系統(tǒng)世界中，基于字典的數(shù)據(jù)壓縮技術(shù)此時(shí)似乎更加流行。不過，通過將算術(shù)編碼與強(qiáng)大的模型技術(shù)結(jié)合在一起，數(shù)據(jù)壓縮的統(tǒng)計(jì)方法可以真正達(dá)到更好的性能。這篇分成兩部分的文章討論了如何用幾個(gè)不同的模型方法與算術(shù)編碼組合以達(dá)到一些重大的壓縮率。本文的第一部分詳細(xì)說明算術(shù)編碼是如何工作的。第二部分說明如何開發(fā)一些可以使用算術(shù)編碼的有效模型以生成高性能壓縮程序。
鐘愛的術(shù)語
數(shù)據(jù)壓縮通常通過從輸入“文本”獲取“符號(hào)”、處理它們，并將“代碼”寫入到壓縮后的文件來進(jìn)行運(yùn)作。對(duì)于本文來說，符號(hào)通常是字節(jié)，但是他們很可能只是像素、80 位的浮點(diǎn)數(shù)或者 EBCDIC 字符。數(shù)據(jù)壓縮方案需要能夠?qū)⒁褖嚎s的文件轉(zhuǎn)換回到與輸入文本的一樣的拷貝才是有效的。如果已壓縮的文件比輸入文本更小，那么不必說，它也是有用的。
基于字典的壓縮系統(tǒng)通過用固定長(zhǎng)度碼來代替輸入文本中的一組符號(hào)來進(jìn)行運(yùn)作。字典技術(shù)的一個(gè)眾所周知的例子是 LZW 數(shù)據(jù)壓縮。（請(qǐng)參見 DDJ 的 89 年第 10 期中的“LZW 數(shù)據(jù)壓縮”一文）。LZW 通過通常從 9 到 16 位大小范圍的碼來取代本來無限長(zhǎng)的字符串來進(jìn)行運(yùn)作。
數(shù)據(jù)壓縮的統(tǒng)計(jì)方法采取一種完全不同的方法。它們通過一次編碼多個(gè)符號(hào)來運(yùn)作。將符號(hào)編碼到可變長(zhǎng)的輸出碼中。輸出碼的長(zhǎng)度根據(jù)符號(hào)的概率或者頻率進(jìn)行變化。低概率的符用較多的位進(jìn)行編碼，并且高概率符用較少的位進(jìn)行編碼。
實(shí)踐中，統(tǒng)計(jì)和字典方法之間的分界線并不總是那么清晰。一些方案并不能明顯地歸為某一個(gè)陣營(yíng)或者另一個(gè)，并且總是有一些使用來自兩種技術(shù)特性的混合方案。不過，在本文中討論的方法使用算術(shù)編碼來實(shí)現(xiàn)純粹的統(tǒng)計(jì)壓縮方案。
霍夫曼（Huffman）編碼：退役的冠軍
在數(shù)據(jù)流中只是能夠精確地計(jì)算字符的概率還不夠，我們也需要能有效地利用這個(gè)知識(shí)的編碼方法?；诟怕式y(tǒng)計(jì)的最著名的編碼方法可能是霍夫曼編碼。D.A.霍夫曼在 1952 年發(fā)表了一篇論文說明為已給定其概率的一組符號(hào)創(chuàng)建碼表的方法。當(dāng)使用固定長(zhǎng)度的編碼時(shí)，霍夫曼編碼表保證產(chǎn)生最低可能的輸出位來統(tǒng)計(jì)輸入流中可能的符號(hào)。霍夫曼稱這些“最小冗余編碼”，但是這個(gè)方案現(xiàn)在統(tǒng)稱為霍夫曼編碼。其它固定長(zhǎng)度編碼系統(tǒng)，如香農(nóng)-范諾（Shannon-Fano）編碼，通過霍夫曼證明不是最理想的。
霍夫曼編碼為每個(gè)符號(hào)指定一個(gè)輸出碼，輸出碼可以 1 位這么短，也可以比輸入符號(hào)長(zhǎng)得多，嚴(yán)格取決于它們的概率。用于每個(gè)符號(hào)的優(yōu)化位數(shù)是以 2 為底，（1/p）的對(duì)數(shù)，這里 p 是指定字符的概率。因此，例如，如果可以在隨機(jī)字節(jié)流中找到的字符概率是 1/256，每個(gè)字符的最佳位數(shù)是以 2 為底的 256 的對(duì)數(shù)，或者 8。如果概率上升到 1/2，編碼字符所需要的最佳位數(shù)將降為 1。
這個(gè)方案放到現(xiàn)實(shí)中時(shí)的問題是霍夫曼編碼的位長(zhǎng)度必須是整數(shù)。例如，如果字符的概率是 1/3，編碼這個(gè)字符的最佳位數(shù)是大約 1.6?；舴蚵幋a方案必須要么指定 1 位，要么指定 2 位給編碼，并且任何一種選擇都導(dǎo)致可能比理論更長(zhǎng)的壓縮消息。
當(dāng)字符的概率變得很高時(shí)，這個(gè)非最佳編碼也變成值得注意的問題。如果能開發(fā)一種可以為給定的字符指定 90% 的概率的統(tǒng)計(jì)方法的話，最佳編碼碼大小將是 0.15 個(gè)比特位?；舴蚵幋a系統(tǒng)只可能給符號(hào)指定一個(gè) 1 位的碼，這要比必需的碼位長(zhǎng) 6 倍。
自適應(yīng)方案
當(dāng)嘗試進(jìn)行自適應(yīng)數(shù)據(jù)壓縮時(shí)產(chǎn)生的霍夫曼編碼的第二個(gè)問題。當(dāng)進(jìn)行非自適應(yīng)數(shù)據(jù)壓縮時(shí)，壓縮程序單程掃描一遍數(shù)據(jù)來收集統(tǒng)計(jì)信息。然后使用在整個(gè)編碼過程中都不能改變的統(tǒng)計(jì)信息來編碼數(shù)據(jù)。
解碼程序?yàn)榱私獯a已壓縮的數(shù)據(jù)流，它首先需要一個(gè)統(tǒng)計(jì)信息的副本。編碼程序一般情況下將預(yù)先考慮的統(tǒng)計(jì)表放入已壓縮的消息中，以使解碼程序可以在開始之前讀入統(tǒng)計(jì)表。這顯然給消息增加了一定量的負(fù)擔(dān)。
當(dāng)使用很簡(jiǎn)單的統(tǒng)計(jì)模型壓縮數(shù)據(jù)時(shí)，編碼表趨于更小。例如，每個(gè)字符的頻率計(jì)數(shù)能以相當(dāng)高的精確性存儲(chǔ)在差不多 256 個(gè)字節(jié)大小的空間中。它并不會(huì)給除真正最小的消息之外的其它任何消息增加明顯的長(zhǎng)度。不過，為了獲得更好的壓縮率，統(tǒng)計(jì)模型在大小上有必要的增加。如果消息的統(tǒng)計(jì)變得太大，在壓縮率中的任何改進(jìn)被將需要預(yù)先放入已編碼消息中的統(tǒng)計(jì)而增加的長(zhǎng)度抵消了。
為了回避這個(gè)問題，提出了自適應(yīng)數(shù)據(jù)壓縮。在自適應(yīng)數(shù)據(jù)壓縮中，編碼程序和解碼程序都以其處于相同狀態(tài)的統(tǒng)計(jì)模型開始。兩者中的每一個(gè)一次處理單個(gè)字符，并在字符讀入后更新統(tǒng)計(jì)模型。這非常類似于大多數(shù)像 LZW 編碼這樣基于字典方案的工作。以非最佳模型開始的消息會(huì)有少量的效率損失，但是它經(jīng)常通過不必隨消息傳送任何統(tǒng)計(jì)信息而得到更好的彌補(bǔ)。
將自適應(yīng)模型與霍夫曼編碼結(jié)合起來的問題是重建霍夫曼樹是一個(gè)非常昂貴的過程。為了讓自適應(yīng)方案高效，有必要在每一個(gè)字符出現(xiàn)之后調(diào)整霍夫曼編碼。直到霍夫曼編碼第一次開發(fā)的 20 年之后，執(zhí)行自適應(yīng)霍夫曼編碼的算法都沒有發(fā)布。即使在現(xiàn)在，最好的自適應(yīng)霍夫曼編碼算法仍然相當(dāng)耗時(shí)間和金錢。
算術(shù)編碼（Arithmetic Coding）：它如何工作
一個(gè)替代霍夫曼編碼的可觀候選方案已在僅近十年得到證實(shí)：算術(shù)編碼（Arithmetic Coding）。算術(shù)編碼完全放棄了用指定的編碼取代輸入符號(hào)的主張。取而代之的是，它接受輸入符號(hào)流并用單個(gè)浮點(diǎn)輸出數(shù)來代替它。消息越長(zhǎng)（并且越復(fù)雜），在輸出數(shù)中就需要越多的位。直到最近仍然沒有發(fā)現(xiàn)在計(jì)算機(jī)上用固定大小的寄存器來實(shí)現(xiàn)這一思想的實(shí)踐方法。
算術(shù)編碼過程產(chǎn)生的輸出是單個(gè)小于 1 并大于等于 0 的數(shù)。這個(gè)單個(gè)的數(shù)可以唯一地解碼以創(chuàng)建參與其構(gòu)造的精確字符流。為了構(gòu)造輸出數(shù)，符號(hào)的編碼必須有一組指定給它們的概率。例如，如果我要編碼隨機(jī)消息“BILL GATES”，我會(huì)得到看起來如下的概率分布：
Character Probability
-------------- --------------
SPACE 1/10
A 1/10
B 1/10
E 1/10
G 1/10
I 1/10
L 2/10
S 1/10
T 1/10
一旦知道了字符的概率，需要按“概率線”為單個(gè)符號(hào)指定一個(gè)范圍，這個(gè)“概率線”名義上是從 0 到 1。為哪個(gè)字符指定哪一段范圍并不麻煩，只要編碼程序和解碼程序都采用相同的方式來指定范圍。我們?cè)谶@里使用的這一組九個(gè)字符符號(hào)將看起來如下：
Character Probability Range
--------------- ---------------- ----------------
SPACE 1/10 0.00 - 0.10
A 1/10 0.10 - 0.20
B 1/10 0.20 - 0.30
E 1/10 0.30 - 0.40
G 1/10 0.40 - 0.50
I 1/10 0.50 - 0.60
L 2/10 0.60 - 0.80
S 1/10 0.80 - 0.90
T 1/10 0.90 - 1.00
在 0 - 1 范圍內(nèi)為每一個(gè)字符指定一個(gè)與其出現(xiàn)的概率對(duì)應(yīng)的的片斷。當(dāng)編碼消息“BILL GATES”時(shí)，第一個(gè)符號(hào)是“B”。要正確編碼第一個(gè)字符，最終編碼后的消息必須是大于或者等于 0.20 并小于 0.30 的一個(gè)數(shù)。要編碼這個(gè)數(shù)，我們所要做的是明了這個(gè)數(shù)會(huì)落入的范圍。因此，在編碼完第一個(gè)字符后，這個(gè)范圍的最底端是 0.20，并且范圍的最頂端是 0.30。
在編碼完第一個(gè)字符之后，我們知道對(duì)于我們的輸出數(shù)來說我們的范圍現(xiàn)在就以這個(gè)底數(shù)和這個(gè)頂數(shù)為邊界。在剩余的編碼過程期間發(fā)生的事情是每一個(gè)要編碼的新符號(hào)將更進(jìn)一步地限制輸出數(shù)的可能范圍。下一個(gè)要編碼的字符，“I”，擁有范圍 0.50 到 0.60。如果它是我們消息中的第一個(gè)數(shù)，我們可以直接將我們的底和頂?shù)姆秶O(shè)為這兩個(gè)值。但是“I”是第二個(gè)數(shù)。因此我們不能直接設(shè)定，而是應(yīng)該說“I”在 0.2 - 0.3 的子范圍中擁有與 0.50 - 0.60 對(duì)應(yīng)的范圍。這意味著新編碼的數(shù)將必然落入當(dāng)前已建立范圍的第 50 至第 60 個(gè)百分點(diǎn)之間的位置。按照這個(gè)邏輯將我們的數(shù)進(jìn)一步限制到 0.25 至 0.26 之間的范圍。
對(duì)任意長(zhǎng)度的消息按照這種思路完成編碼的算法說明如下：
Set low to 0.0
Set high to 1.0
While there are still input symbols do
get an input symbol
code_range = high - low.
high = low + range*high_range(symbol)
low = low + range*low_range(symbol)
End of While
output low
按照這個(gè)流程可以得出對(duì)我們所選擇的消息的自然而簡(jiǎn)單的總結(jié)，看起來如下：
New Character Low Value High Value
-------------------- --------------- ---------------
0.0 1.0
B 0.2 0.3
I 0.25 0.26
L 0.256 0.258
L 0.2572 0.2576
SPACE 0.25720 0.25724
G 0.257216 0.257220
A 0.2572164 0.2572168
T 0.25721676 0.2572168
E 0.257216772 0.257216776
S 0.2572167752 0.2572167756
因此最終的底值，0.2572167752 將使用我們介紹的編碼方案唯一編碼消息“BILL GATES”。
有了這個(gè)編碼方案，明白解碼過程如何運(yùn)作相對(duì)比較容易。我們通過看哪一個(gè)符號(hào)擁有我們已編碼消息所落在的碼空間來查找到第一個(gè)符號(hào)。因?yàn)閿?shù) 0.2572167752 落在 0.2 和 0.3 之間，我們知道第一個(gè)字符必然是“B”。然后我們需要將“B”從已編碼的數(shù)中移除。因?yàn)槲覀冎?B 的底和頂范圍，我們可以用與將它們放入過程相反的過程來消除它們的影響。首先，我們從數(shù)中減去 B 的底值，得到 0.0572167752，然后我們除以 B 的范圍，即 0.1。所得的值為 0.572167752。然后我們可以計(jì)算出在哪里停止，這個(gè)停止的位置正是在下一個(gè)字母“I”的范圍之內(nèi)。
解碼輸入數(shù)的算法看上去如下：
get encoded number
Do
find symbol whose range straddles the encoded number
output the symbol
range = symbol low value - symbol high value
subtract symbol low value from encoded number
divide encoded number by range
until no more symbols
注意我為了方便起見忽略了判斷什么時(shí)候才沒有更多的符號(hào)需要解碼的問題?？梢酝ㄟ^將一個(gè)特殊 EOF 符號(hào)編碼進(jìn)消息，也可以隨已編碼的消息一同傳送流的長(zhǎng)度來解決這個(gè)問題。
“BILL GATES”消息的解碼算法的處理過程如下：
Encoded Number Output Symbol Low High Range
----------------------- -------------------- ------ ------ ---------
0.2572167752 B 0.2 0.3 0.1
0.5721677752 I 0.5 0.6 0.1
0.72167752 L 0.6 0.8 0.2
0.6083876 L 0.6 0.8 0.2
0.041938 SPACE 0.0 0.1 0.1
0.41938 G 0.4 0.5 0.1
0.1938 A 0.2 0.3 0.1
0.938 T 0.9 1.0 0.1
0.38 E 0.3 0.4 0.1
0.8 S 0.8 0.9 0.1
0.0
概括來說，編碼過程就是一個(gè)簡(jiǎn)單地使用每一個(gè)新的符號(hào)來收縮數(shù)的可能范圍這樣一個(gè)過程。新的范圍與附加給這個(gè)符號(hào)的預(yù)先定義的概率成比例。解碼是逆向過程，其中展開的范圍與抽取出的每一個(gè)字符的概率成比例。
實(shí)踐中的問題
使用算術(shù)編碼編/解碼符號(hào)流不是太復(fù)雜。但是初看上去，它似乎完全無法實(shí)現(xiàn)。大多數(shù)計(jì)算機(jī)最多支持的 80 位或差不多的浮點(diǎn)數(shù)。這是不是就意味著你必須在每次完成 10 到 15 個(gè)符號(hào)以后重新開始？你需要浮點(diǎn)處理器？不同浮點(diǎn)格式的機(jī)器可以使用算術(shù)編碼來通信嗎？
如它所展現(xiàn)的，算術(shù)編碼最好使用標(biāo)準(zhǔn) 16 位和 32 位整數(shù)來完成。不必非要要求浮點(diǎn)數(shù)，也不必要求其幫助才能使用算術(shù)編碼。代替浮點(diǎn)的方法是增量轉(zhuǎn)換方案，在方案中，聲明為定點(diǎn)整數(shù)的變量接收在底端的新位，并將這些位轉(zhuǎn)移到頂端，最終形成一個(gè)大的單數(shù)，這個(gè)數(shù)的位只取決于計(jì)算機(jī)的存儲(chǔ)媒介，媒介能存儲(chǔ)多長(zhǎng)，這個(gè)數(shù)就有多大。
在前面的部分，我通過明了括起可能輸出數(shù)的范圍的頂端數(shù)和底端數(shù)，來說明算法如何工作。當(dāng)算法第一次啟動(dòng)時(shí)，底端數(shù)設(shè)為 0.0，并且頂端數(shù)設(shè)為 1.0。使用整數(shù)首先進(jìn)行的簡(jiǎn)化是以二進(jìn)制的形式改變 1.0 至 0.999......，或者.111......。
為了在整數(shù)寄存器中存儲(chǔ)這些數(shù)，我們首先調(diào)整它們，以讓上面這個(gè)隱含的小數(shù)點(diǎn)是在詞的左邊。然后我們載入與適合我們要處理的單詞所需要大小差不多一樣的初始頂值和底值。我的實(shí)現(xiàn)使用 16 位無符號(hào)數(shù)，因此初始的頂值是 0xFFFF，并且底值是 0。我們知道頂值從 FF 開始無限增長(zhǎng)，并且底值從零開始無限增長(zhǎng)，因此我們可以在需要這些剩余位（也就是最后兩位（在 0x00 與 0xFF 之間））時(shí)我們無需再附加頂值和底值，而是直接將它們轉(zhuǎn)移出來。
如果你想像我們的“BILL GATES”例子在一個(gè)具有 5 個(gè)數(shù)的寄存器中，我們?cè)O(shè)置與上述相當(dāng)?shù)倪@個(gè)數(shù)看起來應(yīng)當(dāng)如下：
頂值：99999
底值：00000
為了找到我們新的范圍數(shù)，我們需要應(yīng)用前面部分說明的編碼算法。我們首先需要計(jì)算底值和頂值之間的范圍。兩個(gè)寄存器之間的差值將是 100000，而不是 99999。這是因?yàn)槲覀兗僭O(shè)有無窮多個(gè)的 9（實(shí)際上只受限于我們要處理的單詞數(shù)量） 被加到了存儲(chǔ)頂值的寄存器上，因此我們需要增加計(jì)算出來的差值。那么我們使用來自前面部分的方程來計(jì)算新的頂值：
high = low + high_range(symbol)
在這種情況下頂值范圍是 .30，這個(gè)范圍給出了一個(gè)新的頂值 30000。存儲(chǔ)新的頂值之前，我們需要先將它減 1，再次強(qiáng)調(diào)，因?yàn)橛心莻€(gè)隱藏的數(shù)字加到了整數(shù)值上。因此，新的頂值是 29999。
底端數(shù)的計(jì)算遵循相同的方法，結(jié)果得到新值為 20000。因此，現(xiàn)在頂值和底值看起來如下：
頂端值： 29999 (999...)
底端值： 20000 (000...)
從這一點(diǎn)來說，頂端和底端的最高位的數(shù)字應(yīng)該匹配。因?yàn)槲覀兊乃惴ū举|(zhì)，頂端和底端可以繼續(xù)增長(zhǎng)接近至另一個(gè)完全沒有匹配過的數(shù)。這意味著一旦它們?cè)谧罡呶坏臄?shù)字上匹配時(shí)，這個(gè)數(shù)字就不再改變。 因此，我們現(xiàn)在可以輸出這個(gè)數(shù)字作為我們編碼數(shù)的第一個(gè)數(shù)字。這可以通過將頂端和底端向左移動(dòng)一個(gè)數(shù)字來完成，并且在頂端的最低位數(shù)字后移入一個(gè) 9 進(jìn)來。在這個(gè)算法的 C 實(shí)現(xiàn)中是以二進(jìn)制的形式執(zhí)行相當(dāng)?shù)牟僮鳌?/div>
隨著這個(gè)過程的進(jìn)行，頂端和底端繼續(xù)向著接近碰頭的方向增長(zhǎng)，然后將轉(zhuǎn)移出的數(shù)字編碼進(jìn)單詞中。我們的“BILL GATES”消息的過程看起來如下：
HIGH LOW RANGE CUMULATIVE OUTPUT
Initial state 99999 00000 100000
Encode B (0.2 - 0.3) 29999 20000
Shift out 2 99999 00000 100000 .2
Encode I (0.5 - 0.6) 59999 50000 .2
Shift out 5 99999 00000 100000 .25
Encode L (0.6 - 0.8) 79999 60000 20000 .25
Encode L (0.6 - 0.8) 75999 72000 .25
Shift out 7 59999 20000 40000 .257
Encode SPACE (0.0 - 0.1) 23999 20000 .257
Shift out 2 39999 00000 40000 .2572
Encode G (0.4 - 0.5) 19999 16000 .2572
Shift out 1 99999 60000 40000 .25721
Encode A (0.1 - 0.2) 67999 64000 .25721
Shift out 6 79999 40000 40000 .257216
Encode T (0.9 - 1.0) 79999 76000 .257216
Shift out 7 99999 60000 40000 .2572167
Encode E (0.3 - 0.4) 75999 72000 .2572167
Shift out 7 59999 20000 40000 .25721677
Encode S (0.8 - 0.9) 55999 52000 .25721677
Shift out 5 59999 20000 .257216775
Shift out 2 .2572167752
Shift out 0 .25721677520
注意，在所有的字母都解決完后，兩個(gè)額外的數(shù)字需要轉(zhuǎn)移出頂端值或者底端值來結(jié)束輸出單詞。
復(fù)雜性
這個(gè)方案對(duì)于增量編碼一條消息來說非常適合。在使用雙精度整數(shù)計(jì)算以確保消息可以精確地編碼的期間，精確度是有保證的。不過，在某些情形下，精確度會(huì)有一定潛在的損失。
如果已編碼的詞其中有 0 個(gè)或 9 個(gè)字符串，頂端值和底端值將慢慢地會(huì)聚到一個(gè)值，但是可能不是立即看它們的最高位數(shù)字的匹配。例如，頂值和底值可能看起來如下：
High: 700004
Low: 699995
此時(shí)，計(jì)算的范圍的長(zhǎng)度將只是一個(gè)單個(gè)數(shù)字，這意味我們會(huì)沒有足夠的精度來精確地編碼這個(gè)輸出詞。甚至更糟，在幾次更多的迭代后，頂端數(shù)和底端數(shù)可能會(huì)看起來如下：
High: 70000
Low: 69999
此時(shí)，這兩個(gè)值永遠(yuǎn)也粘不到一塊了。頂端值和底端值變得如此小，以至于任何計(jì)算總是返回相同的值。但是，因?yàn)閮蓚€(gè)詞的最高位的數(shù)字并不相等，算法并不能輸出數(shù)字并進(jìn)行轉(zhuǎn)移。它似乎更像是一個(gè)僵局。
戰(zhàn)勝這個(gè)下溢問題的辦法是防止事情變得這么糟。最初的算法說過一些像“如果頂值和底值的最高位的數(shù)字匹配的話，將它轉(zhuǎn)移出來”這樣的事情。如果兩個(gè)數(shù)字不匹配，而它們現(xiàn)在是很鄰近的數(shù)，就需要應(yīng)用第二次測(cè)試。如果頂端數(shù)和底端數(shù)還是分開的（也就是還沒有碰上），那么我們測(cè)試看頂端中第二高位的數(shù)字是否是 0，以及底端第二高位的數(shù)字是否是 9。如果是，它意味著我們正在接近下溢，并且需要采取行動(dòng)。
當(dāng)下溢出現(xiàn)，我們采用一個(gè)些微轉(zhuǎn)移操作來阻止它。不是將最高位的數(shù)字轉(zhuǎn)移出這個(gè)詞，而是從頂端值和底端值中刪除第二高位的數(shù)字，并將剩余的數(shù)字左移以填充空白。最高位的數(shù)字仍留在原位。然后我們需要調(diào)置一個(gè)下溢計(jì)數(shù)器來記住我們?nèi)拥袅艘粋€(gè)數(shù)字，并且我們不能完全確信它是否就會(huì)是以 0 或者 9 結(jié)束。操作看起來如下：
Before After
--------- --------
High: 40344 43449
Low: 39810 38100
Underflow: 0 1
在每一次重新計(jì)算操作之后，如果最高位的數(shù)字并不能匹配上，我們可以再次檢查下溢數(shù)字。如果下溢仍然出現(xiàn)，我們將它們轉(zhuǎn)移出來并增加計(jì)算機(jī)器。
當(dāng)最高位的數(shù)字最終會(huì)聚到一個(gè)單數(shù)值時(shí)，我們首先輸出這個(gè)值。然后，我們輸出所有在前面丟棄的“下溢”數(shù)字。下溢數(shù)字將全部是 9 或者全部是 0，取決于頂端數(shù)和底端數(shù)是否會(huì)聚到一個(gè)較高的值還是一個(gè)較低的值。在這個(gè)算法的 C 實(shí)現(xiàn)中，下溢計(jì)數(shù)明了輸出了多少個(gè) 9 或者 0。
解碼
在“理想的”解碼過程中，我們使用整個(gè)輸入數(shù)進(jìn)行工作。因此算法要求我們做一些像“通過符號(hào)概率劃分已編碼的數(shù)”。在實(shí)踐中，我們不能在一個(gè)可能有十億個(gè)字節(jié)那么長(zhǎng)的數(shù)上執(zhí)行操作。正如編碼過程，解確程序通過將 16 和 32 位整數(shù)用于計(jì)算來運(yùn)作。
取代維護(hù)兩個(gè)數(shù)，頂端數(shù)和底端數(shù)，解碼程序必須維護(hù) 3 個(gè)整數(shù)。前兩個(gè)是頂端數(shù)，嚴(yán)格對(duì)應(yīng)到由編碼程序維護(hù)的頂端數(shù)和底端數(shù)。第三個(gè)數(shù)，編碼，包含正在從輸入位流中讀入的當(dāng)前的位。編碼值將總是處于頂端值和底端值之間。像它們?cè)絹碓浇咏粯樱瑢l(fā)生新的轉(zhuǎn)移操作，并且頂端數(shù)和底端數(shù)將從編碼退出。
在解碼程序中，頂端值和底端值嚴(yán)格對(duì)應(yīng)于編碼程序所使用的頂端值和底端值。這兩個(gè)值正如它們?cè)诰幋a程序中一樣，在每一個(gè)符號(hào)之后都將被更新，并且應(yīng)該有精確的相同值。通過在頂端數(shù)和底端數(shù)的第一個(gè)的數(shù)字上執(zhí)行相同的比較測(cè)試，解碼程序知道何時(shí)是將一個(gè)新的數(shù)字轉(zhuǎn)移到輸入編碼中的時(shí)間。也與編碼程序步調(diào)一致，執(zhí)行相同的下溢測(cè)試。
在理想的算法中，通過查找其概率接近編碼的當(dāng)前值的符號(hào)來判斷當(dāng)前已編碼的符號(hào)是什么是可行的。在整數(shù)算法中，事情些微更復(fù)雜一些。在這種情況下，概率縮放因子由頂端數(shù)和底端數(shù)之間的差來決定。因此將使用兩個(gè) 16 位的正整數(shù)之間來計(jì)算范圍，來代替 0.1 和 1.0 之間的范圍計(jì)算。當(dāng)前的概率由落入這個(gè)范圍的當(dāng)前編碼所決定。如果你用（high-low+1）除（value-low），你會(huì)得到當(dāng)前符號(hào)的實(shí)際概率。
哪兒有牛肉？
到目前為止，這個(gè)編碼過程可能看起來很有意思，但是為什么說它在霍夫曼編碼的基礎(chǔ)上有所改進(jìn)，看起來并不顯然。當(dāng)我們測(cè)試一個(gè)概率有一點(diǎn)不同的案例時(shí)，答案就變得很清晰了。讓我們測(cè)試一個(gè)我們必須編碼流“AAAAAAA”的案例，并且“A”的概率已知是 0.90。這意味著任何輸入字符有 90% 的機(jī)會(huì)是字母“A”。我們建立起我們的概率表，以使字母“A”占有范圍 0.0 到 0.9，并且消息符號(hào)的結(jié)束占有 0.9 到 1.0 的范圍。那么編碼過程看起來如下：
New Character Low value High value
-------------------- -------------- --------------
0.0 1.0
A 0.0 0.9
A 0.0 0.81
A 0.0 0.729
A 0.0 0.6561
A 0.0 0.59049
A 0.0 0.531441
A 0.0 0.4782969
END 0.43046721 0.4782969
現(xiàn)在我們知道底端值和頂端值是什么，剩下的所有事情就是拿一個(gè)數(shù)來編碼這個(gè)消息。數(shù)“0.45”將可以使這條消息唯一解碼成“AAAAAAA”。這兩個(gè)數(shù)字用了比 7 位還些微少點(diǎn)空間來定義，這意味著我們用少于 8 位的空間編碼了 8 個(gè)符號(hào)。最佳的霍夫曼使用這個(gè)方案來編碼上面的消息最少也要 9 位。
進(jìn)一步延伸這個(gè)觀點(diǎn)，我設(shè)置一個(gè)只定義了兩個(gè)符號(hào)的測(cè)試。字節(jié)值“0”有 16382/16383 的概率，并且 EOF 符號(hào)有 1/16383 的出現(xiàn)概率。然后我創(chuàng)建一個(gè)測(cè)試文件其中填上一百萬（100,000）個(gè)“0”。使用這個(gè)模型壓縮之后，輸出文件只有 3 個(gè)字節(jié)長(zhǎng)！使用霍夫曼編碼的最小的長(zhǎng)度也有 12,501 個(gè)字節(jié)。這顯然是一個(gè)人為的例子，但是它論證了當(dāng)符號(hào)的概率正確的時(shí)候，算術(shù)編碼能夠
以比每個(gè)字節(jié)只占 1 位還好的比率壓縮數(shù)據(jù)。
編碼
一個(gè)用 C 編寫的編碼過程放在列表1 和 2 中。它包含兩個(gè)部分，一個(gè)初始化過程，和編碼程序本身。用于編碼程序以及解碼程序的編碼第一次由 IanH.Witten、Radford Neal 和 John Cleary 發(fā)表在“Communication of the ACM”的 1987 年 2 月期的一篇名為“Arithmetic Coding for Data Compression”的論文中，并且經(jīng)過作者的允許在此公開。我稍微修改了這個(gè)編碼以使程序的建模部分和編碼部分進(jìn)一步地隔離開。
先前說明的兩個(gè)算法之間有兩個(gè)主要的差異以及代碼入在列表 1-2。第一個(gè)不同是在轉(zhuǎn)換概率的方法中。在上面說明的算法中，概率保持為一對(duì)范圍為 0.0 至 1.0 的浮點(diǎn)數(shù)。每一個(gè)符號(hào)有其自己的范圍部分。在我們?cè)谶@里說明的程序中，符號(hào)有稍微不同的定義。符號(hào)的范圍定義為兩個(gè)經(jīng)過縮放因子計(jì)算得出的整數(shù)而不是兩個(gè)浮點(diǎn)數(shù)。這個(gè)縮放因子也作為符號(hào)定義的一部分包括其中。因此，對(duì)于“BILL GATES”的例子，字母 L 在前面定義為一對(duì)值為 0.60 和 0.80 的頂/底端數(shù)。在此處使用的編碼中，用值為 10 的確良符號(hào)縮放因子，計(jì)算出底和頂端數(shù)分別為 6 和 8 來定義“B”。采用這種方法來完成定義的原因是因?yàn)樗诮＿@種類型的數(shù)據(jù)時(shí)，能很好地與我們保持統(tǒng)計(jì)的辦法相適應(yīng)。這兩種方法是相當(dāng)?shù)?，只是保持用整?shù)進(jìn)行運(yùn)算減少了許多需要完成的工作。注意字符實(shí)際上一直擁有范圍，但不包括頂端值。
在這個(gè)算法中的第二個(gè)不同之處是所有比較和轉(zhuǎn)移操作都是以二進(jìn)制的形式完成的，而不是十進(jìn)制。前面給出的說明是基于十進(jìn)制數(shù)字進(jìn)行的，以使算法更好理解一點(diǎn)。算法在十進(jìn)制下可以正常工作，但是在大多數(shù)計(jì)算機(jī)上進(jìn)行十進(jìn)制數(shù)的屏蔽數(shù)字和移位很困難。因此我們現(xiàn)在比較最開始的兩個(gè)位，而不是比較最開始的兩個(gè)數(shù)字。
我們丟失了為了使用編碼和解碼算法所需要的兩件事情。第一件是一組面向位的輸入和輸出程序。這放在了列表 3 和 4 中，并且在代碼中沒有注釋。建模代碼負(fù)責(zé)跟蹤每一個(gè)字符的概率，并執(zhí)行兩個(gè)不同的轉(zhuǎn)換。在編碼過程期間，建模代碼取將要被編碼的字符并將其轉(zhuǎn)換成概率范圍。概率范圍定義為一個(gè)底數(shù)、一個(gè)頂數(shù)和一個(gè)總范圍。在解碼過程期間，建模代碼必須取一個(gè)來自輸入位流的計(jì)數(shù)并將其轉(zhuǎn)換成一個(gè)字符進(jìn)行輸出。
測(cè)試代碼
一個(gè)短的測(cè)試程序放在列表 3 中。它實(shí)現(xiàn)一個(gè)使用前面討論的“BILL GATES”模型的壓縮/展開程序。在幾個(gè)需要判斷的地方加入了打印語句以讓你準(zhǔn)確地跟蹤在這個(gè)程序中進(jìn)行的處理。
BILL.C 有其自己非常簡(jiǎn)單的模型單元，這個(gè)模型對(duì)每一個(gè)消息中可能的字母都有一組因定的概率。我加入了一個(gè)新字符，即空字符串結(jié)束符，以知道何時(shí)停止解碼這條消息。
BILL.C 編碼一個(gè)隨便定義的輸入字符串，并將其寫出到一個(gè)叫作 TEST.CMP 的文件中。然后它解碼這條消息將其打印在屏幕上進(jìn)行驗(yàn)證。在 BILL.C 中有幾個(gè)仍然沒有討論過的建模函數(shù)。在編碼過程期間，調(diào)用了一個(gè)稱為 convert_int_to_symbol 程序。這個(gè)程序獲取一個(gè)給定的輸入字符，并將其轉(zhuǎn)換成一個(gè)底值、頂值和用在此模型中的縮放因子。因?yàn)槲覀冇糜?BILL.C 的模型是一組固定的概率，這就意味著在這個(gè)表中查詢概率。這些一旦定義完畢，就可以調(diào)用編碼程序。
在解碼過程期間，有兩個(gè)與建模有關(guān)的函數(shù)。為了決定輸入流中什么字符正在等待被解碼，模型需要詢問模型來判斷當(dāng)前的縮放因子是多少。在我們的例子中，縮放因子（或者是計(jì)算范圍）是固定在 11，因?yàn)樵谖覀兊哪Ｐ椭锌偸怯?11 次計(jì)算。這個(gè)數(shù)被傳送給解碼程序，并且它為使用這個(gè)縮放因子的給定符號(hào)返回一個(gè)計(jì)數(shù)。然后，調(diào)用一個(gè)稱為 convert_symbol_to_int 的建模函數(shù)調(diào)用。它獲取給定的這個(gè)計(jì)數(shù)，并判斷什么字符與這個(gè)計(jì)數(shù)相匹配。最終，再次調(diào)用解碼程序來解出輸入流中的那個(gè)字符。
下一次
一旦你成功地理解了如何使用算術(shù)編碼來編碼/解碼符號(hào)，那么你可以開始嘗試創(chuàng)建將具有超級(jí)壓縮性能的模型。下一個(gè)月的總結(jié)文章討論一些你可以嘗試的自適應(yīng)壓縮方法。一個(gè)相當(dāng)簡(jiǎn)單的統(tǒng)計(jì)模型程序能夠提供超過備受尊敬的程序，如 PKZIP 或者 COMPRESS 的壓縮。
參考資源
如我在前面提到，在 1987 年 7 月的 “Communication of the ACM”（ACM 通信）提供權(quán)威的算術(shù)編碼的概論。這篇文章的大部分在由 Timothy C.Bell、John G. Cleary 和 Ian H.Witten 所著的“Text Compression”（文本壓縮）一書中重印。這本書為基于統(tǒng)計(jì)和基于字典的壓縮兩種技術(shù)提供了出色的概論。另一本好書是由 James Storer 所著的“Data Compression”（數(shù)據(jù)壓縮）。
Bell, Timothy C., Cleary, John G., Witten, Ian H,(1990) "Text Compression",Prentice Hall, Englewood NJ
Nelson, Mark(1989) "LZW Data Compression", Doctor Dobb's Journal, October, pp 29-37
Storer, J.A.,(1988) "Data Compression", Computer Science Press, Rockville, MD
Witten, Ian H., Neal, Radford M., and Cleary, John G.(1987)"Arithmetic Coding for Data Compression", Communications of the ACM, June, pp 520-540.
|
|
|
