宗傳霞

（蘭州交通大學(xué)電子與信息工程學(xué)院 甘肅 蘭州 730070）

0 引言

由于XML的特殊性,其信息數(shù)據(jù)急劇增長。現(xiàn)有的查詢算法通常都是先結(jié)構(gòu)查詢,在結(jié)構(gòu)匹配成功的基礎(chǔ)上再進(jìn)行內(nèi)容查詢。采用這些算法,不僅要遍歷很多結(jié)構(gòu)相關(guān)但內(nèi)容無關(guān)的XML文檔,而且也要對這些文檔結(jié)構(gòu)與查詢結(jié)構(gòu)做匹配,浪費了查詢時間。目前已有的近似查詢算法主要是靜態(tài)有序選擇算法[1]和動態(tài)加權(quán)減枝算法[3]等。但面對大規(guī)模的查詢時,這些算法的效率就會明顯降低。鑒于這種情況,改進(jìn)XML信息查詢技術(shù)具有必要性和緊迫性,這是XML查詢研究的主要動力。本文以提高并改進(jìn)XML查詢中匹配的關(guān)鍵技術(shù)為主要內(nèi)容,同時以如何提高其數(shù)據(jù)信息的查詢效率為主要目的,描述了一種既能夠在保證查全率的同時又對其查準(zhǔn)率有所提高的方法。

1 新方案的實現(xiàn)

XML文檔采用一種有序的樹型結(jié)構(gòu)來描述數(shù)據(jù),樹的節(jié)點對應(yīng)文檔中的元素、屬性或者文本數(shù)據(jù),而邊則表示元素與元素之間的關(guān)系。對XML文檔的查詢有兩種,以值為基礎(chǔ)的選擇查詢(內(nèi)容查詢)和以結(jié)構(gòu)為基礎(chǔ)的選擇查詢（結(jié)構(gòu)查詢）。

1.1 內(nèi)容查詢

在文獻(xiàn)[1]中提出了給查詢條件定義權(quán)重的概念,利用權(quán)重來體現(xiàn)查詢過程中的強(qiáng)弱,并且把這種強(qiáng)弱程度量化成[0,1]之間的數(shù)值,權(quán)重為0,表示在查詢過程中不起作用;權(quán)重小于1,例如權(quán)重為0.8,那么就表示查詢過程中該關(guān)鍵詞在本文檔中的重要程度為80%;權(quán)重為1,表示在查詢中起全部作用。一般來講,權(quán)重一般會取0與1之間（不包括0,1）的數(shù)值。下面主要從查詢詞的分類因子,語義因子,層次因子,容量因子等4點考慮對于詞項權(quán)重的影響。

1)分類因子

設(shè)C是分類因子,它反映的是用戶搜索內(nèi)容所屬類別的概率。

2)語義因子

在文檔中,越能表現(xiàn)文檔主題的詞項,其語義因子[2]越高。它的范圍在[0,1]之間。

3)層次因子

由于XML文檔存在嵌套的情況,因此同一個詞項出現(xiàn)在不同的層次中所反映的重要程度是不同的。在這里要指出的是根節(jié)點的層次就是樹的層次。層次因子[2]一般取整數(shù)。

4)容量因子

5)查詢關(guān)鍵詞的加權(quán)公式

綜上所述,本文新提出的查詢關(guān)鍵詞加權(quán)公式(1)為：

1.2 結(jié)構(gòu)查詢

在結(jié)構(gòu)查詢中主要涉及到了3種操作,刪除操作、插入操作和替換操作。

1)刪除操作：把相關(guān)文檔中與用戶查詢不相匹配的節(jié)點q刪除,其中α為刪除平衡因子( 實驗驗證一般取值0.5為最佳)[3],用來調(diào)整具體環(huán)境所決定的權(quán)重與刪除代價間變換的差異,見式(2)所示：

2)插入操作：該操作與刪除操作是相反操作,其中β為插入平衡因子（實驗驗證一般取值0.5為最佳）[3]，用來調(diào)整具體環(huán)境所決定的權(quán)重與插入代價變換的相似度。計算公式為(3)所示：

3)替換操作：替換主要分為兩類：全局替換和局部替換。也就是改變一個節(jié)點的標(biāo)簽,把相關(guān)文檔中的某個關(guān)鍵詞節(jié)點的標(biāo)簽 q i 更新為用戶查詢中的某個查詢關(guān)鍵詞節(jié)點的標(biāo)簽 q i ′ ,根據(jù)公式(1)得到替換操作的公式見(4)所示：

所以,在實際查詢中, W d o c文檔的權(quán)重值為 (非負(fù)), W q 為文檔中和用戶關(guān)鍵詞相匹配的詞項權(quán)重值之和,詞項權(quán)重的值是利用公式(1)求得。W o p e為各個編輯操作所耗費的權(quán)重值之和,根據(jù)具體情況,利用公式(2)～(4)分別把刪除操作、插入操作、替換操作的權(quán)重計算出來,并且相加得到權(quán)值之和。注意在很多情況下可能不會把刪除,插入,替換一起應(yīng)用,另外,又可能應(yīng)用插入,刪除或者替換多次。最后,用 W q 減去 W o p e 就是 W d o c 。具體定義公式(5)如下所示：

1.3 算法步驟及其流程圖

1)首先,輸入所查詢的XML信息,根據(jù)本文提出的公式(1)計算出關(guān)鍵詞權(quán)重,選擇大于閾值L(實驗驗證0.5為最佳)[4]的權(quán)重,并且按照由大到小的順序進(jìn)行排列。如果此時權(quán)重為1,則說明內(nèi)容完全匹配,返回結(jié)果,退出查詢即可;

2)其次,如果權(quán)重不為1,這時就要進(jìn)行結(jié)構(gòu)查詢,即利用刪除、插入、替換的操作使得文檔中的關(guān)鍵詞能夠和用戶查詢的信息進(jìn)行完全匹配,然后計算出各個操作所花費的權(quán)重代價之和;

3)最后,用關(guān)鍵詞權(quán)重減去各個編輯操作所花費的代價之和就是最終的權(quán)重值,然后,去掉閾值小于Q的權(quán)重,選擇大于閾值Q(實驗驗證0.5為最佳)[5]的權(quán)重并且按照從高到低進(jìn)行排序,返回最符合用戶查詢要求的文檔。

以下是根據(jù)算法步驟設(shè)計的詳細(xì)流程如圖1所示。

2 實驗

為了驗證該XML查詢方法改進(jìn)的效果,本文對改進(jìn)前的XML文檔查詢方法和基于編輯距離的XML查詢方法進(jìn)行了實驗,并且對實驗結(jié)果進(jìn)行了分析與對比。

圖1 XML查詢流程圖

2.1 實驗環(huán)境

實驗的平臺是Windows XP專業(yè)版,P4 2.8GHz CPU, 768M內(nèi)存,80GB硬盤。開發(fā)工具是在Microsoft Visual Studio.NET 2003(實 現(xiàn) 語 言 為vb.net)、Microsoft SQL Server 2000環(huán)境下設(shè)計并實現(xiàn)的。

INEX[6]（Initiative for the Evaluation of XML Retrieval的縮寫）是XML信息檢索中具有代表性的文檔集,其資源的核心內(nèi)容是從1995年到2000年出版的1.2萬篇期刊文章.本文選取了INEX 2006上的Wikipedia XML文集進(jìn)行實驗的測試,該實驗數(shù)據(jù)集共包含659388篇文章,約4600MB大小,文檔的平均大小約為7.1M,平均深度為6層,每篇文檔所包含的平均結(jié)點數(shù)為161.26個。

TopX2.0[7]是一個針對半結(jié)構(gòu)化的XML文檔的檢索排序引擎,它以擴(kuò)展了的經(jīng)典概率論理論為基礎(chǔ),能夠?qū)δ：齼?nèi)容和結(jié)構(gòu)的XML文檔進(jìn)行查詢和排序顯示。

2.2 實驗結(jié)果

TopX2.0的查詢結(jié)果以文檔為單位顯示,其中關(guān)鍵詞的權(quán)重是檢索記分標(biāo)準(zhǔn),最后按照文檔中的關(guān)鍵詞的最大分值進(jìn)行排序輸出,它可以實現(xiàn)CO(content-only即查詢表達(dá)式中只有查詢詞)和CAS(content and structure即查詢表達(dá)式中包含查詢詞和路徑信息)兩種查詢方式.因為所測試的數(shù)據(jù)集過于龐大，PC上將難以勝任所有文檔的解析操作,在所有完整文檔集上進(jìn)行檢索的效率非常緩慢,所以要先在TopX2.0上發(fā)出查詢請求并進(jìn)行檢索,然后再在檢索結(jié)果中的前100篇文檔上進(jìn)行測試。

在測試的實驗中,盡可能地模擬用戶的查詢行為,根據(jù)調(diào)查統(tǒng)計：一般用戶在查詢時的查詢關(guān)鍵詞不大于5個的平均概率為80%;考慮到用戶在查看結(jié)果時,也不會將所用的相關(guān)文檔都打開瀏覽,而往往希望在第一個頁面（通常為10個結(jié)果）就能找到自己所需的信息.實驗主要評測指標(biāo)為P@10[8]（P@10 常常能比較有效地反映系統(tǒng)在真實應(yīng)用環(huán)境下所表現(xiàn)的性能）,它是對于該主題返回的前10個結(jié)果的準(zhǔn)確率.實驗任意的選擇了10組查詢關(guān)鍵詞。下面以一組簡單的例子進(jìn)行說明,當(dāng)用戶輸入查詢Q1：//[about(.,Chinese new year in the culture)],根據(jù)本文前面所定義的公式,可以計算出文檔的權(quán)重值并排序輸出,查詢具體對比結(jié)果值如表1所示。

在打開輸出的結(jié)果文檔中進(jìn)行查閱,可以看到在文檔“Chinese new year”中所包含的內(nèi)容最符合用戶的查詢要求,而且文檔中有和用戶查詢完全匹配的關(guān)鍵詞,但是在初始查詢中它卻排到第四.同時,也可以看到在初始查詢中排第一的文檔實際是和查詢條件很不匹配的。

3 結(jié)束語

表1 實驗的對比結(jié)果

本文針對XML信息查詢中查詢效率不高的情況提出了基于編輯距離的XML查詢方法,它主要分為內(nèi)容查詢,結(jié)構(gòu)查詢兩步。并且對結(jié)果進(jìn)行了排序,以便查詢出用戶最需要的文檔。通過實驗驗證,該方法在保證查全率的同時對查準(zhǔn)率有一定程度的提高。

[1] J.P.TimBray,C.M.Sperberg-McQueen,F.Yergeau. ExtensibleMarkup Language(XML)1.0(third Edition). W3C Recommendation 04 February 2004.http://www. w3.org/TR/REC-XML/,2004.

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

[3] ClarkJ,DeRose S.XML path language(XPath) version1.0 w3c recommendation.World Wide Web Consortium,1999.

[4] 陳恩紅,許斗,錢海.基于XML的圖形結(jié)構(gòu)數(shù)據(jù)表示的解決方案及其比較[J].計算機(jī)工程,2002, 28(5):6-19.

[5] 王宏志.XML數(shù)據(jù)查詢處理技術(shù)的研究[D]:哈爾濱：哈爾濱工業(yè)大學(xué),2008.

[6] TORSHEN S,NAUMANN F.Approximate tree embedding for querying XML data[C]//Proc of ACM SIGIR Workshop on XML and Information Retrieval A thens:[sn],2000.

[7] 沈劍滄,鮑培明.XML查詢a方法的設(shè)計與研究[J].計算機(jī)工程,2007,21(33)：63-65.

[8] 郭俊文,衡星辰,邵利平,等.一種基于XML文檔聚類的XML近似查詢算法[J].計算機(jī)工程,2006,32(15):52-54.