基于路徑權重的XML文檔相似度仿真研究

趙艷妮，郭華磊，馬軍生

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

基于路徑權重的XML文檔相似度仿真研究

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

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

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

相似度;路徑權重;查詢樹;文檔樹

0 引言

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

文中在文獻［4］的基礎上，提出一種自動計算查詢樹與文檔樹相似度的方法，克服了需要用戶設置路徑權重的缺點。該方法根據有效信息在查詢樹中的位置確定信息的重要程度，自動計算路徑權重并賦予相應路徑，綜合考慮有效節點信息和有效節點間的結構關系來計算查詢樹與文檔樹之間的相似度，滿足用戶對XML文檔的精確匹配和模糊匹配。

1 樹相似度

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

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

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

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

1.1 樹節點信息相似度

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

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

1.2 樹結構相似度

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

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

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

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

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

1.3 相似度計算舉例說明

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

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

同理，α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節點，不存在路徑A→B，B→D，B→E，D節點最近的祖先是A節點，且路徑A→D存在，E節點類似。因此路徑A→D和A →E的權重計算要對路徑A→C進行權重分割，最后求和。權重分割原理α=αAB/n(n為節點B的子節點數量)［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］路徑權重:αAB=0.25，αAC= 0.25，αBD=0.25，αBE=0.25。結果如表1所示。

分析表1可知，文獻［6-7］的相似度算法都存在一定缺陷。QT和DT5樹節點信息和樹結構都完全相同，匹配度應該等于1，但文獻［6］的相似度小于1，與客觀事實不符;QT和DT1樹結構不一致，并且DT1有F節點冗余信息，文獻［7］算法的相似度卻等于1，與客觀事實不符。通過比較分析，文中算法明顯優于其他三種算法，且符合客觀事實。研究發現文檔樹的有效信息數量與相似度并不嚴格保持正比，有效信息量多并且樹結構相似度高的文檔樹相似度才高，檢索結果更接近查詢信息。總之，相似度越接近1效果越好。

3 實驗驗證

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

圖3 查詢效率

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

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

4 結束語

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

［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］.小型微型計算機系統，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關鍵字查詢算法［J］.計算機應用與軟件，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關鍵字查詢［J］.計算機工程，2014，40(10):25-31.

［7］ 張 苗，惠小強.一種快速的XML文檔驗證算法［J］.計算機技術與發展，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］ 劉顯敏，李建中.基于鍵規則的XML實體抽取方法［J］.計算機研究與發展，2014，51(1):64-75.

［10］于亞君，姜 瑛.一種XML的樹匹配改進方法［J］.計算機工程與應用，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節點查詢執行性能優化［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關鍵字查詢算法［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">網絡出版時間:

時間:2016-08-01

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

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

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