王磊，張紅梅，郭有強(qiáng)

（1.蚌埠學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系，安徽蚌埠233000；2.安徽電子信息職業(yè)技術(shù)學(xué)院軟件學(xué)院，安徽蚌埠233000）

基于擴(kuò)展Dewey編碼的XML文檔關(guān)鍵字查詢算法研究

王磊1，張紅梅2，郭有強(qiáng)1

（1.蚌埠學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系，安徽蚌埠233000；2.安徽電子信息職業(yè)技術(shù)學(xué)院軟件學(xué)院，安徽蚌埠233000）

為實(shí)現(xiàn)XML關(guān)鍵字查詢，提出一種基于擴(kuò)展Dewey編碼快速求解SLCA的新算法：FEDA.算法利用Dewey擴(kuò)展編碼快速命中含有N個(gè)關(guān)鍵字的集合，將最終交集看做一棵簡化的XML樹，所有的葉節(jié)點(diǎn)即為求解的SLCA.該算法與經(jīng)典的ILE算法進(jìn)行對比，效率優(yōu)于ILE算法.

XML文檔；Dewey；擴(kuò)展編碼；SLCA

XML文檔大量用于網(wǎng)絡(luò)數(shù)據(jù)表達(dá)和信息交換. Xpath和Xquery［1］利用正則表達(dá)式可以精確地包含XML數(shù)據(jù)單元間的結(jié)構(gòu)與關(guān)聯(lián)，能充分地表達(dá)用戶的查詢意圖，返回結(jié)果命中率高.普通用戶在沒有了解XML數(shù)據(jù)組織結(jié)構(gòu)及查詢語法的前提下，不具備書寫復(fù)雜查詢表達(dá)式的能力，因此無法使用這兩種正則表達(dá)式進(jìn)行查詢.XML關(guān)鍵字查詢（Keyword Search）方式借鑒傳統(tǒng)的信息檢索技術(shù)（Information Retrieval，IR），如Xrank［2］、Xseek［3］等；用戶無需掌握XML文檔細(xì)節(jié)和復(fù)雜的查詢語法，即可在終端快捷方便地查詢.目前越來越多的研究人員設(shè)計(jì)算法以提高XML關(guān)鍵字查詢命中率和時(shí)間響應(yīng)效率，從而降低普通用戶使用XML搜索引擎的門檻，該類算法的研究已成為數(shù)據(jù)庫與信息檢索領(lǐng)域的一個(gè)重要研究方向.

XML關(guān)鍵字查詢算法基于樹形存儲模型，利用Dewey編碼等形式記錄XML文檔樹節(jié)點(diǎn)間的層次關(guān)系，返回LCA（Lowest Common Ancestor）［4］.LCA定義了XML關(guān)鍵字查詢結(jié)果中的最緊致片段，研究人員發(fā)現(xiàn)LCA查詢準(zhǔn)確率較低，原因是LCA對結(jié)果的定義無嚴(yán)格限制，導(dǎo)致結(jié)果集中某些LCA節(jié)點(diǎn)成為另外一些LCA的祖先節(jié)點(diǎn)，這些祖先節(jié)點(diǎn)與查詢關(guān)鍵字之間的相關(guān)度明顯降低，從而無法返回用戶所需的有效信息.在此基礎(chǔ)上，SLCA［5］、VLCA［6］、MLCA［7］等算法相繼出現(xiàn)，進(jìn)一步提高了XML關(guān)鍵字查詢的性能.

1　數(shù)據(jù)模型和相關(guān)定義

1.1XML數(shù)據(jù)模型

一個(gè)XML文檔可以看成是帶標(biāo)簽的有向樹D（r，V，E），其中V表示節(jié)點(diǎn)集合，E表示邊集合，r是根節(jié)點(diǎn).如果v是非葉節(jié)點(diǎn)，則tag（v）表示為標(biāo)簽，否則val（v）表示值.圖1所示的XML文檔樹中，所有的非葉節(jié)點(diǎn)均使用擴(kuò)展Dewey編碼進(jìn)行標(biāo)記，如paper＜5，0.0.2＞，paper＜12，0.0.2.2.0.2＞，paper＜15，0.0.3＞，paper＜ 22，0.1.2＞；而葉節(jié)點(diǎn)單獨(dú)使用Dewey編碼，如xml＜0.0.2.0.0＞和xml＜0.1.2.0.0＞.

圖1　擴(kuò)展Dewey編碼表示的XML文檔樹Fig.1Extended Dewey encoding XML document tree

1.2相關(guān)定義

定義6Dewey編碼.給定對應(yīng)XML文檔的標(biāo)簽有向樹D（r，V，E），D中任意節(jié)點(diǎn)的Dewey編碼由下列規(guī)則確定：1）根節(jié)點(diǎn)r的Dewey編碼為“0”.2）在寬度優(yōu)先遍歷D的過程中，如果節(jié)點(diǎn)v是節(jié)點(diǎn)u的第i個(gè)孩子節(jié)點(diǎn)，那么，節(jié)點(diǎn)v的Dewey編碼為“D（u）.（i-1）”，其中的D（u）表示節(jié)點(diǎn)u的Dewey編碼.

2　FEDA查詢算法

SLCA對XML最緊致片段的定義較為準(zhǔn)確.基于Dewey編碼求解SLCA經(jīng)典算法有堆棧算法（Stack）［7］、ILE（Indexed Lookup Eager）算法［5］和SE（Scan Ea?ger）算法［6］等.Stack算法需要逐一掃描關(guān)鍵字集合中節(jié)點(diǎn)，頻繁的Dewey編碼比較、入棧和出棧導(dǎo)致算法效率偏低.ILE算法利用B+樹索引快速掃描XML全文結(jié)點(diǎn)，使得查詢效率得到一定幅度的提高.SE算法本質(zhì)是ILE的變形，效率與ILE相差不大.

本文提出一種基于擴(kuò)展Dewey編碼快速求解SLCA的新算法FEDA（Fast Encode Dewey Algo?rithm），利用XML文檔樹的特點(diǎn)，在解析XML文檔過程中記錄下每個(gè)非葉節(jié)點(diǎn)的深度遍歷編號（Encode碼）.算法中從每個(gè)含有關(guān)鍵字的節(jié)點(diǎn)出發(fā)，回溯到根節(jié)點(diǎn)，并記錄下回溯過程中的Encode碼.設(shè)N個(gè)關(guān)鍵字命中XML文檔樹中的M個(gè)節(jié)點(diǎn)，最終對這M個(gè)集合的Encode碼求交集ResultSet，對于最終交集的樹結(jié)構(gòu)中，所有的葉節(jié)點(diǎn)就是最終的求解結(jié)果.

例1在圖1中查找包含“IR”和“Tom”關(guān)鍵字的SLCA節(jié)點(diǎn)，關(guān)鍵字“IR”Encode碼的集合Set1=｛｛1，2，5，8，9，12，13｝，｛1，2，15，16｝｝，“Tom”關(guān)鍵字Encode碼的集合Set2=｛｛1，2，5，8，9，12，14｝，｛1，2，15，17｝｝；去除Set1中的重復(fù)節(jié)點(diǎn)后，集合Set1=｛1，2，5，，8，9，12，13，15，16｝，同理Set2=｛1，2，5，8，9，12，14，15，17｝；Set1與Set2的交集為：ResultSet=｛1，2，5，8，9，12，15｝；對應(yīng)的Dewey編碼集合為：DeweySet=｛0，0.0，0.0.2，0.0.2.2，0.0.2.2.0，0.0.2.2.0.2，0.0.3｝，在DeweySet集合中，依次遍歷每個(gè)節(jié)點(diǎn)，剔除每個(gè)節(jié)點(diǎn)的祖先節(jié)點(diǎn)，最后得到的葉子節(jié)點(diǎn)集合為：｛0.0.2.2.0.2，0.0.3｝，即為求解的SLCA節(jié)點(diǎn).

例2查找包含“xml”和“John”關(guān)鍵字的SLCA節(jié)點(diǎn)，“xml”Encode碼集合為｛1，2，5，6，19，22，23｝，“John”Encode碼集合為｛1，2，15，18，19，22，24｝，二者交集為｛1，2，19，22｝，對應(yīng)的Dewey編碼集合為：Dewey?Set=｛0，0.0，0.1，0.1.2｝，剔除每個(gè)節(jié)點(diǎn)的祖先節(jié)點(diǎn)后，得到最終求解的SLCA節(jié)點(diǎn)為｛0.0，0.1.2｝.查詢S個(gè)關(guān)鍵字，只要判斷某個(gè)節(jié)點(diǎn)存在于最終的交集中，即為LCA節(jié)點(diǎn)，然后在ResultSet集合中去除LCA的祖先節(jié)點(diǎn)即可.

2.1數(shù)據(jù)預(yù)處理

解析XML可以置入任意格式數(shù)據(jù)庫，文中使用MySql數(shù)據(jù)庫.基于文獻(xiàn)［8，9］研究基礎(chǔ)，解析過程中將深度遍歷XML文檔樹的編號同步記錄，形成擴(kuò)展的Dewey編碼，形如＜Encode，Dewey＞.

2.2FEDA算法描述

2.3FEDA算法復(fù)雜度分析

2.4算法正確性證明

證明：對于任意給定的關(guān)鍵字對應(yīng)的Encode碼都是經(jīng)過深度優(yōu)先遍歷產(chǎn)生的，必然存在于XML文檔樹中；算法中求得的任意關(guān)鍵字對應(yīng)的Encode碼的集合，是每個(gè)含有關(guān)鍵字元素節(jié)點(diǎn)不斷向其父節(jié)點(diǎn)回溯產(chǎn)生的最短路徑，終止于根節(jié)點(diǎn).當(dāng)N個(gè)集合求交集過程中，只要交集不為空，就意味著在XML文檔樹中存在交叉節(jié)點(diǎn)，最壞的情況是交叉節(jié)點(diǎn)為根節(jié)點(diǎn)，這種情況認(rèn)定為查找失敗.其他情況下，在最終返回的結(jié)果集中，不僅返回了SLCA節(jié)點(diǎn)，連同SLCA的上層節(jié)點(diǎn)LCA一并返回.最后，算法通過刪除路徑集合中的非葉節(jié)點(diǎn)，即通過Dewey碼去除集合中含有SLCA前綴的LCA節(jié)點(diǎn)，使得SLCA節(jié)點(diǎn)會(huì)一直保持在算法運(yùn)行的最后集合中.刪除LCA過程中，不會(huì)刪除SLCA節(jié)點(diǎn)是因?yàn)楦鶕?jù)SLCA的定義中，SLCA所在的層要比LCA深，SLCA不存在更小的子樹同樣包含關(guān)鍵字，若包含則一定含有SLCA的公共前綴.因此，算法是正確可行的.

3　實(shí)驗(yàn)結(jié)果與分析

本文實(shí)驗(yàn)的硬件環(huán)境為：Intel Pentium雙核2.7 GHz，內(nèi)存4 GB；軟件環(huán)境為：Windows7、MySql5.5和MyEclipse8.0.使用Xmark生成大小不同的測試數(shù)據(jù)集，文檔信息見表1.

表1　測試用XML文檔信息Tab.1For test XML document information

用本文FEDA算法與文獻(xiàn)［7］ILE算法對數(shù)據(jù)集中的測試樣本分別計(jì)算SLCA，實(shí)驗(yàn)針對不同測試樣本的XML節(jié)點(diǎn)數(shù)，采用不同的關(guān)鍵字個(gè)數(shù)進(jìn)行運(yùn)行時(shí)間上的對比，得到的結(jié)果如圖2～圖5所示.測試過程重復(fù)3次，分別記錄后求平均值.

圖2　具有382節(jié)點(diǎn)數(shù)XML樣本測試結(jié)果Fig.2Test result with 382 nodes XML

圖3　具有14974節(jié)點(diǎn)數(shù)XML樣本測試結(jié)果Fig.3Test result with 14974 nodes XML

圖4　具有63533節(jié)點(diǎn)數(shù)XML樣本測試結(jié)果Fig.4Test result with 63533 nodes XML

從圖2～圖5中可以看出：使用不同數(shù)量的關(guān)鍵字進(jìn)行查詢時(shí)，系統(tǒng)消耗時(shí)間不同.隨著XML文檔中元素節(jié)點(diǎn)數(shù)遞增時(shí)，算法運(yùn)行時(shí)間隨之增加，F(xiàn)E?DA與ILE算法均可以得到相同查詢結(jié)果.影響查詢效率的另一方面是XML文檔樹的深度，XML文檔樹較深時(shí)，查詢消耗時(shí)間明顯增多.圖5反映出XML文檔樹較深時(shí)兩種算法運(yùn)行時(shí)間差異不大，但FEDA算法執(zhí)行效率仍優(yōu)于ILE算法.鑒于用戶查詢時(shí)，使用的關(guān)鍵字一般不會(huì)超過5個(gè)，當(dāng)XML文檔呈現(xiàn)扁平結(jié)構(gòu)時(shí)，F(xiàn)EDA算法進(jìn)行交運(yùn)算時(shí)間會(huì)一定程度降低，相比ILE算法更加具有優(yōu)勢.

圖5　具有151289節(jié)點(diǎn)數(shù)XML樣本測試結(jié)果Fig.5Test result with 151289 nodes XML

4　結(jié)束語

本文提出一種利用擴(kuò)展Dewey編碼快速求解SLCA的新算法FEDA，并給出算法描述和證明，通過實(shí)驗(yàn)查詢不同節(jié)點(diǎn)數(shù)和深度的XML文檔，與經(jīng)典的ILE算法進(jìn)行對比.結(jié)果表明，對于關(guān)鍵字較少且XML文檔具有扁平結(jié)構(gòu)時(shí)，F(xiàn)EDA算法優(yōu)于ILE算法，具有有效性和可行性.

［1］Xpath，Xquery［EB/OL］.［2011-05-11］.http：//www.w3school.com.cn/.

［2］Guo L，Shao F，Botev C，et al.XRANK：Randed keyword search over XML Documents.In：Halevy AY，Ives ZG，Doan A，eds.Proc.of the 2003 ACM SIGMOD Int’1 Conf.on Management of Data（SIGMOD）［M］.San diego：ACM Press，2003：16-27.

［3］Liu ZY，Walker J，Chen Y.X seek：A Semantic XML Search Engine Using Keywords［C］//VLDB Conference，2007.

［4］Hristidis V，Koudas N，Papakonstantitinou Y，et al.Key?word proximity search in XML trees［J］.IEEE Trans on Knowledge and Data Engineering，2006，18（4）：525-539.

［5］Xu Y，Papakonstantinou Y.Efficient keyword search for smallest LCAs in XML databases.In：ozcan F，ed.Proc.of the ACM SIGMOD Int’l Conf.on Management of Data（SIG?MOD）［M］.Baltimore：ACM Press，2005：537-538.

［6］Li G L，F(xiàn)eng J H，Wang J Y，et al.Effective Keyword Search for Valuable LCAs over XML［C］//SIGMOD Confer?ence，2007.

［7］Liu Z，Chen Y.Identifying meaningful return information for xml keyword search［C］//SIGMOD Conference，2007.

［8］李思莉，李娟.XML文檔到關(guān)系數(shù)據(jù)庫的映射策略［J］.計(jì)算機(jī)工程，2010，36（5）：40-42.

［9］王磊，姚保峰，朱洪浩，等.一種無DTD變化約束的XML與關(guān)系數(shù)據(jù)庫映射方法［J］.遼寧科技大學(xué)學(xué)報(bào)，2011，34（6）：588-593.

責(zé)任編輯：黃瀾

Research on the Algorithm of Keyword Search in XML Document Based on Extended Dewey Encoding

WANG Lei1，ZHANG Hongmei2，GUO Youqiang1
（1.Department of Computer Science and Technology，Bengbu College，Bengbu 233000，China；
2.Software College，Anhui Electron and Information Professional Technology College，Bengbu 233000，China）

For XML query keywords，a new algorithm FEDA based on extended Dewey encoding for fast solving SLCA is proposed.The algorithm gets a collection of N key words quickly by extended Dewey encoding，and the final intersection can be as a simplified XML tree，and the solution to SLCA is all of the leaf nodes.Compared with the classical ILE algorithm，the experimental results showed that the FEDA efficiency was better than the ILE algorithm.

XML document；Dewey；Extended encoding；SLCA

TP 311

A

1674-4942（2015）04-0381-04

2015-10-19

安徽省高校自然科學(xué)研究一般項(xiàng)目（113052015KJ09）；蚌埠學(xué)院自然科學(xué)項(xiàng)目（2013ZR06）；安徽電子信息職業(yè)技術(shù)學(xué)院自然科學(xué)項(xiàng)目（ADZX1303）