李天輝, 穆寶良

(沈陽(yáng)師范大學(xué) 科信軟件學(xué)院, 沈陽(yáng) 110034)

?

支持實(shí)體識(shí)別的XML編碼方案

李天輝, 穆寶良

(沈陽(yáng)師范大學(xué) 科信軟件學(xué)院, 沈陽(yáng) 110034)

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

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

0 引 言

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

1 相關(guān)研究

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

1.1 區(qū)域編碼

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

1.2 起止編碼

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

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

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

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

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

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

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

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

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

2.2.1 計(jì)算SET編碼四元組中前2個(gè)元素start,end值的新算法

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

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

設(shè)XML文檔根結(jié)點(diǎn)為R,孩子結(jié)點(diǎn)為C1,C2,…,Cn,孩子的孩子結(jié)點(diǎn)為G1,G2,…,Gn,該文檔對(duì)應(yīng)的樹(shù)模型和XML文檔如圖2所示。

××× ××× ? ××× ?

圖2 XML文檔的樹(shù)模型與文檔對(duì)應(yīng)圖

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

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

而對(duì)于圖2右的XML文檔,XML元素標(biāo)簽在文檔中的排列順序?yàn)?……。

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

SET編碼的第3元素level值可以按如下方法確定:當(dāng)程序訪問(wèn)指針讀到根結(jié)點(diǎn)R時(shí),把當(dāng)前的層次level值設(shè)置為j(j初值為1)。而指針讀取R的孩子結(jié)點(diǎn)C1時(shí),把當(dāng)前的level值設(shè)置為j=j+1(j=2,即為第2層)。再讀到C1的孩子結(jié)點(diǎn)G1時(shí),把當(dāng)前的level值設(shè)置為j=j+1(j=3,即為第3層)。因?yàn)镚1無(wú)孩子結(jié)點(diǎn),所以直接回訪G1,即可計(jì)算出該結(jié)點(diǎn)的(G1.start,G1.end)元組的值,即該結(jié)點(diǎn)被訪問(wèn)結(jié)束。然后程序訪問(wèn)指針?lè)祷氐缴弦粚?此時(shí)level的值設(shè)置為j=j-1(j=2,代表回到第2層),接下來(lái)繼續(xù)訪問(wèn)C1的下一個(gè)孩子結(jié)點(diǎn)G2,level值的計(jì)算方法同上,直至C1的所有孩子結(jié)點(diǎn)都訪問(wèn)完畢,這時(shí)需要回訪C1,即可算出(G1.start,G1.end)元組的值,C1結(jié)點(diǎn)被訪問(wèn)結(jié)束。此時(shí)訪問(wèn)指針再返回到上一層,即回到根結(jié)點(diǎn)所在層次,此時(shí)level的值設(shè)置為j=j-1(j=1,代表回到第一層),然后再訪問(wèn)根結(jié)點(diǎn)的其他孩子結(jié)點(diǎn),level的值再次設(shè)置為j=j+1(j=2,回到第2層),其他同上。當(dāng)讀完所有孩子結(jié)點(diǎn),程序訪問(wèn)指針?lè)祷氐礁Y(jié)點(diǎn)R,level的值設(shè)置為j=j-1(j=1,回到第一層),即根結(jié)點(diǎn)R的level值為1。

如果元素結(jié)點(diǎn)中含有屬性,形如,此時(shí)把元素的屬性結(jié)點(diǎn)按孩子結(jié)點(diǎn)處理,因?yàn)閷?duì)于XML文檔樹(shù)模型來(lái)說(shuō),元素的屬性結(jié)點(diǎn)和孩子結(jié)點(diǎn)是相同地位的。

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

用以上方法計(jì)算出SET編碼的前3個(gè)元素的值后,就可以根據(jù)這3個(gè)元素的值自動(dòng)計(jì)算出第4個(gè)元素type的值,即結(jié)點(diǎn)的類(lèi)型。

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

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

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

2) 如果一個(gè)結(jié)點(diǎn)M有多個(gè)屬性,則結(jié)點(diǎn)M為實(shí)體結(jié)點(diǎn)。

公式(2):if(M.end-M.start)>=3,且M.level!=1,則M.type=“2”。(因?yàn)閷?shí)體結(jié)點(diǎn)至少有一個(gè)屬性結(jié)點(diǎn)。)

3) 如果一個(gè)結(jié)點(diǎn)M有多個(gè)孩子結(jié)點(diǎn),且孩子結(jié)點(diǎn)中有2個(gè)或2個(gè)以上含有相同標(biāo)簽或者每一個(gè)孩子結(jié)點(diǎn)都是實(shí)體結(jié)點(diǎn),則M結(jié)點(diǎn)為連接結(jié)點(diǎn)。

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

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

算法1 XML文檔SET編碼

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

∥計(jì)算SET編碼前3個(gè)元組,start,end,level編碼

讀取XML文檔元素標(biāo)簽

if(qName是元素開(kāi)始標(biāo)簽){

tagsStack.push(qName) ∥結(jié)點(diǎn)名稱(chēng)入堆棧

入棧元素開(kāi)始編碼設(shè)為i=i+1;元素讀取指針深度設(shè)為j=j+1;

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

∥處理屬性,屬性也是XML文檔樹(shù)的一個(gè)結(jié)點(diǎn),也需要編碼

int len = attrs.getLength();

for (int k = 0; k

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

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

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

int start=i-1; ∥開(kāi)始編碼

int end=i; ∥終止編碼

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

inputhashmap(attrsname,start,end,level);

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

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

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

if(當(dāng)前元素結(jié)束標(biāo)簽名==棧頂元素標(biāo)簽名)元素一對(duì)標(biāo)簽配對(duì)成功

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

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

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

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

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

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

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

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

3 SET編碼性能分析

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

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

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

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

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

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

3.2 SET編碼識(shí)別實(shí)體結(jié)點(diǎn)的有效性測(cè)試與分析

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

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

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

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

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

3.3 性能分析

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

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

4 結(jié) 語(yǔ)

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

[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文檔更新代價(jià)的擴(kuò)展Dewey編碼方案[J]. 沈陽(yáng)師范大學(xué)學(xué)報(bào)(自然科學(xué)版), 2010,28(2):214-217.

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

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

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

[8]羅道鋒,孟小峰,蔣瑜. XML數(shù)據(jù)擴(kuò)展前序編碼的更新方法[J]. 軟件學(xué)報(bào), 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]王國(guó)仁,于戈,楊曉春,等. 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。

遼寧省教育廳科學(xué)研究一般項(xiàng)目(L2012388)。

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

1673-5862(2016)04-0473-06

TP3l1

A

10.3969/ j.issn.1673-5862.2016.04.020