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

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

<p><strong>靜態模型如何實現？</strong></p>

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

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

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

<p><strong>為什么用自適應模型？</strong></p>

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

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

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

<p><strong>自適應模型的階</strong></p>

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

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

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

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

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

<p><strong>轉義碼的作用</strong></p>

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

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

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

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

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

<p><strong>存儲空間問題</strong></p>

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

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

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

<p><strong>資源</strong></p>

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

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

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

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

<p>所有源程序包裝在文件 <a href="src/arith-n.zip">arith-n.zip</a>
中。</p>

<p>　</p>
<div align="center"><center>

<address>
    <a href="chapter3.htm">第三章</a> <a href="chapter5.htm">第五章</a>
</address>
</center></div>

<p align="center">　</p>
<div align="right">

<address>
    有問題嗎？有建議嗎？快給王笨笨寫信：wangyg@contextfree.net
</address>
</div><div align="right">

<address>
    <strong>章節書簽：</strong><a href="default.htm">前言</a>
    <a href="content.htm">目錄</a> <a href="chapter1.htm">1</a>
    <a href="chapter2.htm">2</a> <a href="chapter3.htm">3</a> <a
    href="chapter4.htm">4</a> <a href="chapter5.htm">5</a> <a
    href="chapter6.htm">6</a> <a href="chapter7.htm">7</a> <a
    href="chapter8.htm">8</a> <a href="chapter9.htm">9</a> <a
    href="chapter10.htm">10</a> <a href="chapter11.htm">11</a> <a
    href="chapter12.htm">12</a> 
</address>
</div>
</body>
</html>