支持實體識別的XML編碼方案

李天輝, 穆寶良

(沈陽師范大學 科信軟件學院, 沈陽 110034)

?

支持實體識別的XML編碼方案

李天輝, 穆寶良

(沈陽師范大學 科信軟件學院, 沈陽 110034)

提出了XML文檔的一種start-end-type(SET)編碼方法,SET編碼基于起止編碼的思想,并把起止編碼的三元組(start,end,level)改進為四元組(start,end,level,type),增加了表示XML文檔中結點類型的type值。對四元組中的前3個值提出了新的實現算法,而第4個元素type值由前3個元素的值自動計算出來。SET編碼不僅可以快速判斷出結點之間的祖先/后代、父親/孩子關系,而且還可以根據type值快速判斷出XML文檔中各結點的類型。經過實驗測試,SET編碼不僅具有良好的編碼性能,還能根據各結點類型對XML數據進行實體識別,為進一步研究根據實體類型對XML數據進行查詢提供條件。

大數據; 起止編碼; SET編碼; 深度優先遍歷; 實體結點

0 引 言

對網絡中大量存在的XML數據如何進行高效的查詢[1-4]已成為大數據[5]研究的一部分。通常,利用給出的查詢路徑表達式,在目標XML文檔樹上進行導航并返回匹配結果。為了求得滿足條件約束的匹配結果,必須對祖先/后代或父親/孩子關系的文檔位置關系的進行判斷,所以不可避免在XML文檔上進行結構連接[6]的計算,查詢效率很低。為了提高查詢的效率,本文在起止編碼的基礎上提出了SET編碼。SET編碼不僅可以快速的判斷結點之間的祖先/后代、父親/孩子關系,而且支持對XML文檔結點的類型的識別。

1 相關研究

對XML文檔的編碼[7],是指按照某種規則對XML文檔樹中的每一個結點分配唯一的編碼,目的是通過任意2個結點的編碼,能夠直接判斷出2個結點之間的結構關系,進而能夠高效地支持對XML數據的索引和查詢。目前提出的編碼主要分為4種常見的方法:區域編碼[8]、前綴編碼[9]、K分樹編碼和支持動態更新的編碼[10]方法。下面對區域編碼和起止編碼做簡要介紹。

1.1 區域編碼

根據文獻[7],區域編碼采用樹的前序遍歷和后序遍歷的值為樹中的結點進行編碼,每一個結點賦予了一個二元組(start,end)。這樣前序值和后序值就可以唯一確定一個結點及結點間的位置關系。基于這種思想,出現很多區域編碼,其中起止編碼[11]是最常用的一種編碼方式。

1.2 起止編碼

起止編碼改進了區域編碼,采用深度優先遍歷XML文檔中所有結點,并對每個結點用三元組(start,end,level)表示。用level代表結點在文檔樹中的層次。

起止編碼不僅能很容易判斷出文檔結點間的位置關系,且還能進一步判斷出2個結點之間是否存在父子關系。對于給定的XML文檔中的2個結點m、n,其對應的起止編碼分別為Cm=(m.start,m.end,m.level)、Cn=(n.start,n.end,n.level),當m.start

2 XML文檔的SET編碼方案及實現算法

2.1 SET(start-end-type Coding)編碼方案

為了在查詢過程中不但能判斷出文檔結點間的祖先/后代、父親/孩子關系,還要能識別出XML文檔中各結點的類型,本文提出了對XML文檔的SET編碼。SET編碼是在起止編碼的基礎上,把起止編碼表示結點的三元組(start,end,level)改進為四元組(start,end,level,type),其中第4個元素type代表該結點的類型。根據文獻[12-15],結點類型可分為4種:實體結點、屬性結點、葉子結點和連接結點。具體定義如下:1)實體結點:DTD中帶*的結點或含有多個屬性的結點;2)屬性結點:只含有一個值結點的結點;3)葉子結點:屬性的值結點(葉子結點不做起止編碼);4)連接結點:如果一個結點不是實體結點,屬性結點,葉子結點即為連接結點。

如圖1即為SET編碼的文檔樹(type元素類型的取值:“2”代表實體結點類型,“1”代表屬性結點類型,“3”代表連接結點類型)。

圖1 圖書數據D1的SET編碼文檔樹Fig.1 The SET encoding document tree of Book data D1

2.2 SET編碼實現算法

SET編碼四元組中前3個元素的編碼與起止編碼的編碼思想基本相同,但本文提出了計算前3個元素值的新算法,而四元組中的type元素值是按照上述XML文檔結點分類方法并根據四元組中的前3個編碼值計算出來的。

2.2.1 計算SET編碼四元組中前2個元素start,end值的新算法

計算SET編碼前2個元素值是對XML文檔樹的深度優先遍歷。過程如下:設R是XML文檔樹的根結點,首先從根結點出發,并對R訪問起止編碼開始元素start賦值,即R.start=i(i是整數,初值為1,每訪問結點1次,i都做自加運算i++)。然后選擇一個孩子結點C,然后對孩子結點C進行起止編碼開始元素start賦值,即C.start=i+1,然后對孩子的孩子結點G進行訪問,開始編碼標記G.start=i+1。這樣直到訪問到沒有孩子結點時,對該結點進行回訪,并給其編碼結束元素end賦值,還是延續原編碼開始元組的順序號遞增,即G.end=i+1。此時,再根據同樣的規則訪問其兄弟結點及其兄弟的孩子結點,也用同樣的方法為其編碼開始元素start和編碼元素end的值順次遞增。如果所有的兄弟結點都訪問完畢就回訪其父結點,并給父結點的編碼結束元素end賦值,再訪問父結點的兄弟結點,依此類推,最后回訪到根結點R,并對根結點編碼結束標記end賦值,即R.end=i。因為每個結點訪問2次,所以最后的i值一定是所有結點數的2倍。

在計算SET編碼的前2個元素start,end的值時,本文根據遍歷XML文檔樹結點和解析XML文件元素的對應關系,直接對XML文檔進行編碼。

設XML文檔根結點為R,孩子結點為C1,C2,…,Cn,孩子的孩子結點為G1,G2,…,Gn,該文檔對應的樹模型和XML文檔如圖2所示。

××× ××× ? ××× ?

圖2 XML文檔的樹模型與文檔對應圖

Fig.2 XML document tree model corresponds to diagram and documentation

如前所述,對XML文檔結點的深度優先遍歷的起止編碼的訪問和回訪順序為:R C1 G1 G1* G2 G2* …Gn Gn* C1* C2 C2*…Cn Cn* R*。其中帶*的為回訪,即代表該結點的起止編碼結束。

而對于圖2右的XML文檔,XML元素標簽在文檔中的排列順序為:……。

2.2.2 計算SET編碼四元組中第3個元素level值的實現算法

SET編碼的第3元素level值可以按如下方法確定:當程序訪問指針讀到根結點R時,把當前的層次level值設置為j(j初值為1)。而指針讀取R的孩子結點C1時,把當前的level值設置為j=j+1(j=2,即為第2層)。再讀到C1的孩子結點G1時,把當前的level值設置為j=j+1(j=3,即為第3層)。因為G1無孩子結點,所以直接回訪G1,即可計算出該結點的(G1.start,G1.end)元組的值,即該結點被訪問結束。然后程序訪問指針返回到上一層,此時level的值設置為j=j-1(j=2,代表回到第2層),接下來繼續訪問C1的下一個孩子結點G2,level值的計算方法同上,直至C1的所有孩子結點都訪問完畢,這時需要回訪C1,即可算出(G1.start,G1.end)元組的值,C1結點被訪問結束。此時訪問指針再返回到上一層,即回到根結點所在層次,此時level的值設置為j=j-1(j=1,代表回到第一層),然后再訪問根結點的其他孩子結點,level的值再次設置為j=j+1(j=2,回到第2層),其他同上。當讀完所有孩子結點,程序訪問指針返回到根結點R,level的值設置為j=j-1(j=1,回到第一層),即根結點R的level值為1。

如果元素結點中含有屬性,形如,此時把元素的屬性結點按孩子結點處理,因為對于XML文檔樹模型來說,元素的屬性結點和孩子結點是相同地位的。

2.2.3 計算SET編碼四元組中第4個元素type值的實現算法

用以上方法計算出SET編碼的前3個元素的值后,就可以根據這3個元素的值自動計算出第4個元素type的值,即結點的類型。

首先,規定type元素類型的取值:“2”代表實體結點類型,“1”代表屬性結點類型,“3”代表連接結點類型。計算方法如下:

1) 如果一個結點M只含有葉子結點,則結點M為屬性結點。

公式(1):if(M.end-M.start)=1, 則M.type=“1”。(由于葉子結點不做編碼,所以屬性結點的起止編碼值差為1。)

2) 如果一個結點M有多個屬性,則結點M為實體結點。

公式(2):if(M.end-M.start)>=3,且M.level!=1,則M.type=“2”。(因為實體結點至少有一個屬性結點。)

3) 如果一個結點M有多個孩子結點,且孩子結點中有2個或2個以上含有相同標簽或者每一個孩子結點都是實體結點,則M結點為連接結點。

公式(3):allchildrenequals(M.childrens)=true OR allchildrenisentity(M.childrens)=true,則M.type=“3”。(allchildrenequals()為判斷是否含有2個或2個以上具有相同標簽的孩子結點的函數;allchildrenisentity()為判斷是否所有孩子結點都為實體結點的函數。)

綜上所述,SET編碼可以分為計算start,end值、level值和type值3個部分,具體算法如下:

算法1 XML文檔SET編碼

輸入:XML文檔;輸出:XML文檔的SET編碼

∥計算SET編碼前3個元組,start,end,level編碼

讀取XML文檔元素標簽

if(qName是元素開始標簽){

tagsStack.push(qName) ∥結點名稱入堆棧

入棧元素開始編碼設為i=i+1;元素讀取指針深度設為j=j+1;

hashmap.put(qName,estart);∥把元素開始標簽編碼存入hashmap中

∥處理屬性,屬性也是XML文檔樹的一個結點,也需要編碼

int len = attrs.getLength();

for (int k = 0; k

{i=i+2; ∥屬性結點也是元素的一個分支,占2個編碼

string attrsname=(String)attrs.getQName(k);

∥屬性結點可以直接放入indenhashmap中

int start=i-1; ∥開始編碼

int end=i; ∥終止編碼

int level=j+1; ∥結點的層次

inputhashmap(attrsname,start,end,level);

if(qName是元素結束標簽)

{元素讀取指針深度設為j=j+1;

if (堆棧非空){ key1=棧頂元素標簽名

if(當前元素結束標簽名==棧頂元素標簽名)元素一對標簽配對成功

hashmap.remove(qName);∥能夠配對的標簽出哈斯表。元素的終止編碼設為i;元素讀取指針深度設為j=j-1;

函數inputhashmap(qname,start,end,level)

/*根據start,end,level值計算配對成功結點的類型,然后生成完整的SET編碼(start,end,level,type)四元組。*/

if(end-start==1) type=1; ∥屬性結點

else if(end-start>=3 && level!=1) type=2;∥實體結點

else type=3;∥連接結點

indentityhashmap.put(name,(start, end, level,type))}}}}

本算法是根據SET編碼的前3個元素(start, end, level)的值計算出第4個元素type的值。主要通過函數inputhashmap()來計算實體的匹配結點,而結點的匹配用堆棧技術來實現的。

3 SET編碼性能分析

為了測試SET編碼的性能,用Java語言實現了本文提出的SET編碼算法。在實驗中對XMark數據集進行了SET編碼與起止編碼并進行了比較,同時還測試了隨著XML文檔復雜性的增加時對XML文檔中各結點類型識別的有效性。

3.1 SET編碼與起止編碼的性能比較測試與分析

實驗系統將生成的SET編碼與起止編碼存儲到identityHashmap之中。identityHashmap類利用哈希表實現Map 接口,比較鍵(和值)時使用引用相等性代替對象相等性。即在IdentityHashMap中,當且僅當(k1=k2) 時,才認為2個鍵k1和k2相等(在正常Map實現(如HashMap)中,當且僅當滿足下列條件時才認為2個鍵 k1和 k2相等:(k1=null?k2=null: e1.equals(e2)))。

為了比較SET編碼與起止編碼的編碼性能,使用由Xmark標準提供的XML數據生成器生成六個大小分別為4、8、12、16、20、24 M的XML文檔。實驗中分別對這些大小不同的文檔進行SET編碼與起止編碼,采集測試數據如表1所示。

表1 XMark數據SET編碼與起止編碼的實驗數據Tab.1 Experimental data of SET encoding of XMark data

表1是在目標XML文檔層次深度保持不變的情況下對不同大小的XML數據進行SET編碼與起止編碼的執行時間的測試數據。從表中數據可以看出,在同等條件下SET編碼的執行時間比起止編碼略多,這是因為SET編碼為四元組(start,end,level,type),而起止編碼為三元組(start,end,level)。SET編碼是在計算tpye元素的值時候比起止編碼多花費了一些時間,但是多消耗的時間的增長率是非常低的,且編碼速度變化率也很穩定,說明SET編碼有較好的編碼性能。

3.2 SET編碼識別實體結點的有效性測試與分析

能識別出XML文檔中的實體結點是SET編碼的主要目標。而影響SET編碼識別實體結點的主要因素是XML文檔樹的深度,隨著文檔深度的增加使XML文檔越來越復雜。通過實驗對不同深度的20 M大小的XML文檔進行SET編碼測試并采集數據(文檔深度在5以下時,實體識別準確率全部為100%,表中略去),結果如圖3所示。

圖3 SET編碼算法在不同深度文檔上的執行時間Fig.3 The execution time of SET coding in differentdepth of document

圖3為SET編碼算法在不同深度的文檔上的執行時間,可以看出算法的執行時間與XML文檔的深度關系不大,說明SET編碼速度受XML文檔深度的影響很小。

圖4 SET編碼算法在不同深度文檔中辨別實體結點的正確率Fig.4 The correct rate of SET coding algorithm to distinguishthe entities in different depth of document

圖4為SET編碼算法在不同深度文檔中辨別實體結點的準確率。當XML文檔深度小于5層時,算法辨別實體結點的準確率非常高。而當文檔深度逐漸增加時,算法辨別實體結點的準確率呈下降趨勢。特別當深度達到10以上時,準確率呈快速下降趨勢。因此可以說明,XML文檔越復雜,出現多值屬性的概率越高,從而使SET編碼算法辨別實體結點的準確率呈下降趨勢。這是SET編碼算法有待改進之處。

3.3 性能分析

SET編碼繼承了起止編碼的優點,具有較好的編碼性能。如果XML文檔中的屬性結點不存在多值屬性,那么用SET編碼進行實體結點識別是準確的。如果一個結點含有多值屬性,那么這個結點的start和end值一定不是連續的,即它們的編碼差值要大于或等于3。根據公式(2),可得出這個結點是實體結點,但實際上是屬性結點。此為SET編碼的不足之處。解決這個問題有2種辦法: 1)人工識別,但在文檔很大時可操作性不強; 2)人工智能自動識別,識別程序需要維護一個龐大的知識庫,難度大。本文暫不做研究。

SET編碼較起止編碼增加了表示XML文檔中結點類型的值,所以增加了編碼的存儲容量,容量增加比率為33%。SET編碼以存儲空間換取了編碼新的功能,為進一步研究根據實體類型對XML數據進行查詢提供條件。

4 結 語

基于起止編碼提出了含有四元組(start,end,level,type)的SET編碼。其中第4個元素type代表XML文檔的結點類型,并對XML文檔結點類型進行了劃分。根據實驗測試結果,SET編碼具有良好的編碼性能,很容易判斷出文檔結點間的祖先/后代、父親/孩子關系及結點之間的層次關系,并且還可以根據type元素的值快速地判斷出XML文檔中各結點的類型。

[1]DEUTSCH A,FERNANDEZM,FLORESCU D.A query language for XML[C]∥Intemationl world wide web conference Toronto, 1999:1155-1169.

[2]MIN J K,LEE J,CHUNG C W.An efficient XML encoding and labeling method for query processing and updating on dynamic XML data[J]. J Syst Software, 2009,82(3):503-515.

[3]REN J D,YIN X P,GUO X D.A dynamic labeling scheme for XML document[J]. JCC,2006,3(5):61-65.

[4]楊小萍,李德錄,周文勤. 一種降低XML文檔更新代價的擴展Dewey編碼方案[J]. 沈陽師范大學學報(自然科學版), 2010,28(2):214-217.

[5]涂新莉,劉波,林偉偉. 大數據研究綜述[J]. 計算機應用研究, 2014,31(6):1612-1616.

[6]萬常選,劉云生,徐升華,等. 基于區間編碼的XML索引結構的有效結構連接[J]. 計算機學報, 2005,25(1):113-127.

[7]孟小峰. XML數據管理概念與技術[M]. 北京:清華大學出版社, 2009:59-60.

[8]羅道鋒,孟小峰,蔣瑜. XML數據擴展前序編碼的更新方法[J]. 軟件學報, 2005,16(5):810-818.

[9]YANG B, FONTOURA M,SHEKITA E J.5.Rajago Palan,and K.5.Beyer.Virtualeuxsor For XMLjoins[C]∥CIKM, 2004:523-532.

[10]ZHANG C,NAUGHTON J F,DEWITT D J,et al. On supporting containment queries in relational database management systems[C]∥ACM SIGMOD, 2001:442-446.

[11]LIU Z,CHEN Y.Identifying meaningful return information for XML keyword search[C]∥Management of Data(SIGMOD 2007), 2007:329-340.

[12]YU C,JAGADISH H V. Querying complex structured databases[C]∥Very Large Data Bases (VLOB 2007 ), 2007:1010-1021.

[13]王國仁,于戈,楊曉春,等. XML數據管理技術[M]. 北京:電子工業出版社, 2007:91-93.

[14]DEBAR H,BECKER M,SIBON I D.A neural network component for an intrusion detection system[M]. Berlin: Security and Privacy, 1992:256-266.

[15]GAO Debin,SREITER M K,SONG D. Behavioral distance measurement using hidden Markov models[M]. New Jersey: IEEE, 2006:19-40.

XML coding scheme for entity recognition

LITianhui,MUBaoliang

(Software College, Shenyang Normal University, Shenyang 110034, China)

In the present paper, a start-end-type (SET) coding method in the treatment of XML document is proposed based on the idea of start-end coding, and the start-end coding triplets (start, end, level) is developed into a four-tuple (start, end, level, type), which increases an XML document type node as the type value. This paper also proposes a new implementation algorithm for the first three values of the four tuple, and the type values of the fourth elements can be calculated automatically by the first three elements. SET coding not only can quickly determine the relationship between ancestor and descendant, or father and son of nodes, but also the type of XML document based on type value. After the experiment, SET coding not only has good coding performance, but also can recognize the of XML data entity according to node types, it can be the basis for the further study of XML data query according to the entity type.

big data; start-end coding; SET coding; depth first traversal; entity node

2016-06-13。

遼寧省教育廳科學研究一般項目(L2012388)。

李天輝(1976-),男,遼寧興城人,沈陽師范大學講師,碩士。

1673-5862(2016)04-0473-06

TP3l1

A

10.3969/ j.issn.1673-5862.2016.04.020