一種新的二叉樹結構XML編碼方案

桑俊霞，陶宏才

（ 西南交通大學信息科學與技術學院，成都610031）

隨著XML文件的廣泛使用，對XML的研究越來越多，包括XML編碼、XML查詢、XML存儲等。其中XML編碼可以有效地支持XML查詢中的結構連接操作，是判斷節點間結構關系的重要依據。

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

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

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

1 編碼方法

BTB編碼是基于樹結構的編碼，編碼時需要用到完全二叉樹結構。

1.1 XML文檔樹的二叉樹化

XML文檔是一種半結構化數據，可以以樹的形式表示，該樹被稱為XML文檔樹。一棵XML文檔樹如圖1，其中節點S是二叉樹的根節點，即XML文檔樹的文檔節點，最低層的6個節點是葉子節點。

圖1 XML文檔樹

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

（1）T'的根節點為T的根節點N；

（2）對于其它節點，若它和它的所有兄弟加起來的節點個數n不大于2，則將其子節點作為T'中根節點的子節點；否則轉到步驟（3）；

（3）以當前節點的雙親節點作為祖先節點，將當前節點及其兄弟節點下移[Ilog2nJ] －1層，中間以虛節點填充；

（4）重復步驟（2）和步驟（3），直到所有節點都處理完。

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

圖2 嵌入完全二叉樹的結果

1.2 BTB編碼方法

對一棵文檔二叉樹進行編碼，編碼采用二進制表示，每個節點編碼的二進制位數等于該結點所在的層數，根結點的編碼為“1”，其它節點的編碼為：雙親節點編碼×2＋0/1。其中0和1分別表示左子樹和右子樹。

把一棵XML文檔樹二叉樹化之后，對該二叉樹進行編碼。編碼必須滿足以下2點：

（1） 如果當前節點是根節點，編碼為1；

（2） 如果當前節點不是根節點，當前節點u的編碼由下式計算

L(u)=2×lv+x

其中lv為u的雙親節點編碼。x的取值為0或1，當v是左子樹時取0，v是右子樹時取1。該編碼方法稱為BTB編碼。

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

編碼是一個二進制串，每一個二進制位保存一個路徑分支信息。存儲時可直接按此二進制串表示的整形數據存儲。BTB為不等長碼，節點在樹中的層數越小，編碼長度越短；反之，越是處在下層的節點編碼長度越長。有一些節點是在XML文檔樹中不存在的，是一些虛擬的節點，在編碼時，可直接跳過。

對一棵XML文檔樹進行編碼的算法如下：

算法：Coding_method(T，code)

輸入：XML文檔的根節點T，1

輸出：文檔中每個節點元素的編碼code

Begin

Printf(code); //輸出當前節點編碼code

ChildNumber=ChildNumber of T; //先計算節點的孩子個數

temp=log2ChildNumber;

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

else high=temp;

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

for(i=1; i<=ChildNumber) //對每個子節點分別進行編碼

{ Temp2=child[i] of T

Coding_method(Temp2,code); //對子節點遞歸編碼

code++; //編碼值加1

}

End

BTB編碼可以有效地支持文檔更新，當插入新節點時，僅需要對插入位置節點的子孫節點重新編碼，其余節點編碼不變。例如，要在s2節點下面增加一個孩子節點，只需要修改s2節點2個子節點的編碼，其它編碼不變。

1.3 BTB編碼的性質

性質1：每個節點BTB編碼的二進制長度等于節點在文檔二叉樹中的層次。

證明：當層次length=1時，為根節點，編碼是1，1的二進制長度為1；設length=k時，編碼L(k)的二進制長度為k；則length=k+1時，編碼L(k+1)=L(k) ×2+0或L(k+1)=L(k) ×2+1，因為L(k)的二進制長度為k，故L(k+1)的二進制長度為k+1。證畢。

性質2：給定一個節點u的編碼lu，它的任一祖先節點編碼都是lu所表示的二進制串的前子串。

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

性質3：給定一個節點u的編碼lu，它在文檔二叉樹中h層的祖先節點的編碼可由下式求出

L(parent)=lu/2k-h

其中，k=|log2lu|+1，k計算的是lu的二進制位數。

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

給定u和v 2個節點，設它們在文檔二叉樹中的層數分別為n1和n2。u是v的祖先節點，當且僅當節點u的編碼等于節點v編碼的前n1位。u是v的父親節點，當且僅當u的編碼與v的編碼的前n1位完全相同，且n2=n1+1。

1.4 對文檔更新的支持

設節點u的編碼為lu，孩子數為n。在節點u處插入子節點v時，對新節點編碼的處理有以下3種情況：

（1）當n=0時，即u為葉子節點，新節點v作為節點u的孩子節點插入到文檔二叉樹中，對新節點v編碼，編碼為：lu×2。其它節點編碼不變；

（2）當n=1時，節點u只有一個孩子節點，若新節點作為節點u的右孩子插入到文檔二叉樹中，編碼為：lu×2+1。其它節點編碼不變；

（3）當n=1時，節點u只有一個孩子節點，若新節點作為節點u的左孩子插入到文檔二叉樹中，節點u原來的孩子節點重新編碼為：lu×2+1，節點v編碼為lu×2。其它節點編碼不變；

（4）當n=2時，文檔二叉樹中沒有空位置插入新節點，調用算法Coding_method(u，lu)對節點u的子樹進行重新編碼，其它節點編碼不變；

（5）對于刪除節點的處理是，直接把該節點的編碼刪除，其它節點編碼不變。

2 實驗及分析

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

實驗是在一臺操作系統為Windows XP、處理器為2.16 GHz、內存為2 Gbit的PC機上進行的，算法使用Java編碼實現，所采用的XML測試數據是來源于一個針對XML的基準測試項目X-Mark[7]數據集，實驗選擇典型的區域編碼XISS[3]及前綴編碼LSDX[5]進行比較，實驗結果如圖3。

圖3 編碼長度比較

實驗結果表明，對于相同大小的XML文檔，由于BTB編碼采用的是二進制編碼，占用的存儲空間最小；LSDX編碼用字母表示節點的位置關系，占用的存儲空間最大。

3 結束語

本文提出了BTB編碼方案，該方案可以有效地支持祖先/后代關系、父子節點關系和兄弟關系的判斷，并且判斷可在常數時間完成。對于存儲，該編碼由于采用了二進制的編碼方式，每個節點具有唯一編碼，以十進制數據存儲，占用較少的存儲空間。在該編碼下的結構連接算法是下一步的研究方向。

[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] . 計算機應用， 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.