常為領(lǐng)，方濱興,，云曉春，王樹(shù)鵬，余翔湛

(1. 哈爾濱工業(yè)大學(xué) 計(jì)算機(jī)網(wǎng)絡(luò)與信息安全技術(shù)研究中心，黑龍江 哈爾濱 150001；2. 中國(guó)科學(xué)院 計(jì)算技術(shù)研究所，北京 100190)

1 引言

數(shù)據(jù)壓縮是指在一定的數(shù)據(jù)存儲(chǔ)空間要求下，將相對(duì)龐大的原始數(shù)據(jù)，重組為滿足前述空間要求的數(shù)據(jù)集合，使得從該數(shù)據(jù)集合中恢復(fù)出來(lái)的信息能夠與原始數(shù)據(jù)相一致，或者能夠獲得與原始數(shù)據(jù)一樣的使用品質(zhì)。數(shù)據(jù)之所以能得到壓縮的原因在于數(shù)據(jù)中存在冗余及數(shù)據(jù)所表示的信息之間存在關(guān)聯(lián)。數(shù)據(jù)壓縮減少了數(shù)據(jù)存儲(chǔ)所需要的空間，從而間接減少了處理數(shù)據(jù)所需要的時(shí)間及資源耗費(fèi)。

編碼是信息處理的基礎(chǔ)，不同國(guó)家和地區(qū)存在著不同的編碼標(biāo)準(zhǔn)，主要為單字節(jié)編碼和多字節(jié)編碼兩種。印歐語(yǔ)系主要采用ASCII編碼。漢字?jǐn)?shù)量巨大，必須采用多字節(jié)編碼才能表示，表示漢語(yǔ)的編碼主要包括GB2312-80、GBK、Unicode編碼、GB18030-2000、BIG5等編碼。

壓縮算法的研究及開(kāi)創(chuàng)性的工作是由西方國(guó)家完成的，因此，幾乎所有數(shù)據(jù)壓縮算法的實(shí)現(xiàn)都是基于單字節(jié)的，這些基于單字節(jié)的數(shù)據(jù)壓縮算法，在處理多字節(jié)編碼的數(shù)據(jù)時(shí)，人為地割裂了數(shù)據(jù)編碼中蘊(yùn)含的語(yǔ)義信息，嚴(yán)重地?fù)p害了壓縮率。對(duì)于基于ASCII的單字節(jié)英文文本，現(xiàn)有的壓縮工具已經(jīng)達(dá)到0.8bpc (bits per char/byte)左右的壓縮率，而對(duì)于中文文本僅能達(dá)到3.0bpc左右，遠(yuǎn)遠(yuǎn)低于英語(yǔ)文本。因此需要針對(duì)中文語(yǔ)言，充分考慮其在編碼、語(yǔ)義方面的特點(diǎn)，研究相應(yīng)的壓縮算法。

數(shù)據(jù)壓縮技術(shù)分為無(wú)損壓縮和有損壓縮兩大類，無(wú)損壓縮技術(shù)通常又分為基于統(tǒng)計(jì)的壓縮技術(shù)及基于字典的壓縮技術(shù)?；诮y(tǒng)計(jì)的壓縮技術(shù)根據(jù)字符在數(shù)據(jù)流中的出現(xiàn)概率對(duì)其進(jìn)行編碼，經(jīng)常出現(xiàn)的字符分配較短的編碼，不常出現(xiàn)的字符分配較長(zhǎng)的編碼，代表性技術(shù)有Huffman編碼、算術(shù)編碼及PPM等?；谧值涞膲嚎s技術(shù)將數(shù)據(jù)流中已經(jīng)出現(xiàn)的字符及字符串放入一字典中，對(duì)于重復(fù)出現(xiàn)的字符及字符串用指向字典中該字符串的指針來(lái)表示，由于指針的長(zhǎng)度小于所代替的字符或字符串長(zhǎng)度，所以能起到壓縮的效果，代表性技術(shù)有LZ77、LZ78等等。

傳統(tǒng)的Huffman編碼[1]根據(jù)字符出現(xiàn)的頻率構(gòu)造編碼，是基于ASCII字符的(character-based)，在編碼過(guò)程中并沒(méi)有產(chǎn)生信息熵的轉(zhuǎn)移，其對(duì)自然語(yǔ)言文本的壓縮效果是有限的，因此通常作為其他壓縮算法的后端模塊或補(bǔ)充。當(dāng)將Huffman編碼擴(kuò)展到基于多個(gè)字符時(shí)，如基于詞(word-based)或基于音節(jié)(syllable-based)時(shí)，Huffman編碼的壓縮率會(huì)大幅度提高，這是因?yàn)槎鄠€(gè)字符的組合造成的概率分布不均衡要比單個(gè)字符要大，從而可能獲得更大的壓縮率。對(duì)于英文文本，基于字符的Huffman編碼的壓縮比能達(dá)到1.7左右，而基于單詞的Huffman編碼能達(dá)到4倍左右的壓縮比[2]，達(dá)到或接近LZ的壓縮效果。基于詞的Huffman編碼不僅能提高壓縮率，同時(shí)，由于其在壓縮過(guò)程中保留了字/詞的語(yǔ)義完整性，不像傳統(tǒng)Huffman編碼方法將文本分為一個(gè)個(gè)字節(jié)，人為地割裂了文本中單詞的語(yǔ)義，因而在壓縮文本的檢索方面可能效果更好，速度更快。MG[3]系統(tǒng)就應(yīng)用了基于單詞的Huffman編碼。

LZ[4-7]系列算法通過(guò)使用編碼器中已經(jīng)出現(xiàn)過(guò)的相應(yīng)匹配數(shù)據(jù)信息替換當(dāng)前數(shù)據(jù)從而實(shí)現(xiàn)壓縮功能。但是，根據(jù)詞頻統(tǒng)計(jì)顯示，漢語(yǔ)文本中單字詞與雙字詞占絕對(duì)多數(shù)，因此，漢語(yǔ)文本中重復(fù)子串不可能很長(zhǎng)[8]，從而使LZ系列算法在中文文本上的壓縮性能大打折扣。盡管LZ系列算法還包括LZ78[5]及LZW[7]，由于LZW的專利權(quán)限制，LZW的使用受到相當(dāng)大的制約，但LZSS[6]就沒(méi)有這些約束，從而更受到各種應(yīng)用的青睞，如LZSSCH[9]等。

PPM[10-11]維護(hù)一統(tǒng)計(jì)模型，該模型根據(jù)字符組合預(yù)測(cè)下一個(gè)字符出現(xiàn)的概率，并由算術(shù)編碼對(duì)該概率進(jìn)行編碼輸出。近年來(lái)，對(duì)PPM算法的研究主要集中在PPM的概率的預(yù)測(cè)模型或PPM的階數(shù)上，而對(duì)基于多字節(jié)的PPM算法研究成果很少。Joaquín Adiego和Pablo de la Fuente[12]采用對(duì)文本中的單詞進(jìn)行重新編碼及將PPM改進(jìn)為基于字/詞的PPM，大大提高了PPM的性能。Peiliang Wu和W. J. Teahan[13]將PPM字符壓縮的基本單元由8bits擴(kuò)展到16bits，獲得了4%～10%的壓縮率的提升。

BWT[14]是按塊批量處理數(shù)據(jù)，其核心思想是先對(duì)字符串輪轉(zhuǎn)后得到的字符矩陣進(jìn)行排序和變換，然后對(duì)變換之后的字符串用MTF變換或RLE進(jìn)行處理，最后使用Huffman或算術(shù)編碼進(jìn)行編碼。對(duì)于英文文本，BWT算法的壓縮效果要遠(yuǎn)好于LZ系列算法，但對(duì)于中文文本，考慮到中文編碼的特殊性及中文語(yǔ)義、語(yǔ)法方面與印歐語(yǔ)系的巨大差異，還需要對(duì)BWT算法在中文文本的壓縮技術(shù)中的適應(yīng)性進(jìn)行深入研究。

2 數(shù)據(jù)流的語(yǔ)義特征

本文將數(shù)據(jù)流定義為以bit或byte為基本單位的二進(jìn)制序列。

在壓縮算法中，數(shù)據(jù)流呈現(xiàn)出兩種特性，一是物理特性，如某種bit或byte值的概率分布、byte值的排列順序、某些bit或byte串在數(shù)據(jù)流上下文中的重復(fù)等等；另一種是語(yǔ)義特征，包括兩方面的含義，一是通過(guò)物理特性體現(xiàn)出來(lái)的語(yǔ)義信息，如字節(jié)值的排列順序不同或由多個(gè)字節(jié)的組合來(lái)表示不同的字符，本質(zhì)上是編碼之間的相互依賴關(guān)系。另一種是產(chǎn)生數(shù)據(jù)流的應(yīng)用本身所蘊(yùn)含的語(yǔ)義，基于此種含義，有的學(xué)者認(rèn)為數(shù)據(jù)壓縮是一個(gè)AI-Hard[15]問(wèn)題。本文所討論的語(yǔ)義特征，主要是指通過(guò)物理特性體現(xiàn)出來(lái)的語(yǔ)義信息。

數(shù)據(jù)壓縮本質(zhì)上是一個(gè)可逆的編碼過(guò)程，數(shù)據(jù)流的語(yǔ)義特征與編碼方式息息相關(guān)，如文本：“科學(xué)院南路2號(hào)計(jì)算所ICT。”，其利用編碼蘊(yùn)含語(yǔ)義的方式有以下幾種：

1) 以字節(jié)為單位的變長(zhǎng)編碼方式

如采用ANSI編碼，即雙字節(jié)編碼方式，上述文本編碼為：“BF C6 D1 A7 D4 BA C4 CF C2 B7 32 BA C5 BC C6 CB E3 CB F9 49 43 54 A1 A3”，其中，中文字符及標(biāo)點(diǎn)符號(hào)占16bit，數(shù)字和英文字符占8bit，其在字節(jié)值、字節(jié)順序及字節(jié)組合中所蘊(yùn)含的語(yǔ)義信息如圖1，其中上圖為原數(shù)據(jù)流編碼，下圖為對(duì)應(yīng)編碼所代表的語(yǔ)義，可以看出，該段數(shù)據(jù)流為雙單字節(jié)相間的二進(jìn)制序列，其字節(jié)值、字節(jié)的排列順序及兩個(gè)字節(jié)的組合是一定的，不可以隨意更改，否則將改變所蘊(yùn)含的語(yǔ)義信息。

圖1 原數(shù)據(jù)流的編碼與語(yǔ)義信息

或者采用混合編碼方式，即某些中文字符與數(shù)字、英文字符用8bit，其他用16bit或24bit進(jìn)行編碼, 維持原排列順序，如圖2。

圖2 壓縮編碼方式與語(yǔ)義信息示例：混合編碼

2) 以字節(jié)為單位的定長(zhǎng)編碼方式

圖3中，每個(gè)字符由一個(gè)字節(jié)表示，且編碼的排列順序與原文本中的字符順序相同，如果使用基于單字節(jié)的壓縮算法進(jìn)行壓縮，在進(jìn)行概率計(jì)算、字符比較時(shí)能充分利用所蘊(yùn)含的語(yǔ)義信息，可獲得最優(yōu)的壓縮性能。

圖3 壓縮編碼方式與語(yǔ)義信息示例：?jiǎn)巫止?jié)編碼

3) 以位為單位的變長(zhǎng)編碼方式

此類編碼方式以Huffman編碼為代表，其根據(jù)概率的不同分別對(duì)字符分配以不同位長(zhǎng)的編碼。

根據(jù)壓縮算法對(duì)數(shù)據(jù)中語(yǔ)義信息的維持效果，可以將壓縮算法分為維持語(yǔ)義的壓縮算法及打亂語(yǔ)義的壓縮算法。這里語(yǔ)義是指以位(單個(gè)bit)或位的組合(多個(gè)bit)所表示的具有明確含義的編碼信息及編碼之間的相互依賴關(guān)系。壓縮算法本質(zhì)上是一種信息的再編碼過(guò)程，維持語(yǔ)義的壓縮算法是指壓縮后的數(shù)據(jù)流依然保持了原數(shù)據(jù)流中編碼本身的獨(dú)立關(guān)系(單個(gè)或多個(gè)bit)及編碼之間的相互依賴關(guān)系。

表1 打亂語(yǔ)義的壓縮算法對(duì)壓縮率的影響

打亂語(yǔ)義壓縮算法的使用，使其他壓縮算法不能或錯(cuò)誤地理解了數(shù)據(jù)流中的語(yǔ)義信息，從而對(duì)壓縮效果造成不利影響。如Gzip壓縮算法聯(lián)合使用LZSS與Huffman算法[16]，由于LZSS打亂了語(yǔ)義，再對(duì)經(jīng)LZSS處理后的數(shù)據(jù)進(jìn)行Huffman壓縮時(shí)，就不能正確理解數(shù)據(jù)中的語(yǔ)義信息。同樣，若對(duì)經(jīng)Huffman編碼的數(shù)據(jù)進(jìn)行LZSS壓縮，由于Huffman輸出結(jié)果是變長(zhǎng)編碼的組合，而LZSS字符串的比較是以字節(jié)為基本單位，以字節(jié)為單位對(duì)不等長(zhǎng)編碼的數(shù)據(jù)進(jìn)行操作，完全割裂了數(shù)據(jù)流中的語(yǔ)義特征，從而嚴(yán)重?fù)p壞了壓縮率。

表1為HitIct Corpus[17]與Canterbury Corpus中5個(gè)文本文件使用Huffman與LZSS的壓縮結(jié)果，其中Huffman與LZSS采用文獻(xiàn)[18]中的代碼，CRecode為本文提出的壓縮算法，CRecode(詞組)包含對(duì)頻率最高的768個(gè)雙字詞組的編碼，單位為bpc。

Huffman與LZSS是兩種不同的壓縮算法，前者是根據(jù)字符的概率分布不平衡原理，而后者是用指針代替數(shù)據(jù)流中的重復(fù)字節(jié)串，兩者的作用本質(zhì)上是互補(bǔ)的，但這有個(gè)前提，是兩種算法要能正確對(duì)對(duì)方的壓縮數(shù)據(jù)進(jìn)行理解，能正確地區(qū)分出語(yǔ)義字符，但是在表1中，由于Huffman與LZSS都為打亂語(yǔ)義的壓縮算法，其壓縮結(jié)果如果再采用另一壓縮算法對(duì)其壓縮，其壓縮性能幾乎沒(méi)有增加，有些反而不增反減，如對(duì)樣本17.txt，單獨(dú)采用Huffman可壓縮掉22%的存儲(chǔ)空間，單獨(dú)采用LZSS可壓縮掉29%，如果先用Huffman算法，再用基于變長(zhǎng)前綴碼的LZSS算法進(jìn)行壓縮，可以減少存儲(chǔ)空間44%(0.22+(1-0.22)×0.29=44%)，即4.48bpc，而表1中兩者結(jié)合最大才5.59 bpc，相差25%，可見(jiàn)語(yǔ)義維持對(duì)壓縮性能的影響是巨大的。

對(duì)于中文壓縮算法的而言，目前普遍的作法是將英文壓縮軟件直接應(yīng)用到中文數(shù)據(jù)上，但是由于中英文編碼方式的不同，英文使用的是單字節(jié)的ASCII編碼，采用基于單字節(jié)的壓縮算法，本質(zhì)是符合英文數(shù)據(jù)流的語(yǔ)義要求的，若將其直接用于中文數(shù)據(jù)流上，由于中文采用多字節(jié)編碼，算法從物理上割裂了編碼中蘊(yùn)含的語(yǔ)義信息，從而可能降低壓縮率。

第二種作法是擴(kuò)大壓縮算法運(yùn)算的基本單位，如將字符比較及字符概率計(jì)算的基本單位擴(kuò)大到多字節(jié)方式，這種方式對(duì)于基于統(tǒng)計(jì)的壓縮算法來(lái)講，能較大的提高算法的壓縮率，但對(duì)于基于字典的壓縮算法來(lái)講，反而降低了壓縮率。

第三種方法是考慮中文大字符集的特點(diǎn)，對(duì)漢字進(jìn)行重新編碼，形成基于“中文字符”的Huffman壓縮算法。如Ong[19]根據(jù)被壓縮文本中漢字的頻率分布，為漢字分配4到20bits長(zhǎng)的碼字。Vines和Zobel實(shí)現(xiàn)了一個(gè)基于大規(guī)模的漢語(yǔ)語(yǔ)料庫(kù)的漢語(yǔ)文本的壓縮算法[20]，該算法壓縮性能很高，平均壓縮比達(dá)到2.25(3.56bpc)。

我們知道，數(shù)據(jù)流中所包含的信息量由熵和算法信息內(nèi)容KCC組成，其和為常量或近似于常量[21]，對(duì)信息的先驗(yàn)知識(shí)了解越多，壓縮效果就越好。因此，好的壓縮算法必須能充分利用數(shù)據(jù)流中的熵和KCC信息，而KCC與語(yǔ)義信息密切相關(guān)，在信息熵一定的情況下，對(duì)數(shù)據(jù)流中的語(yǔ)義信息理解、利用的越多，取得的壓縮效果也就越好。上述三種方法，第一種方法直接將中文數(shù)據(jù)單字節(jié)化，以壓縮ASCII編碼數(shù)據(jù)的方式壓縮ANSI編碼的中文數(shù)據(jù)，其結(jié)果是不能充分利用中文數(shù)據(jù)流中蘊(yùn)含的字符級(jí)的語(yǔ)義信息(ANSI編碼的中文數(shù)據(jù)以雙字節(jié)表示一個(gè)漢字，字母數(shù)字等以單字節(jié)來(lái)表示，其語(yǔ)義大多以雙字節(jié)之間的關(guān)系或單雙字節(jié)之間的關(guān)系來(lái)表示)。第二種方法單純將基于字節(jié)的壓縮算法擴(kuò)展為基于字符的壓縮算法，在應(yīng)用到基于統(tǒng)計(jì)的壓縮算法上如Huffman編碼時(shí)，雖然能提高壓縮率，但由于其將Huffman編碼的字符數(shù)從8 bits 256個(gè)字符擴(kuò)展到16 bits 65 536個(gè)字符，對(duì)應(yīng)的Huffman樹(shù)的節(jié)點(diǎn)數(shù)目增加了256倍，從而極大地降低了壓縮速度。另外，要達(dá)到最優(yōu)的壓縮效果，必須兼顧考慮數(shù)據(jù)流中的熵和KCC信息，聯(lián)合運(yùn)用多種基本壓縮算法對(duì)數(shù)據(jù)進(jìn)行壓縮，而后兩種方法，由于其壓縮結(jié)果是變長(zhǎng)的bit流，已經(jīng)不具有字符意義(基于字節(jié))，其基于字節(jié)的概率分布已接近于隨機(jī)數(shù)據(jù)，不再有壓縮的余地。

可見(jiàn)，理想的中文數(shù)據(jù)流壓縮算法應(yīng)該至少具有兩個(gè)特點(diǎn)：一是能維持并充分利用數(shù)據(jù)流的語(yǔ)義信息，二是充分兼容當(dāng)前各種壓縮算法/工具。

3 CRecode壓縮算法

無(wú)損壓縮算法的理論依據(jù)包括：字符概率分布的不平衡原理、利用數(shù)據(jù)流上下文中字符串的重復(fù)信息進(jìn)行熵轉(zhuǎn)移、挖掘語(yǔ)義信息等，這些特征，在所用源自應(yīng)用的數(shù)據(jù)流中都是存在的，但對(duì)于中文數(shù)據(jù)流來(lái)講，還表現(xiàn)出與英文數(shù)據(jù)流不同的特征：

1) 編碼特征，中文是雙字節(jié)編碼，而英文是單字節(jié)編碼，因此壓縮算法為保持?jǐn)?shù)據(jù)流中的語(yǔ)義信息，必須能處理雙字節(jié)編碼。

2) 構(gòu)成英文的基本單位為字母，只有26個(gè)，而構(gòu)成中文的基本單位為字，僅GB2312中的漢字就達(dá)6 763個(gè)，因此，每種語(yǔ)言基本單位中所含的信息量是不同的。

3) 中文字詞概率分布的不平衡有著與其他語(yǔ)言不同的特點(diǎn)[22]。表2為本文統(tǒng)計(jì)的部分ANSI編碼格式的中文文本文件中字符的分布情況，可以看出，前128(該數(shù)字由CRecode的編碼方式?jīng)Q定)個(gè)字符的字頻達(dá)到50%以上，前240個(gè)達(dá)60%以上，前2 288個(gè)97%以上。

4) Huffman編碼的固有缺陷：Huffman編碼在字符的分布概率等于1/2的整數(shù)冪時(shí)壓縮效果最好，如果字符的分布概率與1/2的整數(shù)冪相差較大時(shí)性能會(huì)很差[24]。另外，Huffman編碼為變長(zhǎng)編碼，其輸出結(jié)果不易被其他壓縮算法再處理。

表2 中文文本中字符的分布情況

為充分考慮中文數(shù)據(jù)流的特點(diǎn)，克服連續(xù)變長(zhǎng)編碼如Huffman編碼的固有缺陷，增強(qiáng)統(tǒng)計(jì)編碼與其他壓縮算法的結(jié)合性，本文提出了CRecode壓縮算法。該算法采用非連續(xù)變長(zhǎng)編碼方式，即根據(jù)數(shù)據(jù)流中的字符頻率分布，分別分配8、16最多24位長(zhǎng)的編碼，最大限度保持其語(yǔ)義特征。

3.1 CRecode壓縮數(shù)據(jù)格式

CRecode數(shù)據(jù)格式見(jiàn)圖4。

圖4 CRecode壓縮數(shù)據(jù)格式

FFFF：16 bit CRecode壓縮文件標(biāo)識(shí)，供解碼器判斷是否為CRecode壓縮文件。

Stream Flag：8 bit流標(biāo)識(shí)，用于區(qū)別數(shù)據(jù)流壓縮方式，0x00為ANSI編碼中文數(shù)據(jù)流靜態(tài)壓縮方式，0x01為ANSI編碼中文數(shù)據(jù)流動(dòng)態(tài)壓縮方式。

Char LEN：16 bit字符字典長(zhǎng)度，即字符個(gè)數(shù)；若Stream Flag為0x00靜態(tài)壓縮方式，則該域?yàn)? bit，域值為靜態(tài)編碼字典指針。

Phrase LEN：16 bit短語(yǔ)/詞組字典長(zhǎng)度，若為0x0000則無(wú)短語(yǔ)/詞組字典。中文數(shù)據(jù)流基本上是由詞組組成，以詞組為單位進(jìn)行壓縮則能獲得更大的壓縮率。

Character Dictionary：字符碼表，以在數(shù)據(jù)流中出現(xiàn)的頻率由大到小排列，每個(gè)碼字16 bit。

Phrase Dictionary：若Phrase LEN域不為0x0000，則表示支持詞組編碼。該域的第一字節(jié)為詞組長(zhǎng)度標(biāo)識(shí)，用于標(biāo)識(shí)雙字詞與多字詞。若為0x00則為雙字詞，若為0x01則含有多字詞，在這種情況下，該標(biāo)志后2 byte指未雙字詞長(zhǎng)度，然后為32 bit雙字詞組，以頻率排序，以此類推。

Data：為壓縮數(shù)據(jù)。

EOF：16 bit數(shù)據(jù)結(jié)束標(biāo)記。

MD5：128 bit MD5校驗(yàn)值，校驗(yàn)壓縮數(shù)據(jù)完整性。

3.2 CRecode對(duì)ANSI編碼中文數(shù)據(jù)流的壓縮算法

CRecode有靜態(tài)及動(dòng)態(tài)兩種壓縮方式，根據(jù)用戶對(duì)壓縮速度及壓縮率的要求，可以指定壓縮方式。靜態(tài)壓縮方式使用CRecode自帶的根據(jù)漢語(yǔ)頻率字典中統(tǒng)計(jì)的字、詞使用頻率建立的編碼字典，速度快，不需要傳輸碼表。動(dòng)態(tài)編碼根據(jù)數(shù)據(jù)流動(dòng)態(tài)統(tǒng)計(jì)字、詞頻率，需要對(duì)壓縮數(shù)據(jù)進(jìn)行二遍掃描，速度慢，但壓縮效果好。動(dòng)態(tài)方式由于要傳輸碼表，在文件較小的情況有可能壓縮率不及靜態(tài)方式，這時(shí)可能由用戶指定壓縮方式，或由CRecode對(duì)兩種方式下的壓縮率進(jìn)行比較，自動(dòng)選擇最佳方式。

CRecode對(duì)字符及詞組進(jìn)行編碼時(shí)，先對(duì)壓縮數(shù)據(jù)進(jìn)行掃描，統(tǒng)計(jì)出字符及詞組的使用頻率，按使用頻率自大到小分別排序，然后根據(jù)每個(gè)字符/詞組在排序表中的索引進(jìn)行編碼。輸出時(shí)，先輸出CRecode壓縮文件標(biāo)識(shí)FFFF，然后依次輸出前面定義的相關(guān)標(biāo)識(shí)字段、字編碼表長(zhǎng)度、詞組編碼表長(zhǎng)度，再依次輸出排序表中的字符及詞組(只輸出字符/詞組原編碼)，最后是壓縮數(shù)據(jù)、壓縮文件結(jié)束標(biāo)志EOF、MD5校驗(yàn)值。編碼格式見(jiàn)表3、表4。

3.3 解壓縮算法

CRecode讀入數(shù)據(jù)，首先根據(jù)數(shù)據(jù)流的前兩字節(jié)的值判斷是否為CRecode壓縮數(shù)據(jù)，若不是CRecode壓縮數(shù)據(jù)則不做任何操作，原樣輸出數(shù)據(jù)，否則，根據(jù)流標(biāo)識(shí)判斷是哪種壓縮方式，如果是靜態(tài)壓縮方式，則根據(jù)自帶的碼表解碼，如果為動(dòng)態(tài)壓縮方式，則依次讀入字、詞組碼表長(zhǎng)度，字詞碼表，然后讀入數(shù)據(jù)進(jìn)行解壓縮。解壓縮時(shí)根據(jù)數(shù)據(jù)的第一字節(jié)的值，確定該碼字的字節(jié)數(shù)，然后根據(jù)該碼字求出碼表的索引值，最后輸出碼表中該位置的編碼，循環(huán)往復(fù)。

表3 字符編碼表(不含詞組)

表4 字符編碼表(含詞組)

3.4 性能分析

對(duì)于表3所示的編碼方式，CRecode根據(jù)字符的使用頻率對(duì)字符重新編碼，使用頻率最高的240個(gè)字符采用8位編碼，根據(jù)總字符數(shù)是否大于 4 336，其他字符分別采用16位或24位編碼。

令測(cè)試文件中的字符總數(shù)為N(對(duì)于GB2312，N<7 445)，其中單字節(jié)編碼字符的數(shù)量為N0個(gè)(對(duì)于GB2312，N0< 588)，fi為每個(gè)字符的使用頻率，則可以求出CRecode編碼的累積熵(壓縮率bpc)為：

其中，S為測(cè)試文件的字節(jié)數(shù)，S=1×N0+2×(N-N0)。

進(jìn)一步設(shè)使用頻率索引值≤240的單字節(jié)編碼字符數(shù)為N1個(gè)，為計(jì)算方便，假定其索引值為0到(N1-1)，使用頻率索引值在區(qū)間(240，2 288)上的單字節(jié)編碼字符數(shù)為N2個(gè)，假定其索引值為240到(239+N2)，則使用頻率索引值大于2 287的單字節(jié)編碼字符數(shù)為(N0-N1-N2)個(gè)，假定其索引值為 2 288 到N3(N3=2 287+N0-N1-N2)，fi為每一個(gè)詞或符號(hào)的出現(xiàn)頻率，則CRecode編碼節(jié)省的比特?cái)?shù)為：

如果βCRecode>0，有

即使用頻率最多的中文字符采用單字節(jié)編碼所節(jié)省的比特總數(shù)大于單字節(jié)字符采用雙字節(jié)或三字節(jié)編碼、與中文字符采用三字節(jié)編碼所浪費(fèi)的比特?cái)?shù)之和時(shí)，CRecode具有壓縮效果，βCRecode越大，壓縮率越高。

顯然，CRecode對(duì)壓縮率的貢獻(xiàn)主要由頻率最高的240個(gè)字符來(lái)完成，由表2看出，前240個(gè)字符的頻率占總字符的70%左右，將其由16位重編碼為8位，可節(jié)省35%左右的存儲(chǔ)空間，由于前4 336個(gè)字符所占比例幾乎已是100%，故采用24位編碼的字符對(duì)壓縮率的負(fù)面影響可以忽略不計(jì)。

CRecode在與Huffman算法結(jié)合時(shí)，由于CRecode只是根據(jù)使用頻率對(duì)各個(gè)字符進(jìn)行了重編碼，重編碼后的各字符的使用頻率并沒(méi)有發(fā)生改變，只是某些字符的編碼由16位變成了8位或24位，字符的概率分布不平衡狀態(tài)并沒(méi)有改變，因此，CRecode與Huffman結(jié)合，并不會(huì)影響Huffman算法性能的發(fā)揮。

當(dāng)CRecode與LZSS結(jié)合時(shí)，CRecode是一種基于統(tǒng)計(jì)的壓縮算法，其與LZSS的作用是互補(bǔ)的，CRecode的輸出格式為一到三字節(jié)的多字節(jié)混合編碼方式，完整地保留了原數(shù)據(jù)流中蘊(yùn)含的語(yǔ)義信息，包括字符串在上下文的重復(fù)信息等，因而，CRecode在與LZSS結(jié)合時(shí)仍能取得相當(dāng)好的壓縮效果。

CRecode在與PPM、BWT結(jié)合時(shí)，相當(dāng)于對(duì)數(shù)據(jù)流進(jìn)行了一遍預(yù)處理，CRecode的壓縮結(jié)果并不影響產(chǎn)生數(shù)據(jù)流的應(yīng)用中字符的使用頻率及相對(duì)順序，再采用PPM、BWT壓縮時(shí)基本不會(huì)對(duì)PPM的概率預(yù)測(cè)機(jī)制及BWT的字符轉(zhuǎn)換機(jī)制產(chǎn)生大的影響，因此，其對(duì)數(shù)據(jù)的壓縮效果依然可以保持。

由此可見(jiàn)，由于CRecode能充分維持?jǐn)?shù)據(jù)流中蘊(yùn)含的語(yǔ)義信息，其在與其他基于字節(jié)的算法結(jié)合使用時(shí)，可以在保持CRecode算法本身所獲得的壓縮效果的前提下，不影響其他算法壓縮性能的發(fā)揮，從而提高了整體壓縮率。

對(duì)于CRecode的動(dòng)態(tài)方式，其碼表所占用儲(chǔ)存空間=字符數(shù)×2 Bytes，平均碼表空間在7KB左右。動(dòng)態(tài)方式需預(yù)掃描一遍文件，統(tǒng)計(jì)字符頻率，按頻率對(duì)字符進(jìn)行排序，然后再掃描文件編碼輸出，時(shí)間復(fù)雜度為O(nlog2n)(堆排序，n為字符個(gè)數(shù))，CRecode的靜態(tài)方式只需在編碼過(guò)程中檢索碼表，時(shí)間復(fù)雜度為O(n)。CRecode的解碼算法只需要根據(jù)讀入的碼字檢索碼表，進(jìn)行編碼替換，速度非?？欤瑫r(shí)間復(fù)雜度為O(n)。CRecode支持部分解壓縮。

4 CRecode性能測(cè)試

CRecode主要功能在于它能對(duì)中文數(shù)據(jù)流進(jìn)行預(yù)處理，壓縮數(shù)據(jù)流中的部分信息冗余，并能保持?jǐn)?shù)據(jù)流中所蘊(yùn)含的語(yǔ)義信息，以便使用現(xiàn)有各種基于單字節(jié)的壓縮工具進(jìn)行進(jìn)一步壓縮，從而獲得更好的壓縮率。從表1可以看出，當(dāng)CRecode獨(dú)立使用時(shí)，它的性能比Huffman編碼要好，略差于LZSS算法。

表1還顯示，當(dāng)將CRecode編碼的基本單位擴(kuò)展到詞組時(shí)，其對(duì)壓縮率的影響有限，這是由于CRecode的壓縮原理在于將出現(xiàn)頻率最多的240個(gè)字符用8bit代替原編碼中的16bit編碼，大部分字符仍然采用16bit編碼，極少數(shù)使用24bit編碼，起壓縮作用的只是前240個(gè)字符。如果使用詞組編碼，由于詞組的碼表要占用較大的空間，且由于詞組的編碼占用了有限的16bit碼段，必然將一部分字符及詞組的編碼擠到24bit編碼段，壓縮率的大小取決于字符與詞組個(gè)數(shù)與頻率。同時(shí)由于詞組的查找要占用大量的計(jì)算資源，致使編碼極慢，得不償失。

表5給出了HitIct Corpus中相關(guān)文本文件與90.txt在不同壓縮算法下的壓縮率，單位為bpc，測(cè)試軟件為Huffman、LZSS、WinRAR 3.71 官方簡(jiǎn)體中文版、gzip v1.2.4 win32、bzip2 v1.0.4、PPMVC v1.2、WinRK v3.1.2。

Ong[19]的多級(jí)4-bit編碼(OngCode)對(duì)字符按頻率進(jìn)行4、8、12、16及20bits的編碼方式， 為了比較CRecode編碼方式與OngCode在與其他壓縮工具結(jié)合時(shí)的性能優(yōu)劣，表5列出了選自HitIct Corpus中的3個(gè)文本文件及90.txt(該文件為18M的外國(guó)文學(xué)合集)分別由CRecode和OngCode處理后再由其他壓縮軟件壓縮后壓縮率的變化情況。

表5 不同壓縮算法與CRecode和OngCode結(jié)合后的壓縮率變化情況(提高百分比)

可以看出，CRecode和OngCode在與基本壓縮算法Huffman和LZSS結(jié)合時(shí)都較大的提高了總體壓縮率，但在與其他壓縮工具結(jié)合時(shí)，CRecode的性能遠(yuǎn)高于OngCode，與OngCode結(jié)合的性能不升反降，最大降低了12.33%，這說(shuō)明雖然OngCode的多級(jí)4-bit編碼方式提高了碼位的利用率，但是由于它的4、12、20比特碼長(zhǎng)打亂了以8bits為單位的字節(jié)邊界，對(duì)蘊(yùn)含在數(shù)據(jù)流中的語(yǔ)義造成破壞，從而降低了壓縮率，其本質(zhì)上是一種打亂語(yǔ)義的壓縮方式。

圖5 CRecode、OngCode、Huffman、LZSS壓縮率比較

CRecode包含8、16、24位三種碼長(zhǎng)，OngCode包含4、8、12、16、20位五種碼長(zhǎng)，兩者都屬于非連續(xù)變長(zhǎng)編碼，而Huffman屬于連續(xù)變長(zhǎng)編碼方式，圖5為三種編碼方式單獨(dú)使用時(shí)的壓縮率示意圖，可見(jiàn)，單獨(dú)使用時(shí)，OngCode的性能最好，CRecode次之，Huffman最差。

為了進(jìn)一步測(cè)試CCRecode的性能，我們用建立HitIct Corpus時(shí)所用的當(dāng)代文學(xué)測(cè)試樣本對(duì)CRecode編碼與4個(gè)壓縮工具的結(jié)合性能進(jìn)行了測(cè)試，該樣本集包含90個(gè)文本文件，大小分布在117KB與18M之間，總大小256M，全部來(lái)自互聯(lián)網(wǎng)。獲得的測(cè)試結(jié)果如表6所示。

由此可見(jiàn)，對(duì)于中文文本，經(jīng)CRecode編碼后Huffman編碼可獲得20%～30%的性能提升，LZSS、 gzip、 WinRAR、 bzip2、PPMVC可分別平均獲得20%、10%、7%、4%及4%以上的性能提高，在與PPMVC算法結(jié)合時(shí)獲得了最大2.26bpc、平均2.80bpc的壓縮率(即壓縮比最大3.54、平均 2.86)，具有很高的應(yīng)用價(jià)值，完全可以做為通用壓縮工具的中文數(shù)據(jù)流壓縮接口。

表6 CRecode在90個(gè)樣本上的結(jié)合性能測(cè)試結(jié)果

5 結(jié)論

本文介紹了一個(gè)能對(duì)中文數(shù)據(jù)流進(jìn)行預(yù)處理的壓縮算法CRecode，它克服了Huffman算法在壓縮中文數(shù)據(jù)流時(shí)打亂數(shù)據(jù)中蘊(yùn)含的語(yǔ)義信息及在字符分布概率偏離1/2的整數(shù)冪時(shí)性能下降的缺陷，能與各種壓縮算法、壓縮軟件配合使用，使其壓縮性能提高4%～30%，平均壓縮率最大可達(dá)2.80bpc，即 2.86 的壓縮比。CRecode本質(zhì)上是一種熵編碼方式，本文的創(chuàng)新意義在于，采用三級(jí)8比特編碼方式避免了熵編碼方式對(duì)其他冗余信息的損壞(即維持了語(yǔ)義)，在對(duì)數(shù)據(jù)流中的編碼冗余進(jìn)行適度壓縮的前提下又保持了對(duì)其他壓縮算法的兼容性，最終提高了壓縮率。在實(shí)驗(yàn)中我們還發(fā)現(xiàn)，雖然WinRK是目前文本壓縮領(lǐng)域最優(yōu)秀的壓縮工具[24]，但其在中文文本文件的壓縮性能卻遠(yuǎn)遜于PPMVC，甚至于bzip2，這更說(shuō)明了對(duì)編碼冗余進(jìn)行預(yù)消除的重要性，這也是CRecode的最大貢獻(xiàn)，而事實(shí)上，對(duì)數(shù)據(jù)流進(jìn)行預(yù)處理正是當(dāng)前無(wú)損壓縮領(lǐng)域的研究熱點(diǎn)之一。實(shí)驗(yàn)表明，CRecode作為獨(dú)立壓縮算法，可獲得優(yōu)于Huffman編碼、近似于LZ系列算法的性能。

[1] Huffman, D. A. A Method for the Construction of Minimum-Redundancy Codes [C]//Proc. IRE 40, 9 (Sept.), 1952: 1098-1101.

[2] Ziviani, N., Moura, E., Navarro, G., & Baeza-Yates, R. Compression: a key for next-generation text retrieval systems[J].IEEE Computer, 2000, 33(11): 37-44.

[3] Witten, I., Moffat, A., & Bell, T. Managing gigabytes 2nd [M]. Morgan Kaufmann Publishers. 1999.

[4] Ziv, J., and Lempel, A. A Universal Algorithm for Sequential Data Compression [J]. IEEE Transactions on Information Theory, 1977, 23(3): 337-343.

[5] Ziv, J., and Lempel, A. Compression of Individual Sequences via Variable-Rate Coding [J]. IEEE Transactions on Information Theory,1978,24(5):530-536.

[6] J. A. Storer and T. G. Szymanski. Data Compression via Textual Substitution [J]. Journal of the ACM, 1982, 29: 928-951.

[7] Welch, T. A. A Technique for High-Performance Data Compression [J]. Computer, 1978, 17(6): 8-19.

[8] 王忠效．漢語(yǔ)文本壓縮研究及其應(yīng)用[J]．中文信息學(xué)報(bào)，1997，11(3)：57-64.

[9] 華強(qiáng). 中文文本壓縮的LZSSCH算法[J]. 中文信息學(xué)報(bào), 1998, 12(1): 50-56

[10] T. Bell, J. Cleary, and I. Witten. Data compression using adaptive coding and partial string matching [J]. In: IEEE Transactions on Communications, 1984, 32 (4): 396-402.

[11] A. Moffat. Implementing the PPM data compression scheme [J]. IEEE Transactions on Communications, 1990, 38 (11): 1917-1921.

[12] Joaquín Adiego and Pablo de la Fuente. On the Use of Words as Source Alphabet Symbols in PPM [C]//Data Compression Conference (DCC’06), 2006: 435.

[13] Peiliang Wu, W. J. Teahan. Modelling Chinese For Text Compression [C]//Data Compression Conference (DCC’05), 2005: 488-488.

[14] M. Burrows and D. J. Wheeler. A Block-sorting Lossless Data Compression Algorithm [R]. Digital Systems Research Center Research Report 124, May 1994.

[15] Matt Mahoney. Rationale for a Large Text Compression Benchmark[EB/OL]. Online. Internet. Available from http://www.cs.fit.edu/～mmahoney/compression/rationale.html, 5, Jan. 2008.

[16] P. Deutsch. RFC1951: DEFLATE Compressed Data Format Specification version 1.3 [Z]. 1995.

[17] 常為領(lǐng), 云曉春, 方濱興, 王樹(shù)鵬. HitIct: 中文無(wú)損壓縮算法性能評(píng)估測(cè)試集[J]. 通信學(xué)報(bào),2009,30(3):42-47.

[18] Nelson M., Gailly J. The Data Compression Book, 2nd edition[M].M&T Books,New York,NY,1995.

[19] Ghim Hwee Ong and Shell Ying Huang. Compression of Chinese Text Files Using a Multiple Four-Bit Coding Scheme [C]//IEEE Singapore ICCS/ISITA ’92, Nov. 1992：1062-1066.

[20] Phil Vines, Justin Zobel, Compression Techniques for Chinese Text [J]. Software-Practice and Experience, 1998, 28(12):1299-1314.

[21] David Salomon. Data compression: The Complete Reference, Third Edition [M]. New York : Springer, 2004: 134-155.

[22] 北京語(yǔ)言學(xué)院語(yǔ)言教學(xué)研究所．漢語(yǔ)詞匯的統(tǒng)計(jì)與分析[M]．北京: 外語(yǔ)教學(xué)與研究出版社，1985.

[23] Wikipedia, the free encyclopedia. Huffman coding[BE/OL]. Online. Internet. Available from http://en.wikipedia.org/wiki/Huffman_coding. May 2010.

[24] Maximum Compression’s English Text compression test[BE/OL].Online.Internet.Available from http://www.maximumcompression.com,3,Sept.2009.