李 彬，倪桂強，羅健欣

(解放軍理工大學(xué) 指揮自動化學(xué)院，江蘇 南京210007)

數(shù)據(jù)壓縮分為有損壓縮和無損壓縮。其中無損壓縮編碼是基于信息熵原理的可逆編碼，目前主要有基于統(tǒng)計模型的哈夫曼編碼和算術(shù)編碼，以及基于字典模型的LZ系列編碼。算術(shù)編碼克服了哈夫曼編碼只能用整數(shù)位的代碼表示一個信源符號的缺點，而采用了用一個浮點數(shù)表示一個信源符號流的思想，可以更逼近信源編碼。算術(shù)編碼算法在靜止圖像壓縮編碼標(biāo)準(zhǔn)JPEG2000[1]和視頻編碼標(biāo)準(zhǔn)H.264[2]中已被作為國際標(biāo)準(zhǔn)廣泛采用。

提高編碼的壓縮率和降低編碼的時間、空間復(fù)雜度是人們研究壓縮編碼算法的主要目的?；趯π畔⒅袉蝹€符號頻率統(tǒng)計的算術(shù)編碼是一種向極限挑戰(zhàn)的編碼方式。本文研究的多階自適應(yīng)算術(shù)編碼著重通過研究符號在某符號序列之后出現(xiàn)的概率來獲得高效壓縮。參考文獻[3]介紹了一種基于多階上下文自適應(yīng)的二進制算術(shù)編碼的實現(xiàn)，實現(xiàn)了3階自適應(yīng)。參考文獻[4]介紹了一種能降低復(fù)雜度和內(nèi)存空間但是略微降低了編碼效率的簡化編碼模型。本文的多階自適應(yīng)算術(shù)編碼對參數(shù)進行了優(yōu)化，可以進行更高階次的編碼（測試中最高可達11階），在最大限度降低空間消耗的同時，獲得更好的壓縮效果。與LZW和WinRAR的性能比較結(jié)果表明，本文的多階自適應(yīng)算術(shù)編碼能獲得更滿意的壓縮效果。

1 算術(shù)編碼

1.1 算術(shù)編碼原理

算術(shù)編碼將被編碼的信源符號流表示成實數(shù)半開區(qū)間[0，1)中的一個數(shù)值間隔，這個間隔隨著信息流中每一個信源符號的加入逐步減小，每次減小的程度取決于當(dāng)前加入的信源符號的概率。概率高者減少的程度低，概率低者減少的程度高。符號流越長，代表它的間隔越小，編碼表示這一間隔所需的位數(shù)就越多。從算術(shù)編碼過程中產(chǎn)生的數(shù)值可以被唯一地解碼，精確地恢復(fù)原始的信源符號流[3]。

設(shè)信源符號集由 3個信源符號{a1，a2，a3}組成，根據(jù)已知的信源符號概率，在[0，1)區(qū)間上為它們分配相應(yīng)的子區(qū)間，子區(qū)間大小與概率成正比。其概率分布及對應(yīng)的子區(qū)間如表1所示。

表1 信源符號及其數(shù)值范圍

用range表示編碼輸出數(shù)值落入的間隔，high為range的上界，low為下界，初始時 high為 1，low為 0。 用high_range表示某符號子區(qū)間的上界，low_range為下界。每一信源符號被編碼后，根據(jù)公式(1)計算 high、low及range的新值，并根據(jù)概率分布重新劃分被編碼符號的子區(qū)間。最后一個符號得到的間隔內(nèi)的任何一個實數(shù)代表整個符號流。對符號流“a1a2a3a2a1”進行算術(shù)編碼的過程如圖1所示，用0.305就可以唯一地代表這個符號流。

1.2 多階自適應(yīng)算術(shù)編碼

根據(jù)編碼過程中信源符號是否更新概率分布，算術(shù)編碼分為靜態(tài)模型和自適應(yīng)模型。靜態(tài)模型的缺點是：首先需要在編碼前對信源符號的分布進行統(tǒng)計，會消耗大量時間；其次符號的概率是該符號在整個信息中的概率，根據(jù)信息熵原理，不利于對信息的壓縮。而自適應(yīng)模型隨著符號的讀入，實時動態(tài)更新符號的概率分布，能統(tǒng)計出某個符號在局部的出現(xiàn)概率或某個符號相對于某一上下文的出現(xiàn)概率，壓縮效果好于靜態(tài)模型。

自適應(yīng)編碼中，初始時假設(shè)各個符號的概率相同，并平均分配區(qū)間[0，1)，隨著符號的讀入，相應(yīng)地更新其概率值，與之對應(yīng)的子區(qū)間亦隨之改變。若有新的符號出現(xiàn)則加入符號集即可。仍設(shè)信源符號集由3個符號{a1，a2，a3}組成，對于符號流“a1a2a3a2a1”，各個符號概率更新、子區(qū)間比例變化、符號累計及間隔變化過程如表2所示。

最后一個符號輸入后不再劃分子區(qū)間，得到讀入a1后的區(qū)間[0.238 9，0.240 4)，即編碼結(jié)果的輸出數(shù)值區(qū)間，如0.24就可以作為符號流編碼結(jié)果。同樣類似的解碼過程可以唯一地解出原符號流。

如果編碼時考慮符號之間的相關(guān)性，把多個符號按照不同的上下文結(jié)構(gòu)組合在一起，當(dāng)作一個編碼單元進行自適應(yīng)算術(shù)編碼，就可以進一步提高編碼效率。用“階”表示上下文相關(guān)符號序列的長度，那么1階上下文自適應(yīng)統(tǒng)計的就是符號在某個特定的符號后面出現(xiàn)的概率，同樣2階、3階上下文自適應(yīng)統(tǒng)計的是符號在某兩個、三個特定符號后面出現(xiàn)的概率。使用多階算術(shù)編碼，使得同一符號可以在多個動態(tài)統(tǒng)計的上下文概率表中取得概率值較大的進行編碼，從而使總熵值更小。如在1階自適應(yīng)編碼中，在已經(jīng)編碼的10 000個符號后，剛剛編碼的符號是a1，下一個要編碼的符號是a2，在之前的10 000個符號中統(tǒng)計到出現(xiàn)了100個a1和 a2，a2出現(xiàn)在 a1之后的次數(shù)是 10次，那么 a2在 a1之后的概率是 10/100，這一概率對應(yīng)的熵值是-log2(10/100)=3.321 9 bit，遠小于 0階的熵值-log2(100/10000)=6.643 9 bit。采用 2階、3階或更高階次的自適應(yīng)算術(shù)編碼，可以獲得更高的壓縮率。

2 建模與算法實現(xiàn)

2.1 自適應(yīng)編碼模型

用high_count和low_count表示ai對應(yīng)的子區(qū)間上下界，用scale表示已讀入符號總數(shù)。讀入符號ai時，scale加1，與該符號對應(yīng)的子區(qū)間的上界及后面子區(qū)間的上下界值都加1。high和low表示編碼輸出數(shù)值range的上下界，其初始值分別為0xffff和0，則可以通過公式(2)確定range的范圍。在編碼過程中，用二進制表示的range的數(shù)值范圍越來越小，當(dāng)high與low的最高位相同時，則把最高位二進制作為碼流輸出，且使high與low左移一位，high末位補 1，low末位補 0。當(dāng) high與 low十分接近沒有相同最高位時，就產(chǎn)生下溢，這時需要擴大range使后面的編碼繼續(xù)進行，記錄下溢位數(shù)，并在下次編碼時作為碼流輸出，用于解碼時保持一致。圖2顯示了自適應(yīng)編碼的基本過程。

2.2 多階上下文模型

符號在某符號序列后出現(xiàn)的概率往往高于其在整個信息中的概率，這是多階自適應(yīng)算術(shù)編碼能顯著提高壓縮效果的關(guān)鍵。在1階上下文模型中，使用數(shù)組來統(tǒng)計符號出現(xiàn)的次數(shù)是可行的，但對于2階、3階或更高階的上下文，數(shù)組大小將按指數(shù)級增長（256n+1），采用樹結(jié)構(gòu)[4]存儲出現(xiàn)過的上下文可以解決存儲空間問題。因此，多階上下文模型是一個包含多個鏈表節(jié)點的樹形結(jié)構(gòu)，如果根的層次為0，那么樹的層次對應(yīng)了模型的階，父節(jié)點對應(yīng)低階上下文，子節(jié)點對應(yīng)高階上下文，各層鏈表節(jié)點構(gòu)成了該層符號表，鏈表節(jié)點中指向父節(jié)點和子節(jié)點的指針構(gòu)成了符號序列的上下文關(guān)系，形成上下文樹。樹中只有出現(xiàn)過的上下文才擁有已分配的節(jié)點，沒有出現(xiàn)過的上下文不占用內(nèi)存空間。在每個上下文表中，也無需保存所有 256個字符的計數(shù)，只有在該上下文后面出現(xiàn)過的字符才擁有計數(shù)值。由此，可以最大限度地減少空間消耗。

對于一個未知的上下文，需要用到一個特殊的記號——轉(zhuǎn)義碼，用來告知解碼器下一個上下文在此之前從未出現(xiàn)過，需要使用低階的上下文進行解碼。比如在3階上下文模型中，剛剛編碼過 a1a2a3，現(xiàn)在要編碼a4，而在a1a2a3后面從來沒有出現(xiàn)過a4，這時需要輸出轉(zhuǎn)義碼，并進入2階上下文表查找a4在a2a3后面出現(xiàn)在次數(shù)，如果找到則用2階中的概率為a4編碼，否則輸出轉(zhuǎn)義碼進入1階上下文表查找，如仍未找到，則輸出轉(zhuǎn)義碼進入最低的0階上下文表，如果a4從未出現(xiàn)過，則轉(zhuǎn)到一個特殊的轉(zhuǎn)義表，表內(nèi)包含0～255所有符號，每個符號的計數(shù)都為1，并且永遠不會被更新，任何在高階上下文中沒有出現(xiàn)的符號都可以退到這里按照1/256的概率進行編碼，隨后將a4加入到各階符號表中。符號流“a1a2a3a4…ai…”的上下文環(huán)境處理過程如圖 3所示，其中節(jié)點是簡化了的鏈表節(jié)點，實線箭頭表示指向高一階上下文的指針（葉子節(jié)點指針為空），形成上下文表，虛線箭頭表示指向低一階上下文的指針（根節(jié)點除外）。

多階上下文模型在初始化時，需要創(chuàng)建轉(zhuǎn)義表及初始上下文表，上下文表中各階鏈表節(jié)點中設(shè)置符號表、符號計數(shù)器、符號表大小計數(shù)器以及上下文指針。讀入符號后，在當(dāng)前上下文表中從高階到低階查找符號表，找到后輸出其在符號表的累計次數(shù)，進而計算其概率區(qū)間，否則進入轉(zhuǎn)義表，輸出固定的概率值1/256，然后進入編碼器編碼，編碼完成后，更新上下文表，將符號加入到當(dāng)前上下文各階節(jié)點的符號表中，并更新符號計數(shù)器。多階上下文自適應(yīng)算術(shù)編碼流程如圖4所示。

3 性能測試與比較

壓縮率是反應(yīng)壓縮效果的重要指標(biāo)，其計算式為：（1-輸出文件大小/輸入文件大?。?00%，其值越大，壓縮效果越好。為測試程序性能，選取了不同大小和不同類型的文件進行壓縮，試驗結(jié)果如圖5所示，其中文本文件是大小為137 979 B的歷史文獻節(jié)選，位圖文件是分辨率為1 680×1 050、大小為 5 292 054 B的電腦桌面文件。從結(jié)果中可以看出，多階自適應(yīng)算術(shù)編碼能達到很好的壓縮效果，壓縮率隨著階次的升高而提高，但提高幅度逐漸降低，3階和4階就能達到比較顯著的壓縮效果。與參考文獻[5]中改進的LZW算法比較發(fā)現(xiàn)，0～2階的壓縮效果要差于LZW，但從3階開始，壓縮效果就要優(yōu)于LZW。

考慮到多階自適應(yīng)算術(shù)編碼的特征，其對上下文相關(guān)性強的文件壓縮可以達到更高的壓縮率。為此，選取了一個內(nèi)容相關(guān)性強的文本文件和一個背景變化不太大的位圖文件，如表3和表4所示顯示了多階自適應(yīng)算術(shù)編碼與LZW以及WinRAR的比較結(jié)果。可看出，多階自適應(yīng)算術(shù)編碼對上下文相關(guān)性強的文件壓縮效果從2階開始就優(yōu)于LZW，而3、4階就能較明顯的好于WinRAR。

表5記錄了多階自適應(yīng)算術(shù)編碼和LZW算法對上述4個文件壓縮所需要的時間，從表中可以看出，低階編碼消耗的時間最多，3階、4階左右消耗的時間最少，再高階次消耗的時間反而上升。 另外，對于一般性文件，LZW消耗的時間明顯少于本文多階算法，但是對于上下文相關(guān)性強的文件，本文多階算法可以明顯少于LZW。

表3 壓縮比較(原文件：110 522 B)

表4 壓縮比較(原文件：3 932 214 B)

表5 多階自適應(yīng)算術(shù)編碼與LZW算法時間消耗比較（單位：s）

從以上性能測試與比較中可以得出，本文研究的多階自適應(yīng)算術(shù)編碼在3階、4階時可以獲得滿意的壓縮率，而且消耗的時間最少，在整體上壓縮效果最佳。

[1]陳瑋，楊名利.基于 FPGA的 JPEG2000自適應(yīng)算術(shù)編碼器設(shè)計[J].計算機技術(shù)與發(fā)展，2006，16(10)：211-213.

[2]DAMIAN K，MAREK D.Improved context-adaptive arithmetic coding in H.264/avc[C].Glasgow：EUSIPCO，2009：2216-2220.

[3]楊文濤，劉衛(wèi)忠，鄭立新.多階上下文自適應(yīng)二進制算術(shù)編碼實現(xiàn)[J].華中科技大學(xué)學(xué)報(自然科學(xué)版)，2007，35(3)：42-45.

[4]謝林，虞露，仇佩亮.基于上下文的自適應(yīng)二進制算術(shù)編碼研究[J].浙江大學(xué)學(xué)報(工學(xué)版)，2005，39(6)：910-914.

[5]張鳳林，劉思峰.LZW*：一個改進的LZW數(shù)據(jù)壓縮算法[J].小型微型計算機系統(tǒng)，2006，27(10)：1897-1899.