一種基于結構耦合度的推斷目標節點的方法

李瑞霞，蘇守寶，周先存

（皖西學院信息工程學院，安徽 六安 237012）

近年來XML關鍵字檢索的方法大量用于信息檢索中，主要得益于它帶給用戶很多便利，用戶不必了解XML文檔的結構或者掌握復雜的查詢語言，就可以獲得比較理想的結果.許多研究都注重如何有效地獲得關鍵字匹配的節點（XSEarch，SLCA）［1－2］返回查詢結果.然而這只是解決了信息檢索問題的一個方面.即返回結果可能是有意義的，卻不一定是用戶所期望的.因此，問題的另一個方面就是如何準確地推斷用戶的查詢意圖.在一篇文檔中一個關鍵字可能會有多個意義，例如，用戶輸入的查詢關鍵字是｛volume，11｝，在一篇文章中“11”可能表示文章所在的頁面，也可能表示該文章于第“11”期出版，到底用戶的目標節點是什么呢？往往是很難判斷的.

為了解決關鍵字的二義性，文獻［3］通過一種改進的TF－IDF排序模型，利用關鍵字出現的頻率來推斷用戶的查詢目標節點.文獻［4］將關鍵字出現的位置進行分別考慮，即分別對元素節點和文本節點賦予不同的系數，進而結合文檔的層次改進了XReal的方法.但是以上的方法都是強調了關鍵字出現的頻率，沒有考慮文檔的結構，盡管分別涉及了關鍵字所在的層次，但是因子r是不變的.文獻［5］針對XReal方法提出了動態調節因子r的方法，雖然查詢精度有所改變，但沒有考慮XML中的結構耦合度對目標節點的影響.本文提出一種考慮文檔結構耦合度的推斷目標節點的方法，該方法一方面考慮關鍵字出現的頻率，同時也考慮了關鍵字所在路徑的層次，通過對某一路徑中重復的路徑數進行分析，準確地推斷用戶的目標節點.

1 相關方法

1.1 XML文檔的表示

一篇XML文檔通常可以看作由連接節點和葉子節點組成的無序樹結構，其中連接節點表示元素或者屬性節點，葉子節點指的是文本節點即元素或者屬性的值.圖1展示了一個XML文檔的樹結構.

定義1：節點類型，本文用root表示一棵樹的根節點即文檔的根元素，節點n的類型就是從根節點到節點n的路徑.如果n是一個葉子節點，則它的路徑用其雙親的路徑來表示.

一個節點的類型準確地表示了該節點的意義.如圖1所示，author節點的類型即路徑（sigmord Record，issue，articles，article，author）.為了描述簡單起見，本文在余下的部分將用節點名稱代替其路徑來表示節點的類型.

關鍵字查詢指的是獲取由查詢關鍵字組成的有限集合，例如，給定一個關鍵字查詢｛k1，k2｝和一篇文檔，用t表示文檔的樹結構.關鍵字查詢就是在樹t中查找所有的連接節點和葉子節點中包含關鍵字｛k1，k2｝的節點片段.

圖1 SigmodRecord數據集部分結構

1.2 XReal

XReal作為一個獲取目標節點的典型方法，利用一個實例來簡要闡述其主要思想.一般來講，每一次查詢只可能有一個期望的目標節點，在XReal中利用下面的方法獲得目標節點.

1.3 耦合度

耦合度是軟件設計中各個構件之間相互關聯程度的一種度量［6］.耦合度的強弱往往取決于各構件間的接口復雜性、進入或調用模塊的位置、方式以及通過接口傳送數據的多少等，在設計一個軟件時應該追求盡可能松散耦合的系統.通常在面向構件的軟件設計中，構件的內聚度體現的是構件各成分間相互的緊密程度.也就是說，它可以度量單個構件所完成的各類任務在功能上的相互關聯程度.隨著面向構件技術的廣泛應用，面向構件系統的內聚度和耦合度概念已成為一個重要的研究方向.

文獻［7］在獲取用戶查詢目標節點的方法中也涉及了結構耦合的概念，本文為了能準確地推斷目標節點的類型，將耦合度的概念應用到樹結構中來，首先對路徑之間的耦合關系進行分析，然后，引入結構耦合度的概念，最后，提出一種基于結構耦合度的目標節點推斷方法.

2 目標節點推斷方法

2.1 結構耦合度

從以上的分析中可以看出，XReal方法在結構樹中層次比較多的時候，一些目標節點可能因為指數函數遞減過快而導致得分小于它的祖先節點，因此，最后返回給用戶的就是一些無意義的信息.究其根源主要是公式的第二部分不能起到很好的抑制作用.本文將借鑒軟件工程中耦合度的概念分析樹結構中路徑的耦合度，以此對XReal方法中的抑制因子進行適度的調節.

如圖2所示的樹結構中對于給定的查詢｛k1，k2｝，圖中A1，A2和A3都可以作為目標節點返回，并且3個結構中查詢節點出現的頻率相同，路徑的層次也相同，然而，A1和A3的結構為一個緊耦合的結構，A1和A3類型的路徑中重復的路徑比較多，因此我們通常認為，A1和A3比A2更能準確地反映用戶的查詢意圖.

本文規定節點所在的層次數減去包含了查詢關鍵字的最低共同祖先節點的層次數來得到某類型節點的結構耦合度［8］.如圖2所示，A1和A3的耦合度是2，而A2的耦合度是1.顯然結構耦合度越高的節點類型越接近用戶的查詢目標.因此本文通過結合文章中節點出現的頻率、節點所在的層次，同時利用樹結構中耦合度來避免因抑制因子遞減過快導致錯誤的推斷.

圖2 不同耦合度的樹結構

2.2 相關度計算模型

經過如上的分析，本文定義目標節點的計算公式為

式中：depth（T）－θ表示結構的耦合度；θ表示k出現的路徑中重復的路徑數.然后針對結構中有部分或者極少數路徑層次比較大的情況，本文為了避免層次不均勻出現的異常情況，對其做如下的處理：

式中：avg－depth表示一個文檔樹結構平均的路徑長度；η是一個取值在［0，1］之間的調節參數.通過引入結構耦合度的概念可以保證目標節點包含足夠的信息量.同時對于給定關鍵字檢索，由于XML文檔的樹形結構特征，使得層次越深的節點很有可能具有更高的計算結果，本文通過一個分段函數來均衡結構不均勻出現的異常，也在一定程度上去掉了冗余的信息.

3 實驗分析

本文實驗平臺采用Windows Server 2000，實驗數據分別選擇了DBLP和SigmodRecord做測試，利用Java編程實現所提出的方法，對比方法選擇了XReal.關鍵字出現的位置隨機測試，可能出現在XML文檔中的元素節點，也可能是在屬性節點或文本節點上，所使用的測試用例涵蓋了這幾種關鍵字出現的位置信息.DBLP和SigmodRecord數據集都記錄了關于文章的信息，雖然結構語義較簡單，但是信息量相對大一些.部分測試結果見表1.從表1的查詢結果可以看出，在數據信息較少的情況下XReal可以較為準確地獲得目標節點的類型，但是隨著數據量的增大，XReal過度的夸大了詞頻的作用，在層次較大的結構中，如果結構耦合度比較低，結果導致將目標節點的祖先節點返回.而本文所提出的方法很好地解決了該問題.

表1 2種數據集上的部分測試結果

查準率是衡量信息檢索質量的一個重要指標，圖3表示的是在2種不同的數據集下，平均的查準率.從圖3中可以看出，本文所提出的方法在數據量比較大的情況下優勢更為明顯.結果更為準確.

圖3 2種數據集下的查準率的比較

4 結論

在信息檢索中能否準確地推斷出用戶的查詢意圖，對查詢結果起著至關重要的作用.由于XML數據半結構化的特征和查詢關鍵字的二義性使得推斷目標節點成為難題.本文經過分析現有研究的不足，提出了一種目標節點的推斷方法，該方法分別結合詞頻和關鍵字的路徑耦合度推斷目標節點.最后對結構不均勻的情況也做了處理，可以去除部分的冗余信息.實驗證明，與現有主流算法相比較，本文提出的方法能夠更準確地推斷出用戶的查詢意圖.我們今后將就檢索效率進行研究，以進一步提高本文算法的查詢性能.

［1］COHEN S，MAMOU J，KANZA Y，et al.A semantic search engine for XML［C］.In Proceedings of the 29th VLDB Conference，Berlin，Germany，2003：45－56.

［2］LIU Z，CHEN Y.Identifying meaningful return information for XML keyword search［C］.In：Chan C Y，Ooi B C，Zhou A（eds.）.New York：SIGMOD Conference，2007：329－340.

［3］BAP Z，LING TW，CHEN B，et al.Effective XML keyword search with relevance oriented ranking［C］.In：ICDE，IEEE International Conference on Data Engineering，Los Alamitos，2009：517－528.

［4］郭文琪，陳群，婁穎.一種推斷 XML關鍵字檢索目標節點的方法［J］.計算機工程，2012，38（8）：41－49.

［5］JIANG LI，JUNHU WANG.Effectively inferring the search－for node type in XML keyword search［J］.Lecture Notes in Computer Science，2010，5981：110－124.

［6］郁湧，張坤.基于結構熵的構件耦合性度量方法［J］.計算機應用與軟件，2012，29（6）：33－35.

［7］JIANXIN Li，CHENGFEI LIU，RUI ZHOU.XML keyword search with promising result type recommendations［DB］.World Wide Web，2013：1－33.

［8］XU Y，PAPAKONSTANTINOU Y.Efficient keyword search for smallest LCAs in XML databases［M］.In Ozcan F，ed.Proc of the ACM SIGMOD Int'1Conf on Management of Data，Baltimore：ACM Press，2005：537－538.