基于關(guān)鍵字權(quán)重及結(jié)構(gòu)擴(kuò)展的XML檢索

路芳瑞

(山西財經(jīng)大學(xué)實驗教學(xué)中心, 山西 太原 030006)

0 引 言

由于具有結(jié)構(gòu)化、可擴(kuò)展性、跨平臺等特點(diǎn)，XML(eXtensible Markup Language)[1]逐漸成為信息存儲與交換的主要格式，XML文檔數(shù)量隨之迅速增長.XML文檔在科學(xué)數(shù)據(jù)庫、數(shù)字圖書館以及互聯(lián)網(wǎng)等領(lǐng)域應(yīng)用日益廣泛，對這些海量的XML文檔數(shù)據(jù)進(jìn)行高效準(zhǔn)確的檢索就成為信息檢索領(lǐng)域一個很有意義的研究方向[2-7].信息檢索中查詢表達(dá)式的準(zhǔn)確與否，對檢索結(jié)果的準(zhǔn)確性有很大影響.XML文檔是一種半結(jié)構(gòu)化的文檔，其除了具有文本文檔的內(nèi)容特征外，還具有結(jié)構(gòu)特征,因而對XML文檔進(jìn)行檢索時表達(dá)查詢意圖的查詢表達(dá)式中應(yīng)當(dāng)不僅包含查詢關(guān)鍵字，還應(yīng)當(dāng)包含表達(dá)查詢意圖的結(jié)構(gòu)表達(dá)式.目前雖然可以采用XPath描述查詢結(jié)構(gòu)表達(dá)式，但這需要用戶專門學(xué)習(xí)相關(guān)語法，并且需要用戶對文檔的結(jié)構(gòu)信息有一定的了解，這對絕大多數(shù)用戶來說都是困難的,因而通過反饋幫助用戶形成查詢表達(dá)式是提高XML文檔檢索準(zhǔn)確性的一種好的方法.

1 XML檢索的類型與特點(diǎn)

INEX(Initiative for the Evaluation of XML Retrieval)[8]根據(jù)不同XML檢索的特點(diǎn)，將其分為兩種類型：純內(nèi)容(CO)檢索、內(nèi)容與結(jié)構(gòu)(CAS)檢索.其中CO(Context Only)檢索，是僅通過關(guān)鍵字進(jìn)行檢索，類似于傳統(tǒng)的文本檢索；CAS(Context And Structure)檢索是指查詢表達(dá)式中同時包含關(guān)鍵字內(nèi)容表達(dá)式和結(jié)構(gòu)表達(dá)式的檢索.在XML文檔的這兩種檢索中，CO檢索只需要用戶提出自己的查詢關(guān)鍵字，用戶接口比較友好，但未能充分利用XML文檔的結(jié)構(gòu)信息，導(dǎo)致結(jié)果中可能出現(xiàn)很多不相關(guān)的結(jié)果，因而檢索的準(zhǔn)確性不高.在CAS檢索中，查詢表達(dá)式可以同時包含查詢內(nèi)容表達(dá)式和結(jié)構(gòu)表達(dá)式，在準(zhǔn)確提出查詢表達(dá)式的前提下，檢索準(zhǔn)確性較CO檢索有了很大提高.然而CAS檢索對大多用戶而言，準(zhǔn)確輸入結(jié)構(gòu)查詢表達(dá)式比較困難，這是因為結(jié)構(gòu)表達(dá)式的提出需要用戶熟悉XPath、XQuery、XSearch等相關(guān)語法，有時還需要用戶對目標(biāo)文檔的結(jié)構(gòu)比較熟悉.針對CAS檢索中存在的這種用戶接口不太友好的缺陷，本文提出了一種基于關(guān)鍵字權(quán)重及結(jié)構(gòu)擴(kuò)展的XML檢索方法.對于CAS查詢可以理解為查詢詞表達(dá)式,主要表示內(nèi)容上檢索者的內(nèi)容查詢意圖，查詢中的結(jié)構(gòu)表達(dá)式是對內(nèi)容的限定，即檢索結(jié)果的結(jié)構(gòu)信息要符合查詢結(jié)構(gòu)表達(dá)式.根據(jù)這種理解，本文的檢索方法通過計算關(guān)鍵字的權(quán)重進(jìn)行檢索得到中間檢索結(jié)果，然后再對中間檢索結(jié)果進(jìn)行結(jié)構(gòu)擴(kuò)展進(jìn)一步檢索，進(jìn)而得到最終的查詢結(jié)果.

2 關(guān)鍵字權(quán)重的計算及查詢結(jié)構(gòu)擴(kuò)展

2．1 關(guān)鍵字權(quán)重的計算

用戶查詢的相關(guān)元素或相關(guān)文檔中詞項的權(quán)重計算是檢索的核心問題.傳統(tǒng)的文本信息檢索中查詢詞的權(quán)重計算主要考慮詞項在文檔中出現(xiàn)的頻率因素及文檔的大小因素，最常用的就是TF*IDF方法[9].XML文檔是結(jié)構(gòu)化的文檔，并且結(jié)構(gòu)信息對檢索的結(jié)果也有很大的影響，因此，本文將結(jié)構(gòu)信息對查詢詞權(quán)重的影響作為本文著重研究的一個問題.本文主要從查詢詞在文檔中的層次位置、詞項在文檔中的語義約束、文檔的大小這三點(diǎn)考慮對于查詢詞權(quán)重的影響，在此基礎(chǔ)上對TF*IDF進(jìn)行修改，得出適合XML文檔的查詢詞權(quán)重計算公式.

圖1 一個XML文檔樹例子

2．1．1 關(guān)鍵字在文檔中的層次位置對權(quán)重的影響

嵌套在XML文檔中普遍存在，因此同樣的查詢詞可能出現(xiàn)在不同的標(biāo)簽層次中，傳統(tǒng)的文本檢索中對出現(xiàn)在不同層次的查詢詞看做具有相同的權(quán)重，這顯然是不合適的.經(jīng)過對隨機(jī)抽取的一些樣本文檔進(jìn)行人工調(diào)查統(tǒng)計，我們發(fā)現(xiàn)層次越高的關(guān)鍵詞，通常詞項的權(quán)重也越大一些.在如圖1所示的XML樹形文檔中，第二層、第四層都含有title節(jié)點(diǎn)，但是他們對文檔主題的重要程度顯然是不同的，層次高的節(jié)點(diǎn)對文檔的主題的重要程度更高一些.

2．1．2 文檔節(jié)點(diǎn)元素語義對關(guān)鍵字權(quán)重的影響

XML文檔中有不同的節(jié)點(diǎn)元素，不同的節(jié)點(diǎn)元素中可能包含相同的關(guān)鍵詞，本文認(rèn)為對文檔主題貢獻(xiàn)大的節(jié)點(diǎn)元素，其所包含的詞項對文檔主題的貢獻(xiàn)也比較大.在圖1的XML文檔中title節(jié)點(diǎn)中出現(xiàn)的詞項顯然比paragraph中出現(xiàn)的詞項更能反映文檔的主題.據(jù)此，本文對文檔中的節(jié)點(diǎn)元素設(shè)置語義權(quán)重，以反映檢索中元素的重要程度，并根據(jù)詞項所屬節(jié)點(diǎn)元素的語義權(quán)重來判斷詞項的重要程度.

2．1．3 文檔的大小對關(guān)鍵字權(quán)重的影響

本文把文檔大小對查詢詞權(quán)重影響的因素稱為長度因子，它是由某個詞項所在文檔的總長度決定的.一個文檔內(nèi)的詞項越多，其長度因子就越小，而且這個詞項所在文檔的權(quán)重也會隨之被降低.例如一個大小為5 k的文檔中出現(xiàn)了某個檢索詞一次，同時另一個長度為15 k的文檔也出現(xiàn)了某個檢索詞一次，可以看出，在前一文檔中查詢詞更能反映文檔的主題.

2．1．4 關(guān)鍵字的權(quán)重計算公式

在傳統(tǒng)的文本檢索中，關(guān)鍵字權(quán)重的計算主要考慮詞頻(Term Frequency)權(quán)值和反向文檔頻率(Inverse Document Frequency)權(quán)值.關(guān)鍵詞tj在文檔di中出現(xiàn)的頻率記為tfij，其中在文檔中出現(xiàn)的頻率過高的詞要排除.關(guān)鍵詞tj的反向文檔頻率權(quán)值記為idfj，其計算方法為：idfj=ln(N/nj)+1，其中N為文檔集中文檔的數(shù)量，nj為出現(xiàn)關(guān)鍵詞tj的文檔的數(shù)量.

由于tf*idf是針對文本檢索提出的權(quán)重計算方法，根據(jù)前面分析的XML文檔中影響關(guān)鍵字權(quán)重的因素，本文對tf*idf公式進(jìn)行了調(diào)整，本文計算關(guān)鍵字權(quán)重的公式為：

(1)

2．2 結(jié)構(gòu)查詢擴(kuò)展的生成

在XML文檔檢索中，檢索表達(dá)式中的內(nèi)容表達(dá)式和結(jié)構(gòu)表達(dá)式是緊密相關(guān)的.具體而言，與內(nèi)容表達(dá)式中的查詢詞緊密相關(guān)的就是詞項所屬的元素信息.據(jù)此，本文提出的結(jié)構(gòu)查詢擴(kuò)展的方法是：對于在相關(guān)文檔中出現(xiàn)的查詢擴(kuò)展詞keywordi，分別在相關(guān)文檔中找到語義權(quán)重最大的元素tagi,則tagi-keywordi作為結(jié)構(gòu)查詢擴(kuò)展，對于內(nèi)容表達(dá)式中有多個關(guān)鍵字，則用多個tag-keyword組成的關(guān)系表達(dá)式作為結(jié)構(gòu)查詢擴(kuò)展.本文中的查詢擴(kuò)展表達(dá)式采用INEX的查詢語言NEXI表示，結(jié)構(gòu)查詢擴(kuò)展表達(dá)式的示例如下：

//Doc[about(.//tag1,keyword1) and about(.//tag2,keyword2) and ...]

結(jié)合前面所述，本文提出的檢索方法可描述如下：

(1) 根據(jù)公式1計算文檔中詞項的權(quán)重；

(2) 根據(jù)檢索詞得到擴(kuò)展查詢詞集合；

(3) 根據(jù)檢索詞及擴(kuò)展查詢詞集合生成tag-keyword集合；

(4) 根據(jù)用戶的反饋，生成查詢表達(dá)式；

(5) 返回檢索結(jié)果.

3 實驗及結(jié)果

實驗平臺是Intel E4400 2GHz CPU，1.00G內(nèi)存，Windows XP Sp3操作系統(tǒng)，實現(xiàn)語言為Java.本文的測試數(shù)據(jù)集為INEX2006的WikipediaXML文集，實驗中對檢索詞的排序采用了TopX檢索排序引擎.

表1 實驗初始查詢詞及擴(kuò)展查詢

圖2 擴(kuò)展前后的準(zhǔn)確率比較

測驗中，考慮到用戶在查看結(jié)果時，通常不會將所有的檢索結(jié)果都打開瀏覽，而是希望在檢索結(jié)果的第一個頁面(通常為10個結(jié)果)就能找到自己所需的信息，因而實驗主要的評測指標(biāo)為P@10，即對于檢索返回的前10個結(jié)果的準(zhǔn)確率.本實驗隨機(jī)的選擇了7組關(guān)鍵字進(jìn)行比較，它們的初始查詢詞、擴(kuò)展后的查詢表達(dá)式如表1所示，擴(kuò)展前后的檢索結(jié)果準(zhǔn)確率的對比如圖2所示.

4 結(jié)束語

本文提出的基于關(guān)鍵字權(quán)重及結(jié)構(gòu)擴(kuò)展的XML檢索方法能夠幫助用戶提出更能反映其檢索意圖的查詢表達(dá)式，并且實驗證明該方法在對XML數(shù)據(jù)進(jìn)行檢索時，在用戶選取合適的反饋后，檢索的準(zhǔn)確性也比較好.尋求更高效、更準(zhǔn)確、更友好的檢索方法是今后努力的方向.

參考文獻(xiàn)

[1] Extensible Markup Language (XML). http://www.w3.org/XML/.2011-04-23.

[2] 李劍波,李小華.基于XML的反饋式信息檢索系統(tǒng)研究[J].情報檢索,2005,24(10):72-74.

[3] 劉喜平,萬常選,劉德喜. 有效的XML模糊內(nèi)容與結(jié)構(gòu)檢索計分[J].計算機(jī)研究與發(fā)展,2010,47(6):1 070-1 078.

[4] 萬常選,魯 遠(yuǎn).基于權(quán)重查詢詞的XML結(jié)構(gòu)查詢擴(kuò)展[J].軟件學(xué)報,2008,19(10):2 611-2 619.

[5] 李元韜,曹志宇,李敬文.基于權(quán)重編輯距離的XML查詢[J].蘭州交通大學(xué)學(xué)報,2010,29(3):108-111.

[6] 李露平,王秋月,王 珊.XML元素級檢索的反饋算法[J].計算機(jī)工程與應(yīng)用,2010,46(11):131-134.

[7] 黃 靜,陸嘉恒,孟小峰.高效的XML關(guān)鍵字查詢改寫和結(jié)果生成技術(shù)[J].計算機(jī)研究與發(fā)展,2010,47(5):841-848.

[8] Saadia M,Andrew T,Mounia L,etal. Overview of INEX 2006[R].2006:1-11.

[9] 王 園,龔尚福.基于二次TF* IDF 的互信息文本特征選擇算法研究[J].計算機(jī)應(yīng)用與軟件,2011,28(4):129-131.