一種基于結(jié)構(gòu)耦合度的推斷目標(biāo)節(jié)點(diǎn)的方法

李瑞霞，蘇守寶，周先存

（皖西學(xué)院信息工程學(xué)院，安徽 六安 237012）

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

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

1 相關(guān)方法

1.1 XML文檔的表示

一篇XML文檔通?？梢钥醋饔蛇B接節(jié)點(diǎn)和葉子節(jié)點(diǎn)組成的無序樹結(jié)構(gòu)，其中連接節(jié)點(diǎn)表示元素或者屬性節(jié)點(diǎn)，葉子節(jié)點(diǎn)指的是文本節(jié)點(diǎn)即元素或者屬性的值.圖1展示了一個(gè)XML文檔的樹結(jié)構(gòu).

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

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

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

圖1 SigmodRecord數(shù)據(jù)集部分結(jié)構(gòu)

1.2 XReal

XReal作為一個(gè)獲取目標(biāo)節(jié)點(diǎn)的典型方法，利用一個(gè)實(shí)例來簡要闡述其主要思想.一般來講，每一次查詢只可能有一個(gè)期望的目標(biāo)節(jié)點(diǎn)，在XReal中利用下面的方法獲得目標(biāo)節(jié)點(diǎn).

1.3 耦合度

耦合度是軟件設(shè)計(jì)中各個(gè)構(gòu)件之間相互關(guān)聯(lián)程度的一種度量［6］.耦合度的強(qiáng)弱往往取決于各構(gòu)件間的接口復(fù)雜性、進(jìn)入或調(diào)用模塊的位置、方式以及通過接口傳送數(shù)據(jù)的多少等，在設(shè)計(jì)一個(gè)軟件時(shí)應(yīng)該追求盡可能松散耦合的系統(tǒng).通常在面向構(gòu)件的軟件設(shè)計(jì)中，構(gòu)件的內(nèi)聚度體現(xiàn)的是構(gòu)件各成分間相互的緊密程度.也就是說，它可以度量單個(gè)構(gòu)件所完成的各類任務(wù)在功能上的相互關(guān)聯(lián)程度.隨著面向構(gòu)件技術(shù)的廣泛應(yīng)用，面向構(gòu)件系統(tǒng)的內(nèi)聚度和耦合度概念已成為一個(gè)重要的研究方向.

文獻(xiàn)［7］在獲取用戶查詢目標(biāo)節(jié)點(diǎn)的方法中也涉及了結(jié)構(gòu)耦合的概念，本文為了能準(zhǔn)確地推斷目標(biāo)節(jié)點(diǎn)的類型，將耦合度的概念應(yīng)用到樹結(jié)構(gòu)中來，首先對路徑之間的耦合關(guān)系進(jìn)行分析，然后，引入結(jié)構(gòu)耦合度的概念，最后，提出一種基于結(jié)構(gòu)耦合度的目標(biāo)節(jié)點(diǎn)推斷方法.

2 目標(biāo)節(jié)點(diǎn)推斷方法

2.1 結(jié)構(gòu)耦合度

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

如圖2所示的樹結(jié)構(gòu)中對于給定的查詢｛k1，k2｝，圖中A1，A2和A3都可以作為目標(biāo)節(jié)點(diǎn)返回，并且3個(gè)結(jié)構(gòu)中查詢節(jié)點(diǎn)出現(xiàn)的頻率相同，路徑的層次也相同，然而，A1和A3的結(jié)構(gòu)為一個(gè)緊耦合的結(jié)構(gòu)，A1和A3類型的路徑中重復(fù)的路徑比較多，因此我們通常認(rèn)為，A1和A3比A2更能準(zhǔn)確地反映用戶的查詢意圖.

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

圖2 不同耦合度的樹結(jié)構(gòu)

2.2 相關(guān)度計(jì)算模型

經(jīng)過如上的分析，本文定義目標(biāo)節(jié)點(diǎn)的計(jì)算公式為

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

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

3 實(shí)驗(yàn)分析

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

表1 2種數(shù)據(jù)集上的部分測試結(jié)果

查準(zhǔn)率是衡量信息檢索質(zhì)量的一個(gè)重要指標(biāo)，圖3表示的是在2種不同的數(shù)據(jù)集下，平均的查準(zhǔn)率.從圖3中可以看出，本文所提出的方法在數(shù)據(jù)量比較大的情況下優(yōu)勢更為明顯.結(jié)果更為準(zhǔn)確.

圖3 2種數(shù)據(jù)集下的查準(zhǔn)率的比較

4 結(jié)論

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

［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關(guān)鍵字檢索目標(biāo)節(jié)點(diǎn)的方法［J］.計(jì)算機(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］郁湧，張坤.基于結(jié)構(gòu)熵的構(gòu)件耦合性度量方法［J］.計(jì)算機(jī)應(yīng)用與軟件，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.