李　英，崔艷鵬，高新波

(1. 西安電子科技大學電子工程學院　西安　710071；2. 西安電子科技大學網(wǎng)絡行為研究中心　西安　710071)

一種基于算術編碼的文本數(shù)據(jù)壓縮算法

李英1，崔艷鵬2，高新波1

(1. 西安電子科技大學電子工程學院西安710071；2. 西安電子科技大學網(wǎng)絡行為研究中心西安710071)

提出了一種基于算術編碼的文本數(shù)據(jù)壓縮算法，將掃描產(chǎn)生的偏移量、匹配數(shù)據(jù)長度等全局優(yōu)化問題轉化為局部優(yōu)化問題，并從Glomb編碼思路出發(fā)，推導出一種參數(shù)選擇算法；對LZ77算法進行修正，提出一種預測編碼方法，獲得預測參數(shù)。對預測參數(shù)、偏移量、數(shù)據(jù)匹配長度、保留文本數(shù)據(jù)使用MQ算術編碼器進行編碼，針對不同類型數(shù)據(jù)，設計出不同的編碼算法和相應的上下文算法。對算法進行仿真，并與Winzip、WinRar壓縮效率進行比較，結果表明對純文本數(shù)據(jù)、Word文檔數(shù)據(jù)、C語言程序代碼，圖像數(shù)據(jù)等，該壓縮算法優(yōu)于Winzip；在純文本數(shù)據(jù)、Word文檔數(shù)據(jù)、C語言程序代碼壓縮方面與WinRar相當或者略好，但在圖像壓縮方面的性能與WinRar相比略有不足。

算術編碼;參數(shù)優(yōu)化;預測編碼;文本數(shù)據(jù)壓縮

隨著計算機技術和網(wǎng)絡技術的發(fā)展，各種類型的數(shù)據(jù)層出不窮，海量的數(shù)據(jù)需要傳輸和存儲。為了減少數(shù)據(jù)傳輸和存儲的代價需要對數(shù)據(jù)進行壓縮。根據(jù)不同的數(shù)據(jù)種類及重建質量要求，壓縮算法也各不相同。比如語音壓縮、圖像壓縮[1-6]等，根據(jù)重建質量的不同要求，可以進行限失真壓縮或者無失真壓縮。

由于文本數(shù)據(jù)必須進行精確重建，只能進行無失真壓縮。目前文本壓縮算法眾多，許多算法是針對各種不同類型的應用[7-11]；廣泛使用的文本壓縮工具是WinRar和Winzip，這兩種壓縮算法涉及知識產(chǎn)權保護，詳細編碼過程未見公布，可能采用了預測編碼、游程長度編碼、LZ算法或者LZW等改進算法[7-11]。而這些算法主要突出于文本搜索算法，其中LZW搜索算法需要建立碼書[9-10]，使用碼書可以提高搜索速度，對于長串匹配數(shù)據(jù)而言，還可以有效減少LZ算法中的偏移量，利于提高編碼效率。而這兩種文本壓縮算法使用的熵編碼以及其他細節(jié)未見文獻報道。

為了設計自主知識產(chǎn)權的文本壓縮方法，本文擬采用原始LZ77算法，整個過程并不需要建立碼表，目的主要在于嘗試使用算術編碼對文本數(shù)據(jù)掃描參數(shù)進行壓縮，并為后續(xù)進一步研究奠定基礎。

本文主要工作如下：提出了一種局部參數(shù)優(yōu)化算法，從備選參數(shù)中選擇合理的局部優(yōu)化參數(shù)；對LZ77算法進行改進，增加了預測編碼，并記錄預測標記。預測編碼標記為0和1組成的序列，使用已經(jīng)編碼的前面數(shù)據(jù)產(chǎn)生上下文，并使用算術編碼器進行編碼，能夠有效提高編碼效率。選擇出的掃描參數(shù)，即偏移量、匹配數(shù)據(jù)長度和保留文本數(shù)據(jù)，都使用算術編碼器進行編碼，并根據(jù)各類數(shù)據(jù)的特點使用不同方法產(chǎn)生效應上下文。

1　改進文本數(shù)據(jù)壓縮算法

1.1基于Glomb編碼的優(yōu)化參數(shù)選取

LZ77文本壓縮算法是將當前位置開始的、未知長度的文本數(shù)據(jù)與已經(jīng)掃描過的文本數(shù)據(jù)進行匹配，查找到合理的匹配文本數(shù)據(jù)，記錄下相應的偏移量、匹配數(shù)據(jù)長度、首次出現(xiàn)的文本數(shù)據(jù)等信息。

假設當前位置為i，從第一個匹配文本數(shù)據(jù)開始，搜索到的所有偏移量、匹配數(shù)據(jù)長度分別為ijΔ、lij，其中j=1,2,…,Ni，Ni表示搜索到的匹配文本數(shù)據(jù)的數(shù)量。按照某種準則從Ni個備選參數(shù)集合(ijΔ,lij)來選擇其中一組參數(shù)作為當前搜索的結果，從而使得整個文本數(shù)據(jù)壓縮后的碼流最短。

選擇好的參數(shù)(iΔ,li)來自于備選參數(shù)集合(ijΔ,lij)，表示為：

式中，T(·)表示從參數(shù)集合中選擇一種最佳參數(shù)。為了實現(xiàn)文本數(shù)據(jù)壓縮，參數(shù)選擇后應該經(jīng)過熵編碼器進行編碼，從而得到文本壓縮的碼流，并從各種可能中選擇最優(yōu)參數(shù)。顯然這種全局優(yōu)化選擇方法在工程中幾乎無法實現(xiàn)。

除了上述備選集合參數(shù)外，還涉及到另外一個問題，就是首次出現(xiàn)的文本數(shù)據(jù)問題。如果文本壓縮是全文搜索，且不論壓縮效率如何，對備選參數(shù)集合中的參數(shù)進行壓縮，那么首次出現(xiàn)的文本數(shù)據(jù)的數(shù)量實際是非常有限的，例如將文本數(shù)據(jù)按照8 bit劃分，首次出現(xiàn)的文本數(shù)據(jù)的數(shù)量不大于28=256。更多情況下，文本數(shù)據(jù)壓縮需要設置一個窗口，數(shù)據(jù)匹配是在窗口內(nèi)進行的，即使在窗口內(nèi)能夠找到備選參數(shù)，為了提高壓縮效率，也需要對備選參數(shù)進行選擇，如果所有的備選參數(shù)都不能滿足壓縮效率的要求，則應該將當前文本數(shù)據(jù)視為首次出現(xiàn)文本數(shù)據(jù)。為了不至于產(chǎn)生誤解，將這類文本數(shù)據(jù)稱之為保留文本數(shù)據(jù)。

從備選參數(shù)集合中選擇壓縮編碼所需參數(shù)，實際是一個全局優(yōu)化問題。即：

對于該優(yōu)化問題，最簡單的思路就是考慮所有可能選擇，從而得到最短壓縮碼流長度Lmin。但文本數(shù)據(jù)的統(tǒng)計特性十分復雜，且壓縮編碼的效率與參數(shù)選擇過程密切相關，全局優(yōu)化難以實現(xiàn)?？紤]局部優(yōu)化替代全局優(yōu)化，從而便于工程實現(xiàn)。構造決策函數(shù)：

根據(jù)上述分析，可以得出文本數(shù)據(jù)壓縮結構如圖1所示。

圖1 文本壓縮結構框圖

上述局部優(yōu)化看起來合理，但實際上無法實現(xiàn)。因為實際編碼并沒有進行，無法知道參數(shù)的編碼比特數(shù)，無論是偏移量、長度還是保留文本數(shù)據(jù)。為了解決上述問題，本文采用一種較為簡潔算法解決上述局部優(yōu)化問題，具體如下。

首先假設偏移量、長度都是采用Glomb編碼，對應的參數(shù)為k1、k2，根據(jù)Glomb編碼可知，編碼輸出碼長分別為：

同時選擇調節(jié)參數(shù)1α，決策函數(shù)為：

對于滿足上述條件的參數(shù)，以長度最大且偏移量最小為準則，作為最終選擇參數(shù)；如果參數(shù)集合中所有參數(shù)滿足式(7)，則令偏移量，輸出保留文本數(shù)據(jù)；否則輸出偏移量 Δi和匹配數(shù)據(jù)長度li。

1.2預測編碼

在文本數(shù)據(jù)壓縮中，偏移量iΔ、匹配數(shù)據(jù)長度li的分布都比較復雜。偏移量iΔ中經(jīng)常會出現(xiàn)許多幅值很大的數(shù)據(jù)，其分布動態(tài)范圍很大；為了記錄保留文本數(shù)據(jù)的位置信息，偏移量為0表示該數(shù)據(jù)為保留文本數(shù)據(jù)，譯碼時一旦遇到0，就可以從已經(jīng)譯碼出的保留文本數(shù)據(jù)中取出數(shù)據(jù)，從而實現(xiàn)數(shù)據(jù)重建。位置信息的引入，又增加了數(shù)據(jù)分布的復雜性，也相應增加了編碼復雜度。與此同時，li的幅值盡管相對比較小，但是數(shù)據(jù)分布也是非平穩(wěn)的，無法使用數(shù)學分解工具對其進行分解，從而提高壓縮效率。

考慮到上述因素，為了提高編碼效率，可以進行預測編碼。文本數(shù)據(jù)往往具有一定的規(guī)律，每隔一定間隔，有些數(shù)據(jù)就會重復出現(xiàn)，這類情況可以加以利用。

圖2 改進算法結構框圖

2　參數(shù)的算術編碼實現(xiàn)

MQ算術編碼是改進的Q算法，屬于自適應的二進制算術編碼方法[4-5]，能夠有效實現(xiàn)高效數(shù)據(jù)壓縮，該編碼器在圖像壓縮中已得到廣泛應用。MQ編碼器是通過自適應狀態(tài)跳轉，從而使最終編碼輸出的字節(jié)數(shù)量能夠盡可能小。為了提高編碼效率，MQ算術編碼提供了數(shù)據(jù)分類算法，數(shù)據(jù)分類采用上下文(CX)表示，編碼輸入為二進制判決(D)，如圖3所示。

圖3 MQ算術編碼器

MQ編碼器效果與上下文設計密切相關。在文本數(shù)據(jù)壓縮中使用MQ算術編碼器，需要研究上下文、判決的形成問題。根據(jù)上文可知，文本數(shù)據(jù)掃描過程中會產(chǎn)生偏移量、匹配數(shù)據(jù)長度、保留文本數(shù)據(jù)、預測參數(shù)等。這些數(shù)據(jù)都可以使用算術編碼進行熵編碼。

預測參數(shù)是二進制，不涉及判決產(chǎn)生問題，只需要進行簡單的數(shù)據(jù)分類即可。本文中，上下文為前一個預測值。偏移量、匹配數(shù)據(jù)長度、保留文本數(shù)據(jù)的編碼都是采用比特平面編碼方法，其判決形成與圖像壓縮中的方法相同，而上下文的形成和編碼過程則需要根據(jù)各類數(shù)據(jù)的特點進行研究。偏移量、匹配數(shù)據(jù)長度的編碼分為兩個步驟：零編碼和細化編碼。零編碼對當前比特平面編碼之前還不重要的系數(shù)進行比特平面編碼；而細化編碼則是對在當前比特平面編碼之前已經(jīng)重要的系數(shù)進行編碼。

零編碼的上下文是根據(jù)前后數(shù)據(jù)的重要性產(chǎn)生，即：

式中，CXi表示當前數(shù)據(jù)的上下文；sig(i?1)表示前一個數(shù)據(jù)的重要性；sig(i+1)表示后一個數(shù)據(jù)的重要性。sig(i)=0表示該數(shù)據(jù)是不重要的，sig(i)=1表示該數(shù)據(jù)是重要的。如果數(shù)據(jù)在當前比特平面編碼之前的判決都為0，而在當前比特平面的判決為1，則該數(shù)據(jù)在當前比特平面編碼時由不重要變?yōu)橹匾?/p>

而細化編碼的上下文則是采用零編碼沒有使用的固定上下文，即。保留文本數(shù)據(jù)的編碼只有一個步驟，而上下文則取當前比特編碼之前的數(shù)據(jù)。

3　實驗結果與分析

對所提出的文本壓縮算法進行仿真和測試。采用4種文本數(shù)據(jù)對本算法性能進行測試，并與Winzip、WinRar壓縮效率進行比較，具體結果如表1所示。其中Test1是Word文檔，Test2是純文字文檔，Test3是C語言程序代碼(JPEG-LS核心算法)，Test4是Lena圖像。

由表1結果可以看出，對這4類不同類型數(shù)據(jù)，本文算法壓縮性能明顯好于Winzip，而在Word文檔或者純文字文檔壓縮方面與WinRar相當或者略好；而在C語言程序代碼壓縮方面，本文算法也與WinRar相當或者略低，而對圖像壓縮進行壓縮時，本文壓縮效率與WinRar還有一定差距。

表1 算法比較　byte

與WinRar比較結果可以看出，本文算法對圖像數(shù)據(jù)壓縮沒有取得好的效果，這是因為本文算法沒有進一步使用數(shù)據(jù)之間的相關性進行編碼，因此如何進一步利用相關性進行編碼值得進一步研究。

為了考察參數(shù)α變化對壓縮效率影響，選擇參數(shù)k1=10，k2=6，使用Test1進行測試，具體結果如表2所示。從表2可以看出，當α大于一定值時對壓縮效率影響非常有限。從式(7)可以看出，只有當偏移量很大時，參數(shù)選擇才有意義，其目的是去除那些偏移量很大，而匹配字節(jié)長度較小的那些參數(shù)。而當α大于一定值時，選擇參數(shù)的差異并不是太大，所以壓縮效率變化較小。

表2 參數(shù)α變化對壓縮效率影響　byte

當α取值較小時，參數(shù)選擇的變化就體現(xiàn)出來，一些偏移量很大而匹配字節(jié)長度有限的參數(shù)被選擇，從而降低了編碼效率，編碼輸出文件長度增加較大，從而影響總體編碼效率。

為了考察Glomb參數(shù)選擇對壓縮效率的影響，取α=6.2，k2=6，改變參數(shù)k1，使用Test1進行測試，結果如表3所示。

表3 參數(shù)k1變化對壓縮效率影響　byte

從表3可以看出，參數(shù)的變化對壓縮效率有一定影響，參數(shù)小于10時，隨著參數(shù)減小，壓縮效率明顯降低；而當參數(shù)大于等于10時，由于偏移量大而匹配數(shù)據(jù)長度小的參數(shù)被去除，壓縮效率沒有明顯變化。

為了觀察k2變化對壓縮效率影響，取α=6.2，k1=10，改變參數(shù)k2，使用Test1進行測試，實驗結果如表4所示。

表4 參數(shù)k2變化對壓縮效率影響　byte

從表4可以看出，隨著k2的變化，對壓縮效率有一定影響，但是不是十分明顯。從式(7)可看出，由于大偏移量受到k1約束，k2取值只是輔助參數(shù)選擇的細節(jié)，且受到α變化的制約，因此對總體效率的影響不是很大，其取值大小與匹配字節(jié)長度小的參數(shù)選擇產(chǎn)生一定影響。當其取值太大，會增加小匹配字節(jié)長度選取的門檻，所以對壓縮效率影響較大；而取值較小時，其影響反而不是太大。

綜合k1、k2變化對壓縮效率影響，結果與式(7)說描述的含義是相符的，即：

1)k1主要是限制偏移量大而匹配字節(jié)長度較小的參數(shù)，以提高編碼效率；當其取值較小時，偏移量大，匹配字節(jié)長度較小的參數(shù)被選擇，從而影響編碼效率；而取值較大時，只有極少的參數(shù)被限制，對壓縮效率的影響反而較小。因為匹配字節(jié)長度較大的參數(shù)，k1變化對其沒有約束。

2)k2對偏移量變化沒有限制作用，主要輔助設置匹配字節(jié)長度門檻。取值越大，更多長度較小的參數(shù)被去除，效率降低；而較小的取值，反而對結果影響不大。

4　結　論

本文提出了一種基于算術編碼的文本數(shù)據(jù)壓縮算法，與Winzip、WinRar算法相比，在對純文本數(shù)據(jù)、Word文檔數(shù)據(jù)、C語言程序代碼進行壓縮時，本文算法優(yōu)于WinZip，與WinRar算法相當或略好，但在圖像壓縮方面的性能與WinRar相比略有不足。當然，本文算法還存在以下不足：一方面，簡單使用LZ77掃描算法，從而導致偏移量數(shù)據(jù)較大，不利于后續(xù)數(shù)據(jù)壓縮；另一方面，沒有對相關性數(shù)據(jù)進行進一步處理，對諸如圖像數(shù)據(jù)這類關聯(lián)性很強的數(shù)據(jù)壓縮效率不足。針對上述不足，今后將考慮更好的掃描算法，以提高壓縮效率；對數(shù)據(jù)的相關性進行檢測，對相關性強的數(shù)據(jù)進行數(shù)據(jù)分解，進一步提高編碼效率。

[1]TAUBMAN D. High Performance scalable image compression with EBCOT[J]. IEEE Trans on Image Processing,2000,9(7): 1158-1170.

[2]ISO/IEC. Image coding specification[EB/OL]. [2015-07-21]. http://www.iso.org/iso/iso_catalogue/catalogue_tc/catalogue _detail.htm?csnumber=51609.

[3]DENG Jia-xian,DENG Hai-tao. An image joint compression-encryption algorithm based on adaptive arithmetic coding[J]. Chin Phys B,2013,22(9): 094202-1-094202-6.

[4]WU J Z,WANG Y J,DING L P,et al. Improving performance of network covert timing channel through Huffman coding[J]. Mathematical and Computer Modelling,2012,55(1-2): 69-79.

[5]鄧家先,任玉莉. 基于改進零樹編碼的圖像聯(lián)合壓縮加密算法[J]. 光子學報,2013,42(1): 121-126. DENG Jia-xian,REN Yu-li. Image joint compressionencryption algorithm based on improved zero-tree coding[J]. Acta Photonica Sinica,2013,42(1): 121-126.

[6]謝耀華,湯曉安,孫茂印,等. 基于分類重排LZW的圖像無損壓縮算法[J]. 中國圖象圖形學報,2010,15(2): 236-241. XIE Yao-hua,TANG Xiao-an,SUN Mao-yin,et al. A lossless image compression algorithm based on classification,re-ordering and LZW[J]. Journal of Image and Graphics,2010,15(2): 236-241.

[7]王忠效. 漢語文本壓縮研究及其應用[J]. 中文信息學報,1997,11(3): 57-64. WANG Zhong-xiao. Research and application of chinese text compression[J]. Journal of Chinese Information Processing,1997,11(3): 57-64.

[8]特日跟,李雄飛,李軍. 基于整數(shù)數(shù)據(jù)的文檔壓縮編碼方案[J]. 吉林大學學報,2016,46(1): 228-234. TE Ri-gen,LI Xiong-fei,LI Jun. Document compression coding scheme based on integer data[J]. Journal of Jilin University,2016,46(1): 228-234.

[9]ZIV J,LEMPEL A. Compression of individual sequences via variable-rate coding[J]. IEEE Transactions on Information Theory,1978,24(5): 530-536.

[10]ZIV J,LEMPEL A. A universal algorithm for sequential data compression[J]. IEEE Transactions on Information Theory,1977,23(3): 337-343.

[11]常為領,方興濱,云曉春,等. 一種支持ANSI編碼的中文文本壓縮算法[J]. 中文信息學報,2010,24(5): 96-105. CHANG Wei-ling,FANG Xin-bin,YUN Xiao-chun,et al. A chinese text compression algorithm for ANSI coding[J]. Journal of Chinese Information Processing,2010,24(5): 96-105.

編輯稅紅

A Novel Algorithm for Text Data Compression Based on Arithmetic Codec

LI Ying1,CUI Yan-peng2,and GAO Xin-bo1
(1.School of Electronic Engineering,Xidian UniversityXi’an710071;2. Institute for Internet Behavior,Xidian UniversityXi’an710071)

A novel algorithm for text data compression is proposed based on arithmetic codec. The global parameters optimization is converted into the local parameter optimization,then Glomb code principle is used to solve the local optimization,and a parameter choice method is derived. The LZ77 scanning algorithm is improved in which a prediction code is proposed,and the prediction data is preserved. The parameters such as prediction data,offset,match data length and preserved text data are loaded into MQ codec in which the data can be compressed. To improve the compression efficiency,the corresponding compression algorithms and the context design algorithm are proposed. The proposed algorithm for text data compression is simulated and compared with Winzip and WinRAR. The results show that our compression algorithm has an advantage in compression effect over the Winzip for the data such as texts,word documents,C language program codes and images. Compared with WinRar,our algorithm achieved almost the same compression results for texts,word documents,C language program codes except images.

arithmetic code;parameters optimization;predict code;text data compression

TP391.1

A

10.3969/j.issn.1001-0548.2016.06.009

2015 ? 08 ? 24；

2016 ? 03 ? 23

國家自然科學基金(61571354)

李英(1976 ? )，女，博士生，高級工程師，主要從事圖像處理及編碼、移動通信技術等方面的研究.