趙艷妮，郭華磊，馬軍生

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

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

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

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

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

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

0 引言

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

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

1 樹相似度

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

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

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

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

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

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

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

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

樹節(jié)點信息相似度僅僅反映了查詢樹的節(jié)點信息與文檔樹的節(jié)點信息的相似性，忽略了樹的結(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é)點;αuv表示在QT中節(jié)點u，v之間的路徑權(quán)重;LQTuv表示在QT 中u，v節(jié)點之間的路徑所包含的邊數(shù)量;LDTuv表示在DT中u，v節(jié)點之間的路徑所包含的邊數(shù)量。

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

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

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

1.3 相似度計算舉例說明

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

查詢樹QT路徑層數(shù)量LC(QT)為2，LayerAB= LayerAC=2，LayerBD=LayerBE=2，LQTAB=LQTAC= LQTBD=LQTBE=1。根據(jù)式(4)計算路徑權(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é)點，不存在路徑A→B，B→D，B→E，D節(jié)點最近的祖先是A節(jié)點，且路徑A→D存在，E節(jié)點類似。因此路徑A→D和A →E的權(quán)重計算要對路徑A→C進行權(quán)重分割，最后求和。權(quán)重分割原理α=αAB/n(n為節(jié)點B的子節(jié)點數(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 算法比較分析

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

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

3 實驗驗證

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

圖3 查詢效率

從查詢效率、查準率和查全率三個性能指標對上述四種算法進行比較。為了避免算法的局限性，給定了20棵完全不同的XML查詢樹，性能曲線上的每個點表示20棵查詢樹的平均值［14］。

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

4 結(jié)束語

針對XML文檔信息的有效查詢效率較低的問題，提出了基于路徑權(quán)重的XML文檔相似度匹配算法。依據(jù)日常工作生活中編輯信息的習慣，最重要的信息放在顯著位置，例如XML的樹根節(jié)點，根據(jù)信息的重要性依次排列在樹的各個層次，距離根節(jié)點越近的節(jié)點表示的信息越重要，依次排列，最低層信息的重要性最小。根據(jù)有效路徑在查詢樹的層次自動計算該有效路徑的權(quán)重，克服了人工指定路徑權(quán)重的缺陷，計算簡單有效。該算法有效信息量和有效節(jié)點間的結(jié)構(gòu)關(guān)系共同影響查詢樹和文檔樹的相似度，克服了僅僅依靠信息匹配、忽略信息之間關(guān)聯(liá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］.小型微型計算機系統(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］ 牛大偉，蘇龍超，韓雨童，等.基于擴展倒排索引的不確定XML關(guān)鍵字查詢算法［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］ 朱菁華，王曉玲.基于擴展查詢表達式的XML關(guān)鍵字查詢［J］.計算機工程，2014，40(10):25-31.

［7］ 張 苗，惠小強.一種快速的XML文檔驗證算法［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實體抽取方法［J］.計算機研究與發(fā)展，2014，51(1):64-75.

［10］于亞君，姜 瑛.一種XML的樹匹配改進方法［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é)點查詢執(zhí)行性能優(yōu)化［J］.計算機科學，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］覃章榮，岑龍科，任新文，等.基于中心實體邏輯分組的XML關(guān)鍵字查詢算法［J］.計算機工程與設(shè)計，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ò)出版時間:

時間:2016-08-01

國家自然科學基金資助項目(61272284);陜西省自然科學基金(2014JM8354);陜西省教育重點實驗室科技項目(13JS083)

趙艷妮(1982-)，女，博士研究生，講師，研究方向為模式識別。

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