一種新的二叉樹結(jié)構(gòu)XML編碼方案

?？∠?，陶宏才

（ 西南交通大學(xué)信息科學(xué)與技術(shù)學(xué)院，成都610031）

隨著XML文件的廣泛使用，對(duì)XML的研究越來越多，包括XML編碼、XML查詢、XML存儲(chǔ)等。其中XML編碼可以有效地支持XML查詢中的結(jié)構(gòu)連接操作，是判斷節(jié)點(diǎn)間結(jié)構(gòu)關(guān)系的重要依據(jù)。

目前已有的編碼方案主要分為2類：區(qū)域編碼和前綴編碼。

區(qū)域編碼[1~2]是按照結(jié)點(diǎn)的物理位置進(jìn)行編碼，編碼結(jié)構(gòu)為，其中start和end分別表示節(jié)點(diǎn)的開始位置和結(jié)束位置。區(qū)域編碼是目前使用較多的XML編碼方法，但其不能有效地支持文檔更新，雖然通過預(yù)留編碼空間等方法緩解了它對(duì)文檔更新的缺憾，但仍不夠靈活。前綴編碼[3~4]把節(jié)點(diǎn)路徑做為編碼依據(jù)，保存了編碼的路徑信息，編碼支持文檔更新，缺點(diǎn)是編碼較長(zhǎng)，占用存儲(chǔ)空間較大。文獻(xiàn)[5]提出了PBiTree編碼，并在此基礎(chǔ)上提出了基于橫向拆分和基于縱向拆分的結(jié)構(gòu)連接算法，該算法采用了二叉樹編碼方法，但算法復(fù)雜，中間轉(zhuǎn)換較多，仍不夠完善。文獻(xiàn)[6]等提出的高效查詢編碼方法，采用記錄節(jié)點(diǎn)路徑的方式，支持快速查詢操作，但需要較多的輔助信息。

本文提出了一種基于二叉樹的BTB（Binary Tree Based，BTB）編碼，編碼是二進(jìn)制格式，可以保存節(jié)點(diǎn)的路徑信息。由于采用的是二進(jìn)制的編碼形式，有效地節(jié)省了編碼的存儲(chǔ)空間，并支持文檔更新。

1 編碼方法

BTB編碼是基于樹結(jié)構(gòu)的編碼，編碼時(shí)需要用到完全二叉樹結(jié)構(gòu)。

1.1 XML文檔樹的二叉樹化

XML文檔是一種半結(jié)構(gòu)化數(shù)據(jù)，可以以樹的形式表示，該樹被稱為XML文檔樹。一棵XML文檔樹如圖1，其中節(jié)點(diǎn)S是二叉樹的根節(jié)點(diǎn)，即XML文檔樹的文檔節(jié)點(diǎn)，最低層的6個(gè)節(jié)點(diǎn)是葉子節(jié)點(diǎn)。

圖1 XML文檔樹

BTB編碼的編碼思想是：把XML文檔樹二叉樹化，對(duì)轉(zhuǎn)化后的文檔二叉樹進(jìn)行編碼。把一棵XML文檔樹T二叉樹化，轉(zhuǎn)化后的二叉樹用T′表示。二叉樹化的步驟如下：

（1）T'的根節(jié)點(diǎn)為T的根節(jié)點(diǎn)N；

（2）對(duì)于其它節(jié)點(diǎn)，若它和它的所有兄弟加起來的節(jié)點(diǎn)個(gè)數(shù)n不大于2，則將其子節(jié)點(diǎn)作為T'中根節(jié)點(diǎn)的子節(jié)點(diǎn)；否則轉(zhuǎn)到步驟（3）；

（3）以當(dāng)前節(jié)點(diǎn)的雙親節(jié)點(diǎn)作為祖先節(jié)點(diǎn)，將當(dāng)前節(jié)點(diǎn)及其兄弟節(jié)點(diǎn)下移[Ilog2nJ] －1層，中間以虛節(jié)點(diǎn)填充；

（4）重復(fù)步驟（2）和步驟（3），直到所有節(jié)點(diǎn)都處理完。

例如，圖2是將圖1中XML文檔樹二叉樹化后的結(jié)果。

圖2 嵌入完全二叉樹的結(jié)果

1.2 BTB編碼方法

對(duì)一棵文檔二叉樹進(jìn)行編碼，編碼采用二進(jìn)制表示，每個(gè)節(jié)點(diǎn)編碼的二進(jìn)制位數(shù)等于該結(jié)點(diǎn)所在的層數(shù)，根結(jié)點(diǎn)的編碼為“1”，其它節(jié)點(diǎn)的編碼為：雙親節(jié)點(diǎn)編碼×2＋0/1。其中0和1分別表示左子樹和右子樹。

把一棵XML文檔樹二叉樹化之后，對(duì)該二叉樹進(jìn)行編碼。編碼必須滿足以下2點(diǎn)：

（1） 如果當(dāng)前節(jié)點(diǎn)是根節(jié)點(diǎn)，編碼為1；

（2） 如果當(dāng)前節(jié)點(diǎn)不是根節(jié)點(diǎn)，當(dāng)前節(jié)點(diǎn)u的編碼由下式計(jì)算

L(u)=2×lv+x

其中l(wèi)v為u的雙親節(jié)點(diǎn)編碼。x的取值為0或1，當(dāng)v是左子樹時(shí)取0，v是右子樹時(shí)取1。該編碼方法稱為BTB編碼。

例如，圖2中，節(jié)點(diǎn)S為根節(jié)點(diǎn)，編碼為“1”，s1編碼為“100”，s2的子節(jié)點(diǎn)姓名編碼為s2的編碼+“0”，即為“1010”。

編碼是一個(gè)二進(jìn)制串，每一個(gè)二進(jìn)制位保存一個(gè)路徑分支信息。存儲(chǔ)時(shí)可直接按此二進(jìn)制串表示的整形數(shù)據(jù)存儲(chǔ)。BTB為不等長(zhǎng)碼，節(jié)點(diǎn)在樹中的層數(shù)越小，編碼長(zhǎng)度越短；反之，越是處在下層的節(jié)點(diǎn)編碼長(zhǎng)度越長(zhǎng)。有一些節(jié)點(diǎn)是在XML文檔樹中不存在的，是一些虛擬的節(jié)點(diǎn)，在編碼時(shí)，可直接跳過。

對(duì)一棵XML文檔樹進(jìn)行編碼的算法如下：

算法：Coding_method(T，code)

輸入：XML文檔的根節(jié)點(diǎn)T，1

輸出：文檔中每個(gè)節(jié)點(diǎn)元素的編碼code

Begin

Printf(code); //輸出當(dāng)前節(jié)點(diǎn)編碼code

ChildNumber=ChildNumber of T; //先計(jì)算節(jié)點(diǎn)的孩子個(gè)數(shù)

temp=log2ChildNumber;

if(temp!=|temt|) high=temp+1; //high表示要下移的層數(shù)

else high=temp;

code=code*(2^high); //下移high層時(shí)編碼左移high位，即末位加high個(gè)0

for(i=1; i<=ChildNumber) //對(duì)每個(gè)子節(jié)點(diǎn)分別進(jìn)行編碼

{ Temp2=child[i] of T

Coding_method(Temp2,code); //對(duì)子節(jié)點(diǎn)遞歸編碼

code++; //編碼值加1

}

End

BTB編碼可以有效地支持文檔更新，當(dāng)插入新節(jié)點(diǎn)時(shí)，僅需要對(duì)插入位置節(jié)點(diǎn)的子孫節(jié)點(diǎn)重新編碼，其余節(jié)點(diǎn)編碼不變。例如，要在s2節(jié)點(diǎn)下面增加一個(gè)孩子節(jié)點(diǎn)，只需要修改s2節(jié)點(diǎn)2個(gè)子節(jié)點(diǎn)的編碼，其它編碼不變。

1.3 BTB編碼的性質(zhì)

性質(zhì)1：每個(gè)節(jié)點(diǎn)BTB編碼的二進(jìn)制長(zhǎng)度等于節(jié)點(diǎn)在文檔二叉樹中的層次。

證明：當(dāng)層次length=1時(shí)，為根節(jié)點(diǎn)，編碼是1，1的二進(jìn)制長(zhǎng)度為1；設(shè)length=k時(shí)，編碼L(k)的二進(jìn)制長(zhǎng)度為k；則length=k+1時(shí)，編碼L(k+1)=L(k) ×2+0或L(k+1)=L(k) ×2+1，因?yàn)長(zhǎng)(k)的二進(jìn)制長(zhǎng)度為k，故L(k+1)的二進(jìn)制長(zhǎng)度為k+1。證畢。

性質(zhì)2：給定一個(gè)節(jié)點(diǎn)u的編碼lu，它的任一祖先節(jié)點(diǎn)編碼都是lu所表示的二進(jìn)制串的前子串。

證明：由BTB編碼原理可知，除根節(jié)點(diǎn)外，任一節(jié)點(diǎn)編碼都是由其雙親節(jié)點(diǎn)編碼變化得來，即在雙親節(jié)點(diǎn)編碼后補(bǔ)一位，0/1，故，它的任一祖先節(jié)點(diǎn)的編碼都是其編碼的前子串。證畢。

性質(zhì)3：給定一個(gè)節(jié)點(diǎn)u的編碼lu，它在文檔二叉樹中h層的祖先節(jié)點(diǎn)的編碼可由下式求出

L(parent)=lu/2k-h

其中，k=|log2lu|+1，k計(jì)算的是lu的二進(jìn)制位數(shù)。

證明：由性質(zhì)1可知，h層節(jié)點(diǎn)的二進(jìn)制編碼長(zhǎng)度為h；由性質(zhì)2可知，節(jié)點(diǎn)u在h層的祖先節(jié)點(diǎn)的編碼為lu所表示的二進(jìn)制串的前子串。所以，u在h層的祖先節(jié)點(diǎn)的編碼是lu所表示的二進(jìn)制串的前h位子串，故原式成立。證畢。

給定u和v 2個(gè)節(jié)點(diǎn)，設(shè)它們?cè)谖臋n二叉樹中的層數(shù)分別為n1和n2。u是v的祖先節(jié)點(diǎn)，當(dāng)且僅當(dāng)節(jié)點(diǎn)u的編碼等于節(jié)點(diǎn)v編碼的前n1位。u是v的父親節(jié)點(diǎn)，當(dāng)且僅當(dāng)u的編碼與v的編碼的前n1位完全相同，且n2=n1+1。

1.4 對(duì)文檔更新的支持

設(shè)節(jié)點(diǎn)u的編碼為lu，孩子數(shù)為n。在節(jié)點(diǎn)u處插入子節(jié)點(diǎn)v時(shí)，對(duì)新節(jié)點(diǎn)編碼的處理有以下3種情況：

（1）當(dāng)n=0時(shí)，即u為葉子節(jié)點(diǎn)，新節(jié)點(diǎn)v作為節(jié)點(diǎn)u的孩子節(jié)點(diǎn)插入到文檔二叉樹中，對(duì)新節(jié)點(diǎn)v編碼，編碼為：lu×2。其它節(jié)點(diǎn)編碼不變；

（2）當(dāng)n=1時(shí)，節(jié)點(diǎn)u只有一個(gè)孩子節(jié)點(diǎn)，若新節(jié)點(diǎn)作為節(jié)點(diǎn)u的右孩子插入到文檔二叉樹中，編碼為：lu×2+1。其它節(jié)點(diǎn)編碼不變；

（3）當(dāng)n=1時(shí)，節(jié)點(diǎn)u只有一個(gè)孩子節(jié)點(diǎn)，若新節(jié)點(diǎn)作為節(jié)點(diǎn)u的左孩子插入到文檔二叉樹中，節(jié)點(diǎn)u原來的孩子節(jié)點(diǎn)重新編碼為：lu×2+1，節(jié)點(diǎn)v編碼為lu×2。其它節(jié)點(diǎn)編碼不變；

（4）當(dāng)n=2時(shí)，文檔二叉樹中沒有空位置插入新節(jié)點(diǎn)，調(diào)用算法Coding_method(u，lu)對(duì)節(jié)點(diǎn)u的子樹進(jìn)行重新編碼，其它節(jié)點(diǎn)編碼不變；

（5）對(duì)于刪除節(jié)點(diǎn)的處理是，直接把該節(jié)點(diǎn)的編碼刪除，其它節(jié)點(diǎn)編碼不變。

2 實(shí)驗(yàn)及分析

目前的編碼方案都存在一定缺陷，區(qū)域編碼不能很好地支持文檔更新，前綴編碼支持文檔更新，但需要占用大量的存儲(chǔ)空間。本文提出的BTB編碼，采用的是二進(jìn)制編碼形式，存儲(chǔ)時(shí)以十進(jìn)制存儲(chǔ)，節(jié)省大量空間，并且對(duì)于文檔的更新，更新時(shí)只需要修改少量數(shù)據(jù)。

實(shí)驗(yàn)是在一臺(tái)操作系統(tǒng)為Windows XP、處理器為2.16 GHz、內(nèi)存為2 Gbit的PC機(jī)上進(jìn)行的，算法使用Java編碼實(shí)現(xiàn)，所采用的XML測(cè)試數(shù)據(jù)是來源于一個(gè)針對(duì)XML的基準(zhǔn)測(cè)試項(xiàng)目X-Mark[7]數(shù)據(jù)集，實(shí)驗(yàn)選擇典型的區(qū)域編碼XISS[3]及前綴編碼LSDX[5]進(jìn)行比較，實(shí)驗(yàn)結(jié)果如圖3。

圖3 編碼長(zhǎng)度比較

實(shí)驗(yàn)結(jié)果表明，對(duì)于相同大小的XML文檔，由于BTB編碼采用的是二進(jìn)制編碼，占用的存儲(chǔ)空間最小；LSDX編碼用字母表示節(jié)點(diǎn)的位置關(guān)系，占用的存儲(chǔ)空間最大。

3 結(jié)束語

本文提出了BTB編碼方案，該方案可以有效地支持祖先/后代關(guān)系、父子節(jié)點(diǎn)關(guān)系和兄弟關(guān)系的判斷，并且判斷可在常數(shù)時(shí)間完成。對(duì)于存儲(chǔ)，該編碼由于采用了二進(jìn)制的編碼方式，每個(gè)節(jié)點(diǎn)具有唯一編碼，以十進(jìn)制數(shù)據(jù)存儲(chǔ)，占用較少的存儲(chǔ)空間。在該編碼下的結(jié)構(gòu)連接算法是下一步的研究方向。

[1] Zhang C, et al. On Supporting Containment Queries in Relational Database Management Systems[C] . Proc. of SIGMOD, 2001:425-436.

[2] Michael Erdmann, Rudi Studer. How to structure and access XML documents with ontologies[J] . Data & Knowledge Engineering, 2001(36): 317-335.

[3] Cohen E, Kaplan H, Milo T. Labeling Dynamic XML Trees[C] .Proc. of PODS, 2002: 271-281.

[4] Duong M, Zhang Y. A New Labeling Scheme for Dynamically Updating XML Data[C] . Proc. of ADC, 2005.

[5] Wang W, Jiang HF, Lu HJ, Jeffrey XY. PBiTree coding and efficient processing of containment joins[C] . Dayal U, Ramamritham K, Vijayaraman TM, eds. Proc. of the 19th Int'l Conf.on Data Engineering. Los Alamitos: IEEE Press, 2003: 391-402.

[6] 文華南，劉先鋒，李文鋒，李玲勇. 高效查詢的XML編碼方案[J] . 計(jì)算機(jī)應(yīng)用， 2010， 30（3）： 831-834.

[7] SCHMIDT A, WAAS F, KERSTEN M, et at. XMark A benchmark for XML data management[C] . Proc. of the 28th VLDB Conf. HongKong VLDB Endowment, 2002: 974-985.