向極限挑戰：算術編碼

(轉) http://blog.csdn.net/hhf383530895/archive/2009/08/24/4478605.aspx

我們在上一章中已經明白，Huffman 編碼使用整數個二進制位對符號進行編碼，這種方法在許多情況下無法得到最優的壓縮 效果。假設某個字符的出現概率為 80%，該字符事實上只需要 -log2 (0.8) = 0.322 位編碼，但 Huffman 編碼一定會為其分配一位 0 或一位 1 的編碼。可以想象，整個信息的 80% 在壓縮后都幾乎相當于理想長度的 3 倍左右，壓縮效果可想而知。

難道真的能只輸出 0.322 個 0 或 0.322 個 1 嗎？是用剪刀把計算機 存儲 器中的二進制位剪開嗎？計算機真有這樣的特異功能嗎？慢著慢著，我們不要被表面現象所迷惑，其實，在這一問題上，我們只要換一換腦筋，從另一個角度……哎呀，還是想不通，怎么能是半個呢？好了，不用費心了，數學家們也不過是在十幾年前才想到了算術編碼這種神奇的方法，還是讓我們虛心地研究一下他們究竟是從哪個角度找到突破口的吧。

輸出：一個小數

更神奇的事情發生了，算術編碼對整條信息（無論信息有多么長），其輸出僅僅是一個數，而且是一個介于 0 和 1 之間的二進制小數。例如算術編碼對某條信息的輸出為 1010001111，那么它表示小數 0.1010001111，也即十進制數 0.64。

咦？怎么一會兒是表示半個二進制位，一會兒又是輸出一個小數，算術編碼怎么這么古怪呀？不要著急，我們借助下面一個簡單的例子來闡釋算術編碼的基本原理。為了表示上的清晰，我們暫時使用十進制表示算法中出現的小數，這絲毫不會影響算法的可行性。

考慮某條信息中可能出現的字符僅有 a b c 三種，我們要壓縮保存的信息為 bccb。

在沒有開始壓縮進程之前，假設我們對 a b c 三者在信息中的出現概率一無所知（我們采用的是自適應模型），沒辦法，我們暫時認為三者的出現概率相等，也就是都為 1/3，我們將 0 - 1 區間按照概率的比例分配給三個字符，即 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現在我們拿到第一個字符 b，讓我們把目光投向 b 對應的區間 0.3333 - 0.6667。這時由于多了字符 b，三個字符的概率分布變成：Pa = 1/4，Pb = 2/4，Pc = 1/4。好，讓我們按照新的概率分布比例劃分 0.3333 - 0.6667 這一區間，劃分的結果可以用圖形表示為：

+-- 0.6667 Pc = 1/4 | +-- 0.5834 | | Pb = 2/4 | | | +-- 0.4167 Pa = 1/4 | +-- 0.3333

接著我們拿到字符 c，我們現在要關注上一步中得到的 c 的區間 0.5834 - 0.6667。新添了 c 以后，三個字符的概率分布變成 Pa = 1/5，Pb = 2/5，Pc = 2/5。我們用這個概率分布劃分區間 0.5834 - 0.6667：

+-- 0.6667 | Pc = 2/5 | | +-- 0.6334 | Pb = 2/5 | | +-- 0.6001 Pa = 1/5 | +-- 0.5834

現在輸入下一個字符 c，三個字符的概率分布為：Pa = 1/6，Pb = 2/6，Pc = 3/6。我們來劃分 c 的區間 0.6334 - 0.6667：

+-- 0.6667 | | Pc = 3/6 | | | +-- 0.6501 | Pb = 2/6 | | +-- 0.6390 Pa = 1/6 | +-- 0.6334

輸入最后一個字符 b，因為是最后一個字符，不用再做進一步的劃分了，上一步中得到的 b 的區間為 0.6390 - 0.6501，好，讓我們在這個區間內隨便選擇一個容易變成二進制的數，例如 0.64，將它變成二進制 0.1010001111，去掉前面沒有太多意義的 0 和小數點，我們可以輸出 1010001111，這就是信息被壓縮后的結果，我們完成了一次最簡單的算術壓縮過程。

怎么樣，不算很難吧？可如何解壓縮呢？那就更簡單了。解壓縮之前我們仍然假定三個字符的概率相等，并得出上面的第一幅分布圖。解壓縮時我們面對的是二進制流 1010001111，我們先在前面加上 0 和小數點把它變成小數 0.1010001111，也就是十進制 0.64。這時我們發現 0.64 在分布圖中落入字符 b 的區間內，我們立即輸出字符 b，并得出三個字符新的概率分布。類似壓縮時采用的方法，我們按照新的概率分布劃分字符 b 的區間。在新的劃分中，我們發現 0.64 落入了字符 c 的區間，我們可以輸出字符 c。同理，我們可以繼續輸出所有的字符，完成全部解壓縮過程（注意，為了敘述方便，我們暫時回避了如何判斷解壓縮結束的問題，實際應用中，這個問題并不難解決）。

現在把教程拋開，仔細回想一下，直到你理解了算術壓縮的基本原理，并產生了許多新的問題為止。

真的能接近極限嗎？

現在你一定明白了一些東西，也一定有了不少新問題，沒有關系，讓我們一個一個解決。

首先，我們曾反復強調，算術壓縮可以表示小數個二進制位，并由此可以接近無損壓縮的熵極限，怎么從上面的描述中沒有看出來呢？

算術編碼實際上采用了化零為整的思想來表示小數個二進制位，我們確實無法精確表示單個小數位字符，但我們可以將許多字符集中起來表示，僅僅允許在最后一位有些許的誤差。

結合上面的簡單例子考慮，我們每輸入一個符號，都對概率的分布表做一下調整，并將要輸出的小數限定在某個越來越小的區間范圍內。對輸出區間的限定是問題的關鍵所在，例如，我們輸入第一個字符 b 時，輸出區間被限定在 0.3333 - 0.6667 之間，我們無法決定輸出值得第一位是 3、4、5 還是 6，也就是說，b 的編碼長度小于一個十進制位（注意我們用十進制講解，和二進制不完全相同），那么我們暫時不決定輸出信息的任何位，繼續輸入下面的字符。直到輸入了第三個字符 c 以后，我們的輸出區間被限定在 0.6334 - 0.6667 之間，我們終于知道輸出小數的第一位（十進制）是 6，但仍然無法知道第二位是多少，也即前三個字符的編碼長度在 1 和 2 之間。等到我們輸入了所有字符之后，我們的輸出區間為 0.6390 - 0.6501，我們始終沒有得到關于第二位的確切信息，現在我們明白，輸出所有的 4 個字符，我們只需要 1 點幾個十進制位，我們唯一的選擇是輸出 2 個十進制位 0.64。這樣，我們在誤差不超過 1 個十進制位的情況下相當精確地輸出了所有信息，很好地接近了熵值（需要注明的是，為了更好地和下面的課程接軌，上面的例子采用的是 0 階自適應模型，其結果和真正的熵值還有一定的差距）。

小數有多長？

你一定已經想到，如果信息內容特別豐富，我們要輸出的小數將會很長很長，我們該如何在內存 中表示如此長的小數呢？

其實，沒有任何必要在內存中存儲要輸出的整個小數。我們從上面的例子可以知道，在編碼的進行中，我們會不斷地得到有關要輸出小數的各種信息。具體地講，當我們將區間限定在 0.6390 - 0.6501 之間時，我們已經知道要輸出的小數第一位（十進制）一定是 6，那么我們完全可以將 6 從內存中拿掉，接著在區間 0.390 - 0.501 之間繼續我們的壓縮進程。內存中始終不會有非常長的小數存在。使用二進制時也是一樣的，我們會隨著壓縮的進行不斷決定下一個要輸出的二進制位是 0 還是 1，然后輸出該位并減小內存中小數的長度。

靜態模型如何實現？

我們知道上面的簡單例子采用的是自適應模型，那么如何實現靜態模型呢？其實很簡單。對信息 bccb 我們統計出其中只有兩個字符，概率分布為 Pb = 0.5，Pc = 0.5。我們在壓縮過程中不必再更新 此概率分布，每次對區間的劃分都依照此分布即可，對上例也就是每次都平分區間。這樣，我們的壓縮過程可以簡單表示為：

輸出區間的下限 輸出區間的上限 -------------------------------------------------- 壓縮前 0.0 1.0 輸入 b 0.0 0.5 輸入 c 0.25 0.5 輸入 c 0.375 0.5 輸入 b 0.375 0.4375

我們看出，最后的輸出區間在 0.375 - 0.4375 之間，甚至連一個十進制位都沒有確定，也就是說，整個信息根本用不了一個十進制位。如果我們改用二進制來表示上述過程的話，我們會發現我們可以非常接近該信息的熵值（有的讀者可能已經算出來了，該信息的熵值為 4 個二進制位）。

為什么用自適應模型？

既然我們使用靜態模型可以很好地接近熵值，為什么還要采用自適應模型呢？

要知道，靜態模型無法適應信息的多樣性，例如，我們上面得出的概率分布沒法在所有待壓縮信息上使用，為了能正確解壓縮，我們必須再消耗一定的空間保存靜態模型統計出的概率分布，保存模型所用的空間將使我們重新遠離熵值。其次，靜態模型需要在壓縮前對信息內字符的分布進行統計，這一統計過程將消耗大量的時間，使得本來就比較慢的算術編碼壓縮更加緩慢。

另外還有最重要的一點，對較長的信息，靜態模型統計出的符號概率是該符號在整個信息中的出現概率，而自適應模型可以統計出某個符號在某一局部的出現概率或某個符號相對于某一上下文的出現概率，換句話說，自適應模型得到的概率分布將有利于對信息的壓縮（可以說結合上下文的自適應模型的信息熵建立在更高的概率層次上，其總熵值更小），好的基于上下文的自適應模型得到的壓縮結果將遠遠超過靜態模型。

自適應模型的階

我們通常用“階”(order)這一術語區分不同的自適應模型。本章開頭的例子中采用的是 0 階自適應模型，也就是說，該例子中統計的是符號在已輸入信息中的出現概率，沒有考慮任何上下文信息。

如果我們將模型變成統計符號在某個特定符號后的出現概率，那么，模型就成為了 1 階上下文自適應模型。舉例來說，我們要對一篇英文文本進行編碼，我們已經編碼了 10000 個英文字符，剛剛編碼的字符是 t，下一個要編碼的字符是 h。我們在前面的編碼過程中已經統計出前 10000 個字符中出現了 113 次字母 t，其中有 47 個 t 后面跟著字母 h。我們得出字符 h 在字符 t 后的出現頻率是 47/113，我們使用這一頻率對字符 h 進行編碼，需要 -log2 (47/113) = 1.266 位。

對比 0 階自適應模型，如果前 10000 個字符中 h 的出現次數為 82 次，則字符 h 的概率是 82/10000，我們用此概率對 h 進行編碼，需要 -log2 (82/10000) = 6.930 位。考慮上下文因素的優勢顯而易見。

我們還可以進一步擴大這一優勢，例如要編碼字符 h 的前兩個字符是 gt，而在已經編碼的文本中 gt 后面出現 h 的概率是 80%，那么我們只需要 0.322 位就可以編碼輸出字符 h。此時，我們使用的模型叫做 2 階上下文自適應模型。

最理想的情況是采用 3 階自適應模型。此時，如果結合算術編碼，對信息的壓縮效果將達到驚人的程度。采用更高階的模型需要消耗的系統 空間和時間至少在目前還無法讓人接受，使用算術壓縮的應用程序 大多數采用 2 階或 3 階的自適應模型。

轉義碼的作用

使用自適應模型的算術編碼算法必須考慮如何為從未出現過的上下文編碼。例如，在 1 階上下文模型中，需要統計出現概率的上下文可能有 256 * 256 = 65536 種，因為 0 - 255 的所有字符都有可能出現在 0 - 255 個字符中任何一個之后。當我們面對一個從未出現過的上下文時（比如剛編碼過字符 b，要編碼字符 d，而在此之前，d 從未出現在 b 的后面），該怎樣確定字符的概率呢？

比較簡單的辦法是在壓縮開始之前，為所有可能的上下文分配計數為 1 的出現次數，如果在壓縮中碰到從未出現的 bd 組合，我們認為 d 出現在 b 之后的次數為 1，并可由此得到概率進行正確的編碼。使用這種方法的問題是，在壓縮開始之前，在某上下文中的字符已經具有了一個比較小的頻率。例如對 1 階上下文模型，壓縮前，任意字符的頻率都被人為地設定為 1/65536，按照這個頻率，壓縮開始時每個字符要用 16 位編碼，只有隨著壓縮的進行，出現較頻繁的字符在頻率分布圖上占據了較大的空間后，壓縮效果才會逐漸好起來。對于 2 階或 3 階上下文模型，情況就更糟糕，我們要為幾乎從不出現的大多數上下文浪費大量的空間。

我們通過引入“轉義碼”來解決這一問題。“轉義碼”是混在壓縮數據流中的特殊的記號，用于通知解壓縮程序下一個上下文在此之前從未出現過，需要使用低階的上下文進行編碼。

舉例來講，在 3 階上下文模型中，我們剛編碼過 ght，下一個要編碼的字符是 a，而在此之前，ght 后面從未出現過字符 a，這時，壓縮程序輸出轉義碼，然后檢查 2 階的上下文表，看在此之前 ht 后面出現 a 的次數；如果 ht 后面曾經出現過 a，那么就使用 2 階上下文表中的概率為 a 編碼，否則再輸出轉義碼，檢查 1 階上下文表；如果仍未能查到，則輸出轉義碼，轉入最低的 0 階上下文表，看以前是否出現過字符 a；如果以前根本沒有出現過 a，那么我們轉到一個特殊的“轉義”上下文表，該表內包含 0 - 255 所有符號，每個符號的計數都為 1，并且永遠不會被更新，任何在高階上下文中沒有出現的符號都可以退到這里按照 1/256 的頻率進行編碼。

“轉義碼”的引入使我們擺脫了從未出現過的上下文的困擾，可以使模型根據輸入數據的變化快速 調整到最佳位置，并迅速減少對高概率符號編碼所需要的位數。

存儲空間問題

在算術編碼高階上下文模型的實現中，對內存的需求量是一個十分棘手的問題。因為我們必須保持對已出現的上下文的計數，而高階上下文模型中可能出現的上下文種類又是如此之多，數據結構的設計將直接影響到算法實現的成功與否。

在 1 階上下文模型中，使用數組來進行出現次數的統計是可行的，但對于 2 階或 3 階上下文模型，數組大小將依照指數規律增長，現有計算機的內存滿足不了我們的要求。

比較聰明的辦法是采用樹結構存儲所有出現過的上下文。利用高階上下文總是建立在低階上下文的基礎上這一規律，我們將 0 階上下文表存儲在數組中，每個數組元素包含了指向相應的 1 階上下文表的指針，1 階上下文表中又包含了指向 2 階上下文表的指針……由此構成整個上下文樹。樹中只有出現過的上下文才擁有已分配的節點，沒有出現過的上下文不必占用內存空間。在每個上下文表中，也無需保存所有 256 個字符的計數，只有在該上下文后面出現過的字符才擁有計數值。由此，我們可以最大限度地減少空間消耗。

資源

關于算術壓縮具體的設計和實現請參考下面給出的示例程序。

程序 Arith-N 由 League for Programming Freedom 的 Mark Nelson 提供，由王笨笨在 Visual C++ 5.0 環境下編譯、調試 通過。

Arith-N 包含 Visual C++ 工程 ArithN.dsp 和 ArithNExpand.dsp，分別對應了壓縮和解壓縮程序 an.exe 與 ane.exe。

Arith-N 是可以在命令行指定階數的 N 階上下文自適應算術編碼通用壓縮、解壓縮程序，由于是用作教程示例，為清晰起見，在某些地方并沒有刻意進行效率 上的優化 。

所有源程序包裝在文件 .NET /wangyg/tech/benben/src/Arith-N.zip">Arith-N.zip 中。

?

本文來自CSDN博客，轉載請標明出處：http://blog.csdn.net/pyramide/archive/2010/01/12/5172334.aspx