付敏，戴祖旭，王道蓬

1 武漢工程大學(xué)理學(xué)院，湖北 武漢 430502；2 華中科技大學(xué)圖像識別與人工智能研究所多譜圖像信息處理國防重點(diǎn)實(shí)驗(yàn)室，湖北 武漢 430074

壓縮編碼的上下文樹構(gòu)造算法

付敏1，2，戴祖旭1，王道蓬2

1 武漢工程大學(xué)理學(xué)院，湖北 武漢 430502；2 華中科技大學(xué)圖像識別與人工智能研究所多譜圖像信息處理國防重點(diǎn)實(shí)驗(yàn)室，湖北 武漢 430074

上下文樹是構(gòu)造無算壓縮算法的一種重要基礎(chǔ)，作為信息處理過程分析隨機(jī)序列統(tǒng)計特性的常用數(shù)據(jù)結(jié)構(gòu)，隨機(jī)序列中的符號來自于某個固定的符號集合.上下文樹一般是一棵n元樹，其中n大于1，但是樹是一種占用計算機(jī)內(nèi)存較多的數(shù)據(jù)結(jié)構(gòu)，因此提出了基于壓縮編碼的上下文樹構(gòu)造算法，根據(jù)符號的一階統(tǒng)計特性對符號做二進(jìn)制的壓縮編碼，用二元樹代替n（n＞2）元樹，在相同內(nèi)存的存儲空間下，可以大大增加樹的高度.計算機(jī)數(shù)值實(shí)驗(yàn)表明基于壓縮編碼的上下樹構(gòu)造對子串做出了更大長度的相關(guān)性檢測，并且提高了數(shù)據(jù)分析的精度.

上下文樹；n元樹；壓縮編碼

0 引言

信息處理技術(shù)的飛速發(fā)展使得算法應(yīng)用越來越為廣泛，在圖像處理［1］，路徑搜索優(yōu)化［2-3］以及工程應(yīng)用等領(lǐng)域，數(shù)學(xué)形態(tài)學(xué)越來越重要.作為其中的一種重要的數(shù)據(jù)結(jié)構(gòu)，上下文樹是信息處理過程中分析隨機(jī)序列統(tǒng)計特性的常用工具.利用上下文樹獲取序列中字符串［4-5］的頻率分布，可以構(gòu)造高效的數(shù)據(jù)壓縮算法［6-7］，通過上下文樹分析文本或生物DNA序列中符號的相關(guān)性，可以準(zhǔn)確實(shí)現(xiàn)文檔或DNA序列的自動分段［8-9］.同時，上下文樹也是研究可變長Markov鏈的主要數(shù)學(xué)工具，用于隨機(jī)序列發(fā)生器設(shè)計［10-11］.

隨機(jī)序列中的符號來自于某個固定的符號集合，比如英文文檔包括26個字母，DNA序列由A、C、G、T組成，它們分別代表組成DNA的四種核苷酸一腺嘌呤、胞嘧啶、鳥嘌呤和胸腺嘧啶．因此上下文樹一般是一棵n元樹，其中n大于1.樹是一種占用計算機(jī)內(nèi)存較多的數(shù)據(jù)結(jié)構(gòu)，系統(tǒng)內(nèi)存容量會直接影響樹的高度，而樹高決定了分析過程中序列子字符串的長度，會直接影響符號串統(tǒng)計特性的精度.

本文提出了基于壓縮編碼的上下文樹構(gòu)造算法，根據(jù)符號的一階統(tǒng)計特性對符號做二進(jìn)制的壓縮編碼，用二元樹代替n（n＞2）元樹，在相同內(nèi)存的存儲空間下，可以大大增加樹的高度，對子串做更大長度的相關(guān)性檢測，提高分析的精度.

1 上下文樹

設(shè)A＝｛a1，a2，…，an｝是一個符號集合，隨機(jī)序列x＝x－Nx－N＋1…x－1x0x1…xMxi∈A，i∈I從序列x中任取一點(diǎn)，比如x0，向左回溯，找到x＝x－jx－j＋1…x－1x0，其中0≤J≤N，使得條件概率為

成立，設(shè)x＝x－jx－j＋1…x－1x0為x1的上下文環(huán)境. x1的上下文環(huán)境說明了影響符號x1的出現(xiàn)的歷史追溯到x－J即可，不必再回溯到x－J－1以及更早的符號.要驗(yàn)證式（1）中的n個等式，需要根據(jù)序列x統(tǒng)計出字符串x－j－1x－j…x－1x0x和x－jx－j＋1…x－1x0x出現(xiàn)的頻數(shù).統(tǒng)計頻數(shù)的工作由如下的上下文樹算法完成.

算法1：上下文樹構(gòu)造算法：

（1）初始化根節(jié)點(diǎn)，符號計數(shù)設(shè)置為0.

（2）假設(shè)根據(jù)字符串xt＝x1x2…xt構(gòu)造出樹Tt，當(dāng)前輸入符號為xt＋1，從根節(jié)點(diǎn)出發(fā)，按照字符串xtxt－1…的指引，訪問Tt的結(jié)點(diǎn)，直到xt的符號用完，或者到了葉子結(jié)點(diǎn).對每個訪問到的結(jié)點(diǎn)，將該結(jié)點(diǎn)處的符號xt＋1的計數(shù)增加1.

（3）如果最后一次訪問到的結(jié)點(diǎn)xt＋1處的計數(shù)≥2，創(chuàng)建一個新結(jié)點(diǎn)xt…xt－j＋1xt－j，新結(jié)點(diǎn)xt＋1處的計數(shù)置為1，其他符號的計數(shù)置為0，得到樹Tt＋1.

從上下文樹構(gòu)造算法可知，樹Tt是一棵n元樹，其高度隨著從左到右掃描序列的時刻t增加而增加.n元樹結(jié)點(diǎn)個數(shù)有如下性質(zhì)：

命題2：高度為h的n元滿樹的長度為l（l≤h）的字符串個數(shù)為nl個.

2 基于壓縮編碼的上下文樹算法

由于隨機(jī)序列中符號出現(xiàn)的概率是非均勻分布的，利用熵壓縮編碼的原理可以對符號進(jìn)行二進(jìn)制變長壓縮編碼，二進(jìn)制符號作為碼元符號，隨機(jī)序列中的自然語言符號可編碼為變長的二進(jìn)制串.本文在構(gòu)建上下文樹的時候，樹的結(jié)點(diǎn)不是自然語言符號，而是僅含0，1的二元樹，每個自然語言符號都對應(yīng)著二元樹上的一段路徑.

算法2：基于壓縮編碼的上下文樹算法.

（1）統(tǒng)計隨機(jī)序列的符號的頻率，構(gòu)造Huffman編碼，形成碼表，用B（xi）表示自然語言符號x對應(yīng)的二進(jìn)制串.

（2）初始化根結(jié)點(diǎn)，符號計數(shù)置為0，令t時刻自然語言符號序列為xt＝x1x2…xt.

（3）假設(shè)根據(jù)字符串xt＝x1x2…xt構(gòu)造出樹Tt，當(dāng)前輸入為xt＋1，從根結(jié)點(diǎn)出發(fā)，按照字符xtxt－1…的指引，訪問Tt的結(jié)點(diǎn)，直到xt的符號用完，或者到了葉子結(jié)點(diǎn)，比如B（xt）…B（xt－j＋1）.對每個訪問到的結(jié)點(diǎn)，將該結(jié)點(diǎn)處符號xt＋1的計數(shù)增加1.

（4）如果最后一次訪問到的結(jié)點(diǎn)xt＋1處的計數(shù)≥2，創(chuàng)建一個新結(jié)點(diǎn)B（xt）…B（xt－j＋1）B（xt－j），新結(jié)點(diǎn)處xt＋1的計數(shù)置為1，其他符號的計數(shù)置為0，得到樹Tt＋1.

基于壓縮編碼的上下文樹算法與上下文樹算法不同點(diǎn)在于，將n元樹化為二元樹，n元樹中的每個結(jié)點(diǎn)在二元樹中擴(kuò)展為一條路徑.該路徑對應(yīng)著自然語言符號的Huffman編碼.下面的結(jié)論表明，將n元樹化為二元樹，在表達(dá)相同數(shù)量的自然語言字符串情況下占用的內(nèi)存卻大大減少了.

命題3：設(shè)n元樹的每個節(jié)點(diǎn)指針域占用字節(jié)數(shù)為d，數(shù)據(jù)域占用字節(jié)數(shù)為m，對n個符號采用二進(jìn)制編碼，平均碼長為l0．則高度為h的n元滿樹所占用字節(jié)總數(shù)

表1 3個長度為62的字符串1-62階條件概率計算結(jié)果范例Table 1 Computational results of 3 stings'conditional probability

除以nh得到：

故關(guān)于n的不等式（4）有解

也即n≥2時結(jié)論成立.

3 實(shí)驗(yàn)結(jié)果

利用基于壓縮編碼的上下文樹構(gòu)造算法對英文長篇小說《Forrest Gramp》（Winston Groom，1986）開展了統(tǒng)計工作，程序運(yùn)行環(huán)境為32位微軟XP service pack3操作系統(tǒng)，Pentium Dual－Core E6700 CPU，主頻3.20 GHz，內(nèi)存2 GByte分析字符串長度達(dá)到62個自然語言符號時，運(yùn)行時間約34分鐘，統(tǒng)計出共281 705條長度為62的字符串，每個字符串分別計算出從1階到62階條件概率以供后續(xù)分析使用.表1給出了其中的3個計算結(jié)果.

從數(shù)據(jù)統(tǒng)計分析可以看出，符號的一階統(tǒng)計特性可以在數(shù)值實(shí)驗(yàn)中得到，對文本信息的符號做二進(jìn)制的壓縮編碼，在結(jié)構(gòu)處理上采用二元樹代替（＞2）元樹，在相同內(nèi)存的存儲空間下，理論上證明可以增加樹的高度，實(shí)驗(yàn)也進(jìn)一步驗(yàn)證結(jié)論.基于此，可以對長度更大的子串進(jìn)行相關(guān)性檢測，并且提高分析的精度.

［1］洪漢玉，章秀華，程莉.道路病害形態(tài)特征的圖像分析［J］.武漢工程大學(xué)學(xué)報，2014，36（4）：70－76.

HONG Han－yu，ZHANG Xiu－h(huán)ua，CHENG Li.Image analysis method for road disease morphology characteristic［J］.Journal of Wuhan Institute of Technology，2014，36（4）：70－76.（in Chinese）

［2］孫玉昕，章瑾.利用堆排序優(yōu)化路徑搜索效率的分析［J］.武漢工程大學(xué)學(xué)報，2013，35（10）：50－55.

SUN Yu－xin，ZHANG Jin.Practical analysis of improving path searching efficiency by heap sort［J］.Journal of Wuhan Institute of Technology，2013，35（10）：50－55.（in Chinese）

［3］王學(xué)華，劉莉君，馬凡杰，等.數(shù)控激光加工路徑鏈表快速搜索優(yōu)化［J］.武漢工程大學(xué)學(xué)報，2014，36（10）：52－57.

WANG Xue－h(huán)ua，LIU Li－jun，MA Fan－jie et al.Rapid routine searching of numerical control laser processing based on linked list structure［J］.Journal of Wuhan Institute of Technology，2014，36（10）：52－57.（in Chinese）

［4］徐超，周一民，沈磊.一種面向隱含主題的上下文樹核［J］.電子與信息學(xué)報，2010，32（11）：2695－2700.

XU Chao，ZHOU Yi－min，SHEN Lei.A context tree kernel based on latent semantictopic［J］.Journal of Electronics＆Information Technology，2010，32（11）：2695－2606.（in Chinese）

［5］RISSANEN J.A universal data compression system［J］. IEEE Transactions on information theory，1983，29（5）：656－664.

［6］陳亮，孟慶愿，董彥磊，等.CTW無損壓縮算法在管道無損檢測中的應(yīng)用［J］.實(shí)驗(yàn)技術(shù)與管理，2012，29（6）：42－47.

CHEN Liang，MENG Qingyuan，DONG Yanlei，et al. Using CTW lossless compression algorithm in pipelines nondestructive testing［J］.Experimental Technology and Management，2012，29（6）：42－47.（in Chinese）

［7］DUMONT Thierry.Context tree estimation in variable length hidden［J］.IEEE Transactions on information theory，2014，60（6）：3196－3208.

［8］GWADERA R，GIONIS A，MANNILA H.Optimal segmentation using tree models［J］.Knowledge and Information Systems，2008，15（3）：259－283.

［9］Martins D A，Neves A J R，Pinho A J.Variable Order Finite－Context Models in DNA Sequence Coding［C］// PatternRecognitionandImageAnalysis.Springer Berlin Heidelberg，2009：457－464.

［10］BüHLMANN P.Model selection for variable length Markov chains and tuning the context algorithm［J］. Annals of the Institute of Statistical Mathematics，2000，52（2）：287－315.

［11］CéNAC P，CHAUVIN B，PACCAUT F，et al.Context trees，variable length Markov chains and dynamical sources［C］//Séminaire de Probabilités XLIV. Springer Berlin Heidelberg，2012：1－39.

Context tree algorithm based on compression encoding

FU Min1，2，DAI Zu－xu1，WANG Dao－peng2
1.College of Science，Wuhan Institute of Technology，Wuhan 430502，China; 2．Institute of Pattern Recognition and Artificial Intelligence，Multi－spectral Image Information Processing Key Laboratory of National Defense，Huazhong University of Science and Technology，Wuhan 430074，China

The context tree as a commonly used data structure plays a very important role in analyzing statistical characteristics of random sequence，and the random sequence of symbols generally comes from a fixed symbol set．The general context tree is a n－tree，in which n is more than 1．Because the tree is a kind of computer memory wasting data structure，a context tree construction algorithm based on compress coding was presented utilizing the first－order statistical properties of binary symbols．In the numerical experiment under the same memory storage space condition，the tree’s height has been greatly increased，and the accuracy of data analysis also improved．

context tree；n＿gram tree；compression encoding

TP309.7

A

10.3969/j.issn.1674-2869.2015.04.012

1674-2869（2015）04-0056-03

本文編輯：陳小平

2015－01－12

湖北省自然科學(xué)基金重點(diǎn)項(xiàng)目（2010CDA009）；湖北省自然科學(xué)基金一般項(xiàng)目（2009CDB367）；國家自然科學(xué)基金面上項(xiàng)目（61175013）；武漢工程大學(xué)校級教研項(xiàng)目（X2013021）．

付敏（1979－），女，湖北襄陽人，講師，博士研究生.研究方向：信息處理，計算機(jī)視覺.