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

李天輝, 穆寶良

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

?

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

李天輝, 穆寶良

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

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

大數(shù)據(jù); 起止編碼; SET編碼; 深度優(yōu)先遍歷; 實體結(jié)點

0 引 言

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

1 相關(guān)研究

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

1.1 區(qū)域編碼

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

1.2 起止編碼

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

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

2 XML文檔的SET編碼方案及實現(xiàn)算法

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

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

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

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

2.2 SET編碼實現(xiàn)算法

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

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

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

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

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

××× ××× ? ××× ?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

算法1 XML文檔SET編碼

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

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

讀取XML文檔元素標簽

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

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

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

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

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

int len = attrs.getLength();

for (int k = 0; k

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

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

∥屬性結(jié)點可以直接放入indenhashmap中

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

int end=i; ∥終止編碼

int level=j+1; ∥結(jié)點的層次

inputhashmap(attrsname,start,end,level);

if(qName是元素結(jié)束標簽)

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

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

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

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

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

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

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

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

else type=3;∥連接結(jié)點

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

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

3 SET編碼性能分析

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

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

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

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

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

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

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

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

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

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

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

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

3.3 性能分析

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

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

4 結(jié) 語

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

[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]涂新莉,劉波,林偉偉. 大數(shù)據(jù)研究綜述[J]. 計算機應用研究, 2014,31(6):1612-1616.

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

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

[8]羅道鋒,孟小峰,蔣瑜. XML數(shù)據(jù)擴展前序編碼的更新方法[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數(shù)據(jù)管理技術(shù)[M]. 北京:電子工業(yè)出版社, 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