壓縮編碼的上下文樹構造算法

付敏，戴祖旭，王道蓬

1 武漢工程大學理學院，湖北 武漢 430502；2 華中科技大學圖像識別與人工智能研究所多譜圖像信息處理國防重點實驗室，湖北 武漢 430074

壓縮編碼的上下文樹構造算法

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

1 武漢工程大學理學院，湖北 武漢 430502；2 華中科技大學圖像識別與人工智能研究所多譜圖像信息處理國防重點實驗室，湖北 武漢 430074

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

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

0 引言

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

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

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

1 上下文樹

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

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

算法1：上下文樹構造算法：

（1）初始化根節點，符號計數設置為0.

（2）假設根據字符串xt＝x1x2…xt構造出樹Tt，當前輸入符號為xt＋1，從根節點出發，按照字符串xtxt－1…的指引，訪問Tt的結點，直到xt的符號用完，或者到了葉子結點.對每個訪問到的結點，將該結點處的符號xt＋1的計數增加1.

（3）如果最后一次訪問到的結點xt＋1處的計數≥2，創建一個新結點xt…xt－j＋1xt－j，新結點xt＋1處的計數置為1，其他符號的計數置為0，得到樹Tt＋1.

從上下文樹構造算法可知，樹Tt是一棵n元樹，其高度隨著從左到右掃描序列的時刻t增加而增加.n元樹結點個數有如下性質：

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

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

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

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

（1）統計隨機序列的符號的頻率，構造Huffman編碼，形成碼表，用B（xi）表示自然語言符號x對應的二進制串.

（2）初始化根結點，符號計數置為0，令t時刻自然語言符號序列為xt＝x1x2…xt.

（3）假設根據字符串xt＝x1x2…xt構造出樹Tt，當前輸入為xt＋1，從根結點出發，按照字符xtxt－1…的指引，訪問Tt的結點，直到xt的符號用完，或者到了葉子結點，比如B（xt）…B（xt－j＋1）.對每個訪問到的結點，將該結點處符號xt＋1的計數增加1.

（4）如果最后一次訪問到的結點xt＋1處的計數≥2，創建一個新結點B（xt）…B（xt－j＋1）B（xt－j），新結點處xt＋1的計數置為1，其他符號的計數置為0，得到樹Tt＋1.

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

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

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

除以nh得到：

故關于n的不等式（4）有解

也即n≥2時結論成立.

3 實驗結果

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

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

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

HONG Han－yu，ZHANG Xiu－hua，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］孫玉昕，章瑾.利用堆排序優化路徑搜索效率的分析［J］.武漢工程大學學報，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］王學華，劉莉君，馬凡杰，等.數控激光加工路徑鏈表快速搜索優化［J］.武漢工程大學學報，2014，36（10）：52－57.

WANG Xue－hua，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］.電子與信息學報，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無損壓縮算法在管道無損檢測中的應用［J］.實驗技術與管理，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

湖北省自然科學基金重點項目（2010CDA009）；湖北省自然科學基金一般項目（2009CDB367）；國家自然科學基金面上項目（61175013）；武漢工程大學校級教研項目（X2013021）．

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