趙艷妮，郭華磊，馬軍生

(1.陜西職業(yè)技術(shù)學(xué)院計(jì)算機(jī)科學(xué)系，陜西西安 710100;2.西安理工大學(xué)自動(dòng)化與信息工程學(xué)院，陜西西安 710048; 3.西安通信學(xué)院信息服務(wù)系，陜西西安 710106)

基于路徑權(quán)重的XML文檔相似度仿真研究

趙艷妮1，2，郭華磊3，馬軍生3

(1.陜西職業(yè)技術(shù)學(xué)院計(jì)算機(jī)科學(xué)系，陜西西安 710100;
2.西安理工大學(xué)自動(dòng)化與信息工程學(xué)院，陜西西安 710048; 3.西安通信學(xué)院信息服務(wù)系，陜西西安 710106)

針對(duì)XML文檔查詢效率低和準(zhǔn)確度不理想的問題，提出一種基于路徑權(quán)重的樹相似度算法。該算法以樹節(jié)點(diǎn)信息相似度和樹結(jié)構(gòu)相似度為出發(fā)點(diǎn)，依據(jù)信息組織主次分明的客觀規(guī)律，信息按照重要程度依次排列在樹的各個(gè)層次，樹節(jié)點(diǎn)信息自上至下重要程度逐漸減弱。根據(jù)距離根節(jié)點(diǎn)越近的節(jié)點(diǎn)表示的信息越重要，最低層信息的重要性最小的特點(diǎn)，依照樹節(jié)點(diǎn)在XML文檔樹中的層次自動(dòng)計(jì)算該節(jié)點(diǎn)的路徑權(quán)重，克服了傳統(tǒng)XML文檔樹相似度計(jì)算中樹節(jié)點(diǎn)信息權(quán)重平均分配或手工設(shè)置的缺點(diǎn)，解決了XML文檔樹的相似度自動(dòng)計(jì)算問題，實(shí)現(xiàn)了XML查詢樹與文檔樹的快速匹配。仿真結(jié)果表明，該算法在大量XML文檔檢索方面查詢效率、查準(zhǔn)率和查全率都得到有效改進(jìn)。

相似度;路徑權(quán)重;查詢樹;文檔樹

0 引言

隨著XML技術(shù)的廣泛應(yīng)用，如何在海量的XML文檔中快速準(zhǔn)確地檢索到有效信息逐漸受到重視，成為近幾年的熱門研究領(lǐng)域之一。由于XML文檔檢索受到內(nèi)容和結(jié)構(gòu)的雙重約束，因此XML文檔的查詢需要考慮關(guān)鍵字相似度和結(jié)構(gòu)相似度兩個(gè)因素［1］。關(guān)鍵詞相似度的研究比較成熟，而結(jié)構(gòu)相似度的研究是XML信息檢索的難點(diǎn)。目前針對(duì)XML結(jié)構(gòu)相似度的研究有兩種:一是結(jié)構(gòu)變換，窮舉查詢樹的所有可能結(jié)構(gòu)，然后與文檔樹匹配，該方法查準(zhǔn)率高，但效率非常低;二是建立數(shù)學(xué)模型，建立查詢樹與文檔樹相似度的數(shù)學(xué)模型，該方法檢索效率高，但查準(zhǔn)率和查全率還有待提高［2-3］。

文中在文獻(xiàn)［4］的基礎(chǔ)上，提出一種自動(dòng)計(jì)算查詢樹與文檔樹相似度的方法，克服了需要用戶設(shè)置路徑權(quán)重的缺點(diǎn)。該方法根據(jù)有效信息在查詢樹中的位置確定信息的重要程度，自動(dòng)計(jì)算路徑權(quán)重并賦予相應(yīng)路徑，綜合考慮有效節(jié)點(diǎn)信息和有效節(jié)點(diǎn)間的結(jié)構(gòu)關(guān)系來計(jì)算查詢樹與文檔樹之間的相似度，滿足用戶對(duì)XML文檔的精確匹配和模糊匹配。

1 樹相似度

文中將用戶查詢信息和XML文檔都用樹型結(jié)構(gòu)表示，即將XML文檔轉(zhuǎn)換為一棵標(biāo)記樹的數(shù)學(xué)模型，樹節(jié)點(diǎn)表示元素或元素屬性，樹節(jié)點(diǎn)的父子關(guān)系表示“元素-子元素”或“元素-屬性”的關(guān)系，葉節(jié)點(diǎn)表示文本、關(guān)鍵字等信息［5-6］。

設(shè)QT為用戶查詢樹，DT為文檔樹，SIMS(QT，DT)表示查詢樹與文檔樹的相似度。查詢樹QT和文檔樹DT的相似度首先考慮QT和DT包含節(jié)點(diǎn)信息的相似度，QT和DT包含節(jié)點(diǎn)信息相同的數(shù)量直接影響信息的相似度，相同的越多則相似度越高，相同的越少則相似度越低。但是樹節(jié)點(diǎn)信息的相似度僅僅反映查詢樹與文檔樹節(jié)點(diǎn)信息的相似性，忽略了樹節(jié)點(diǎn)之間的結(jié)構(gòu)相似度［7］，因此在考慮樹節(jié)點(diǎn)信息相似度的基礎(chǔ)上，樹節(jié)點(diǎn)的結(jié)構(gòu)相似度也非常重要，事實(shí)上文檔中信息都是有關(guān)聯(lián)的［8］。QT和DT的相似度由樹節(jié)點(diǎn)信息相似度和樹結(jié)構(gòu)相似度共同影響，只有樹節(jié)點(diǎn)信息越相似且樹節(jié)點(diǎn)結(jié)構(gòu)越相似時(shí)QT與DT的相似度才大［9］。

XML樹相似度如式(1)所示:

其中，QT為查詢樹;DT為文檔樹;SIMS(QT，DT)表示QT和DT的相似度;SIMS(EQT，EDT)表示QT和DT的樹節(jié)點(diǎn)信息相似度;SIMS(LQT，LDT)表示QT與DT的樹結(jié)構(gòu)相似度。

1.1 樹節(jié)點(diǎn)信息相似度

直觀上XML樹節(jié)點(diǎn)信息相同越多，則它們的相似度越高。文中改進(jìn)了文獻(xiàn)［4］提出的相似度方法:

其中，SIMS(EQT，EDT)表示查詢樹QT和文檔樹DT的樹節(jié)點(diǎn)信息相似度;EQT表示QT的節(jié)點(diǎn);EDT表示DT的節(jié)點(diǎn)。

1.2 樹結(jié)構(gòu)相似度

樹節(jié)點(diǎn)信息相似度僅僅反映了查詢樹的節(jié)點(diǎn)信息與文檔樹的節(jié)點(diǎn)信息的相似性，忽略了樹的結(jié)構(gòu)關(guān)系，因此需考慮查詢樹與文檔樹的結(jié)構(gòu)關(guān)系相似度［1］。XML樹結(jié)構(gòu)相似度如式(3)所示:

其中，SIMS(LQT，LDT)表示查詢樹QT和文檔樹DT的樹結(jié)構(gòu)相似度;u，v為QT中包含的節(jié)點(diǎn);αuv表示在QT中節(jié)點(diǎn)u，v之間的路徑權(quán)重;LQTuv表示在QT 中u，v節(jié)點(diǎn)之間的路徑所包含的邊數(shù)量;LDTuv表示在DT中u，v節(jié)點(diǎn)之間的路徑所包含的邊數(shù)量。

路徑權(quán)重定義如式(4)所示:

其中，Layeruv表示節(jié)點(diǎn)u，v路徑所在的層數(shù)(路徑所在層數(shù)從樹最下層計(jì)算，最低層層數(shù)為1，依次每增加一層加1);LC(QT)表示查詢樹QT路徑層的數(shù)量;LC(i)表示第i層路徑的數(shù)量。

這樣既保證了所有路徑的權(quán)重和為1，又符合距離根節(jié)點(diǎn)越近的節(jié)點(diǎn)信息越重要的客觀事實(shí)?？陀^上，查詢樹的根節(jié)點(diǎn)代表的信息是關(guān)鍵信息，所以被檢索的XML文檔必須保證根節(jié)點(diǎn)的匹配。檢索時(shí)首先進(jìn)行查詢樹根節(jié)點(diǎn)的匹配。將文檔樹根節(jié)點(diǎn)下所有節(jié)點(diǎn)進(jìn)行解析，構(gòu)建若干個(gè)文檔子樹，將這些文檔子樹以相似度的降序排列作為檢索結(jié)果反饋給用戶［10］。

1.3 相似度計(jì)算舉例說明

查詢樹QT，文檔樹DT1、DT2和DT3見圖1。

查詢樹QT路徑層數(shù)量LC(QT)為2，LayerAB= LayerAC=2，LayerBD=LayerBE=2，LQTAB=LQTAC= LQTBD=LQTBE=1。根據(jù)式(4)計(jì)算路徑權(quán)重:

同理，αAC=1/3，αBD=αBE=1/6。

(1)文檔樹DT1相似度。

其中，LDTAB=1，LQTAB=1，LDTAC=2，LQTAC=1，DLBD=QLBD=1，DLBE=QLBE=1。

文檔樹DT1相似度如式(6)所示:

(2)文檔樹DT2相似度。

其中，LDTAC=LQTAC=1，LDTAD=LQTAD=2，LDTAE=LQTAE=2。由于DT2缺少B節(jié)點(diǎn)，不存在路徑A→B，B→D，B→E，D節(jié)點(diǎn)最近的祖先是A節(jié)點(diǎn)，且路徑A→D存在，E節(jié)點(diǎn)類似。因此路徑A→D和A →E的權(quán)重計(jì)算要對(duì)路徑A→C進(jìn)行權(quán)重分割，最后求和。權(quán)重分割原理α=αAB/n(n為節(jié)點(diǎn)B的子節(jié)點(diǎn)數(shù)量)［11］。在DT2中，n為2，αAD定義如式(7)所示:

同理，αAE=1/3。

文檔樹DT 相似度如式(8)所示:

(3)文檔樹DT3相似度。

其中，LDTAB=LQTAB=1，LDTAC=LQTAC=1，LDTBD=3，LQTBD=1，LDTBE=3，LQTCE=1。

文檔樹DT3相似度如式(9)所示:

2 算法比較分析

選取具有代表性的文獻(xiàn)［6-8］中提出的算法，以圖2為研究對(duì)象進(jìn)行比較研究，驗(yàn)證文中相似度算法的有效性。其中，文獻(xiàn)［7］路徑權(quán)重:αAB=0.25，αAC= 0.25，αBD=0.25，αBE=0.25。結(jié)果如表1所示。

分析表1可知，文獻(xiàn)［6-7］的相似度算法都存在一定缺陷。QT和DT5樹節(jié)點(diǎn)信息和樹結(jié)構(gòu)都完全相同，匹配度應(yīng)該等于1，但文獻(xiàn)［6］的相似度小于1，與客觀事實(shí)不符;QT和DT1樹結(jié)構(gòu)不一致，并且DT1有F節(jié)點(diǎn)冗余信息，文獻(xiàn)［7］算法的相似度卻等于1，與客觀事實(shí)不符。通過比較分析，文中算法明顯優(yōu)于其他三種算法，且符合客觀事實(shí)。研究發(fā)現(xiàn)文檔樹的有效信息數(shù)量與相似度并不嚴(yán)格保持正比，有效信息量多并且樹結(jié)構(gòu)相似度高的文檔樹相似度才高，檢索結(jié)果更接近查詢信息?？傊?，相似度越接近1效果越好。

3 實(shí)驗(yàn)驗(yàn)證

將文獻(xiàn)［6］、文獻(xiàn)［7］(路徑權(quán)重取平均值)、文獻(xiàn)［8］中提出的算法與文中算法進(jìn)行比較。實(shí)驗(yàn)數(shù)據(jù): 500個(gè)XML格式的構(gòu)件信息描述文檔;實(shí)驗(yàn)環(huán)境:i5-3210M處理器，4 G內(nèi)存，Windows 7操作系統(tǒng);實(shí)驗(yàn)策略:Java語(yǔ)言在Eclipse3.7集成開發(fā)環(huán)境下以樹節(jié)點(diǎn)按層優(yōu)先搜索算法實(shí)現(xiàn)，圖表顯示采用開源插件org.swtchart_0.9.0［12-13］。具體結(jié)果如圖3～5所示。

圖3 查詢效率

從查詢效率、查準(zhǔn)率和查全率三個(gè)性能指標(biāo)對(duì)上述四種算法進(jìn)行比較。為了避免算法的局限性，給定了20棵完全不同的XML查詢樹，性能曲線上的每個(gè)點(diǎn)表示20棵查詢樹的平均值［14］。

圖3說明在查詢效率上文中算法優(yōu)于其他三種算法，并且隨著XML文檔數(shù)量的增加，查詢速度優(yōu)勢(shì)逐漸變大;圖4說明在查準(zhǔn)率上文中算法高于其他三種算法，主要原因是文中算法采用了距離根節(jié)點(diǎn)越近的路徑代表信息越重要的策略，符合信息組織主次分明的客觀事實(shí);圖5說明在查全率上文中算法比其他三種算法理想，文中算法從節(jié)點(diǎn)信息和結(jié)構(gòu)信息兩個(gè)方面考慮，增加了信息匹配率，提高了查全率。在查準(zhǔn)率和查全率上，隨著XML文檔數(shù)量的增加，四種算法都逐漸下降，其他三種算法的下降趨勢(shì)比文中算法較明顯，符合客觀事實(shí)。

4 結(jié)束語(yǔ)

針對(duì)XML文檔信息的有效查詢效率較低的問題，提出了基于路徑權(quán)重的XML文檔相似度匹配算法。依據(jù)日常工作生活中編輯信息的習(xí)慣，最重要的信息放在顯著位置，例如XML的樹根節(jié)點(diǎn)，根據(jù)信息的重要性依次排列在樹的各個(gè)層次，距離根節(jié)點(diǎn)越近的節(jié)點(diǎn)表示的信息越重要，依次排列，最低層信息的重要性最小。根據(jù)有效路徑在查詢樹的層次自動(dòng)計(jì)算該有效路徑的權(quán)重，克服了人工指定路徑權(quán)重的缺陷，計(jì)算簡(jiǎn)單有效。該算法有效信息量和有效節(jié)點(diǎn)間的結(jié)構(gòu)關(guān)系共同影響查詢樹和文檔樹的相似度，克服了僅僅依靠信息匹配、忽略信息之間關(guān)聯(lián)的局限性，使查準(zhǔn)率和查全率得到顯著提高。實(shí)驗(yàn)結(jié)果表明，該算法能夠幫助用戶方便快速地查詢到有效信息，符合用戶的需求。

［1］ Posonia A M，Jyothi V L.XML document retrieval by developing an effective indexing technique［C］//Proc of sixth international conference on advanced computing.［s.l.］:IEEE，2014:120-123.

［2］ 魏 珂，任建華，孟祥福.基于查詢片段松弛的XML小枝近似查詢方法［J］.小型微型計(jì)算機(jī)系統(tǒng)，2013，34(3):508 -514.

［3］ Rekha M，Rani N U.Efficient extraction of frequent elements from XML document using XML tree pattern matching［J］.International Journal of Advance Research in Computer Science and Management Studies，2014，2(3):54-59.

［4］ 牛大偉，蘇龍超，韓雨童，等.基于擴(kuò)展倒排索引的不確定XML關(guān)鍵字查詢算法［J］.計(jì)算機(jī)應(yīng)用與軟件，2015，32 (4):247-251.

［5］ Liao H，Li X，Chen J.An accurate identification of extended XML tree pattern for XQuery language［J］.International Journal of Database Theory and Application，2014，7(5):211-226.

［6］ 朱菁華，王曉玲.基于擴(kuò)展查詢表達(dá)式的XML關(guān)鍵字查詢［J］.計(jì)算機(jī)工程，2014，40(10):25-31.

［7］ 張 苗，惠小強(qiáng).一種快速的XML文檔驗(yàn)證算法［J］.計(jì)算機(jī)技術(shù)與發(fā)展，2015，25(8):123-127.

［8］ Piernik M，Brzezinski D，Morzy T.Clustering XML documents by patterns［J］.Knowledge and Information Systems，2016，46 (1):185-212.

［9］ 劉顯敏，李建中.基于鍵規(guī)則的XML實(shí)體抽取方法［J］.計(jì)算機(jī)研究與發(fā)展，2014，51(1):64-75.

［10］于亞君，姜 瑛.一種XML的樹匹配改進(jìn)方法［J］.計(jì)算機(jī)工程與應(yīng)用，2012，48(20):177-181.

［11］Piernik M，Brzezinski D，Morzy T，et al.XML clustering:a review of structural approaches［J］.The Knowledge Engineering Review，2015，30(3):297-323.

［12］郭憲勇，陳性元，鄧亞丹.基于多核處理器的VTD—XML節(jié)點(diǎn)查詢執(zhí)行性能優(yōu)化［J］.計(jì)算機(jī)科學(xué)，2014，41(2):179-181.

［13］Mohan G B，Ravi T，Chandra J L E，et al.Duplicate detection in XML data using extended sub tree similarity function［J］. International Journal of Applied Engineering Research，2015，10(3):7325-7334.

［14］覃章榮，岑龍科，任新文，等.基于中心實(shí)體邏輯分組的XML關(guān)鍵字查詢算法［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2014，35 (6):2218-2223.

Simulation Research of XML Document Similarity Based on Path Weighting

ZHAO Yan-ni1，2，GUO Hua-lei3，MA Jun-sheng3
(1.Department of Computer Science，Shaanxi Vocational＆Technical College，Xi’an 710100，China; 2.School of Automation and Information Engineering，Xi’an University of Technology，Xi’an 710048，China; 3.Department of Information Service，Xi’an Communication College，Xi’an 710106，China)

In order to realize the rapid and accurate retrieval of the XML document information，a tree similarity algorithm based on path weight is proposed.It considers the tree node information similarity and structural similarity，and the information is arranged in each level of the tree in accordance with the degree of importance by object rules of primary and secondary information organization，making the degree of importance for tree node information weakened from up to down.According to the characteristics that the node with closer distance from the root node represents the more important information，and the lowest level of the information has minimal importance，the path weight is calculated automatically in accordance with the tree node in XML document tree level，which overcomes the disadvantage of equally distribution or manual setting for tree node information weigh in the traditional XML document，and solves the similarity calculation of XML document tree，and realizes the fast matching of XML query tree and document.Simulation shows that the algorithm is improved in query efficiency，precision and recall.

similarity;path weight;query tree;document tree

TP391.9

A

1673-629X(2016)09-0197-04

10.3969/j.issn.1673-629X.2016.09.044

2015-12-08

2016-04-05< class="emphasis_bold">網(wǎng)絡(luò)出版時(shí)間:

時(shí)間:2016-08-01

國(guó)家自然科學(xué)基金資助項(xiàng)目(61272284);陜西省自然科學(xué)基金(2014JM8354);陜西省教育重點(diǎn)實(shí)驗(yàn)室科技項(xiàng)目(13JS083)

趙艷妮(1982-)，女，博士研究生，講師，研究方向?yàn)槟Ｊ阶R(shí)別。

http://www.cnki.net/kcms/detail/61.1450.TP.20160801.0907.052.html