基于編輯距離的X M L查詢方法★

宗傳霞

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

0 引言

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

1 新方案的實現

XML文檔采用一種有序的樹型結構來描述數據,樹的節點對應文檔中的元素、屬性或者文本數據,而邊則表示元素與元素之間的關系。對XML文檔的查詢有兩種,以值為基礎的選擇查詢(內容查詢)和以結構為基礎的選擇查詢（結構查詢）。

1.1 內容查詢

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

1)分類因子

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

2)語義因子

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

3)層次因子

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

4)容量因子

5)查詢關鍵詞的加權公式

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

1.2 結構查詢

在結構查詢中主要涉及到了3種操作,刪除操作、插入操作和替換操作。

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

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

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

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

1.3 算法步驟及其流程圖

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

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

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

以下是根據算法步驟設計的詳細流程如圖1所示。

2 實驗

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

圖1 XML查詢流程圖

2.1 實驗環境

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

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

TopX2.0[7]是一個針對半結構化的XML文檔的檢索排序引擎,它以擴展了的經典概率論理論為基礎,能夠對模糊內容和結構的XML文檔進行查詢和排序顯示。

2.2 實驗結果

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

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

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

3 結束語

表1 實驗的對比結果

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

[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] 萬常選,魯遠.基于權重查詢詞的XML結構查詢擴展[J].軟件學報,2008,10(19):7-13.

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

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

[5] 王宏志.XML數據查詢處理技術的研究[D]:哈爾濱：哈爾濱工業大學,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方法的設計與研究[J].計算機工程,2007,21(33)：63-65.

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