XML文檔語義檢索方法研究

莫正波，宋 玲，呂 強，鄧 薇

1.青島理工大學 理學院，山東 青島 266033

2.山東建筑大學 計算機科學與技術學院，濟南 250101

3.國網技術學院 電網檢修培訓部，濟南 250002

4.山東科技大學 基礎課部，山東 泰安 271021

XML是一種元標記語言，它提供描述結構化資料的格式，可用于創建標記語言。它以其良好的數據存儲格式、可擴展性、高度結構化、便于網絡傳輸等優勢在許多領域得到廣泛應用，XML便于網頁信息組織，不僅能滿足不斷增長的網絡應用需求，而且還能夠確保在與網絡進行交互時，具有良好的可靠性與互操作性。XML具有可擴展性、靈活性以及自描述性。隨著XML的數據存儲、網絡信息交互、數據發現和挖掘、XML版本控制、半結構數據的整合、以及XML文檔檢索的蓬勃發展，使得XML的檢索目前來說始終是一個研究重點。

XML文檔可以被模型化為有序標簽樹，一個XML文檔的例子及其樹模型如圖1所示。對應一個XML文檔的所有路徑組成的集合叫做XML文檔的路徑集，如圖1（b）的路徑集為{articles/article/title/Data Mining，articles/article/author/Febio，articles/article/keywords/Data Mining Algorithms}。

圖1 一個XML文檔及其樹表示

1 相關研究

XML信息檢索技術可劃分為以下幾種研究方向：基于XML數據查詢語言XPATH[1]、XQuery[2]的檢索；基于關鍵詞的面向XML文檔內容的檢索[3]；以及基于XML文檔結構以及內容的檢索[4-5]。其中最后一種檢索由于同時考慮了XML的文檔結構以及語義特點，是目前研究的一個主要方向，在該類方法的研究中一般采用編碼或者建立索引的方式考慮內容方面，通過路徑考慮結構方面的檢索[6-7]。基于用戶查詢（將用戶查詢可以描述為一個XML文檔）和XML文檔之間相似度的方法是將用戶的查詢與XML文檔集中的每個XML文檔都計算相似度，并根據相似度值返回檢索結果。對于XML文檔相似度的計算，許多學者進行了廣泛的研究，文獻[8]將這些方法分為三類：基于編輯距離的方法、基于信息檢索的方法以及其他方法。基于編輯距離的方法基本思想是將兩棵樹之間的距離定義為利用編輯操作實現一棵樹到另一棵樹轉換所需的代價。顯然，距離和相似度之間成反比關系，樹之間的距離越小，則相似度越大。樹之間的編輯操作主要有三種：插入、刪除和替換[9-10]，但它們的復雜度比較高。在文獻[11-12]中，研究者不但把插入、刪除操作限制在葉節點上，還增加了一種重定位子樹的移動操作。然而，這種算法并不能保證最優的結果。Chawathe的方法把插入、刪除操作限制在文檔樹的葉節點上，并且允許在樹的任何地方重定義節點標簽，Chawathe算法的總體復雜度為O(N2)，其中N是參與比較的標簽樹中擁有最多節點的樹的節點數。該算法的性能和效率較高[13]。Nierman和Jagadish在計算XML結構相似度尤其是子樹相關的相似度中，具有更好的精度并且能保持在二次方的復雜度[14]。以上基于編輯距離的相似度方法適用于結構嚴謹的數據型（data-centric）XML，而基于信息檢索的相似度方法適用于結構松散的文檔型（document-centric）XML，主要應用于排序的XML查詢（ranked XML querying）。Fuhr和Gro?johann對 XML文檔元素或不相交的子樹進行索引[15]。為了滿足用戶對于XML文檔中的部分檢索要求，Grabs和Schek提出塊索引方法[16]。為了能體現XML文檔的結構，Schlieder和Meuss提出了一種拓展的向量空間模型，把詞條的標準概念拓展成了結構詞條，一個結構詞條表示一棵標簽樹[17]；Pokorny和Rejlek把XML用標簽樹來表示，并且應用了路徑這一概念，把XML抽象成了一個矩陣而不是簡單的向量，查詢和文檔之間的相似度也就轉化成了相應矩陣之間的相似度計算[18]。其他的XML相似度方法包括標簽相似度、邊匹配[19]、路徑相似度[20-21]等。但目前這種相似度的檢索方法用得比較少，主要原因在于用戶的查詢請求很少用XML文檔直接描述，其次如果將用戶的查詢與XML文檔集中的每個XML文檔在充分考慮文檔結構和語義內容的情況下計算相似度，并根據相似度值返回檢索結果，這種方法的計算復雜性比較高。

但是在一些情況下，當用戶的查詢請求通過XML文檔很清晰地描述出來，這時基于相似度的檢索在排序方面就具有了一種明顯的優勢，基于該應用背景，本文提出一種有效的XML文檔檢索的方法，主要貢獻是提出了粗糙過濾和精確匹配的思想，具體如下：（1）過濾階段，利用簽名技術，將大量無關的XML文檔進行過濾，得到可能與用戶查詢相關的文檔，該方法大大縮減XML數據查詢集，降低精確匹配過程中的計算復雜度。（2）精確匹配階段，綜合考慮了元素的相似度和路徑的結構信息，計算XML文檔之間的相似度。

2 語義檢索方法框架

給定XML文檔集D和用戶查詢q，XML檢索即是從D中查找出符合q的XML文檔。為了提高計算效率，同時考慮XML文檔的結構和語義，本文在計算用戶查詢與XML文檔相似度的過程中包括三個階段：（1）用戶的語義查詢擴展階段，利用本體對用戶的查詢路徑進行同義詞擴展。（2）過濾階段，利用查詢詞的簽名逐一與各個XML文檔簽名進行匹配，查找可能相似的XML文檔，此處所得到的一系列XML文檔并不一定就是用戶所希望得到的，但是數據集中所有與用戶查詢相關的文檔都包含在了這些小范圍的XML文檔中。此步操作是進行正式搜索的預處理工作，目的是大大縮減XML數據查詢集，降低算法的復雜度提高算法性能和效率。（3）精確計算階段，綜合考慮了元素的相似度和路徑的結構信息，精確計算查詢與文檔之間的相似度。

算法的主要思路如圖2所示，該算法分為三步：首先，基于WordNet對用戶查詢q進行同義詞擴展得到q'；然后，將q'和D中的每一篇XML文檔都進行數字簽名，并通過簽名之間的匹配對D進行有效過濾，除去大量不符合用戶查詢的文檔，得到一個文檔子集 D′,D′?D；最后，對q'與D'中的文檔進行精確匹配得到檢索結果。

圖2 算法流程圖

3 XML文檔過濾

3.1 布隆過濾器

布隆過濾器是一個很長的二進制向量和一系列隨機映射函數，用于檢索一個元素是否在一個集合中。其基本思想就是用一個或多個hash函數對數據集中的每個成員做映射，映射結果不是存在完整的hash表中，而是一個位向量（bit vector）中。位向量所有位初始都為0，根據hash結果將位向量中相應位置1。對數據集中的所有成員的hash計算完成后，就得到了該數據集的位向量。當需要判斷一個元素是否屬于該數據集時，也用相同的hash函數對其映射得到它的位向量，然后將其位向量上所有為1的位與數據集位向量上相應位比較，如果發現數據集的位向量上某個位為0的話，可以判斷這個元素不屬于該數據集，這樣的一個結果是肯定的。而如果所有相應位都為1的話，那么該元素可能屬于這個數據集。

如果由布隆過濾判斷某個元素屬于一個集合，但事實上卻不是，那就是誤判。假如集合成員數為n，用k個函數映射后，m位向量上某個位為0的概率為：(1-1/m)k×n,某個位為1的概率就是(1-1/m)k×n,而如果要判斷一個數是否屬于該集合，其所有映射位和集合向量的所有匹配的概率就是(1-(1-1/m)k×n)k。從上式看出，當m越大，誤算的概率就越低。但是m越大，所占空間就越大。

3.2 用戶查詢詞的語義擴展

對于用戶所給的查詢詞，即關鍵字，首先要經過查詢擴展處理。通常不能因為兩篇文檔缺乏公共關鍵字就斷定它們一定是不相關的。同樣在用戶利用關鍵詞進行查詢時，某一文檔不包含用戶枚舉的關鍵字時也未必說明此文檔不符合用戶的查詢要求。如，用戶想了解關于“car”的信息，但是某一文檔中所涉及內容為“motor”，則此文檔也極有可能符合用戶的需求，也就是說要得到良好的查詢結果應該把語義考慮進來。在本文中，先把查詢詞進行同義擴展，即利用WordNet[21]這一工具查找出用戶給定的關鍵字的所有同義詞，并利用所得到的同義詞和原來關鍵字一并作為新的關鍵字進行查詢。WordNet是由Princeton大學設計的一種基于認知語言學的英語詞典。語言中的詞匯是按照同義詞類組織在一起的，每個詞類都對應一種“潛在的概念”，詞類與詞類之間通過不同的方式聯系，將單詞按照其意義組成一個“單詞的網絡”，它是研究語義相關性的有力工具。如用戶輸入查詢“author/Fabio”，利用WordNet將“author”語義擴展為“writer，generator，source”。

3.3 用戶查詢及XML文檔的布隆過濾器簽名

用戶在進行查詢時，通過多條查詢路徑，構成路徑查詢集。如用戶的查詢是author為Fabio并且title為data mining，對用戶查詢集中的每個詞進行同義詞查詢擴展并逐一進行簽名獲得其對應的向量。

解析數據集中的每個XML，把它的所有標簽節點、屬性節點、值節點全部解析出來，得到對應的文本文檔，將其通過與以上類似的方法利用布隆過濾器進行數字簽名。

3.4 用戶查詢及XML文檔簽名匹配

利用查詢詞的簽名向量逐一與各個XML文檔向量進行匹配查找可能的目的XML文檔，此處所得到的一系列XML文檔并不一定就是用戶所希望得到的，但是數據集中所有與用戶查詢相關的文檔都包含在了這些小范圍的XML文檔中。此步操作目的是大大縮減XML數據查詢集，接下來再對這些小范圍XML數據集進行搜索查詢即可。

4 用戶查詢與XML文檔相似度的計算

用戶查詢與XML文檔之間的相似度與它們之間的共性和差別相關，它們所擁有的共性越多，則相似度越大，差異越多，則相似度越小。由于XML文檔可擴展性和高度結構化的特點，XML文檔之間相似度比較至少要涉及到兩個層次：結構的比較以及標簽（label）名和內容的比較。因為路徑能夠部分表示XML的拓撲結構，所以可以基于路徑來表示文檔的結構信息，并考慮路徑上標簽的語義信息來計算XML文檔間的相似度。概括來說，首先將XML文檔解析成標簽樹，將標簽樹分解為從根到葉子節點的路徑集，因此通過比較路徑集之間的相似度得到文檔之間的相似度。對于路徑之間相似度比較需要考慮路徑元素之間的語言相似性和結構位置的相對有序性。在以往的工作中，提出了一種計算基于XML結構特征和語義內容特征計算XML文檔相似度的方法[22-23]，方法描述如下：

對于路徑Pa={ea1/ea2/…/eam}和路徑Pb={eb1/eb2/…/ebn},s[i,j]被定義為子序列Pai(Pai={ea1/ea2/…/eai}(i≤m))和Pbj(Pbj={eb1/eb2/…/ebj},j≤n)的路徑相似度，則Pa和Pb的相似度值為s[m,n]，公式（1）遞歸地求解路徑之間相似度。

其中ESim(xi,yj)為節點xi,yj之間的編輯相似度和語義相似度的最大值。由于在XML文檔中，層次高的節點（離根節點更近的節點）往往比層次低的節點（離根節點較遠的節點）更能反映文檔的結構信息，在計算相似度時，必須把節點所處的層次考慮在內。為了反映這一特點，本文對路徑中各個節點賦不同的權值，越靠近根節點，被賦予的權值越大，也就意味著對路徑相似度的貢獻越大。有權路徑就是對路徑中的每個節點都賦給一個非負數的權值。路徑p的最大深度為h，對于節點x位于第m層（從葉子節點到x的路徑長度），那么x的權重就被賦值為γh-m(0＜γ≤1),其中γ為一參數。

為了便于比較，對于路徑Pa={ea1/ea2/…/eam}和路徑Pb={eb1/eb2/…/ebn}，公式（2）將公式（1）歸一化到區間[0，1]。

令d為一個XML文檔，Pd為其對應的路徑集，Q為路徑查詢集。d和Q的相似度定義如公式（3）所示：

5 實驗

為了測試本文提出的方法，本文XML實驗數據集來自于（Niagara，http：//www.cs.wisc.edu/niagara/data/）和 IBM XML generator（http：//www.alphaworks.ibm.com/tech/xmlgenerator），共有1 039個文檔，為了測試XML文檔的語義和結構，從1 039個文檔中拷貝了600個文檔，將這600個文檔通過標簽名或內容語義替換或結構刪除的方式進行了改變，共得到1 639個文檔。

用戶查詢通過5個在校大學生獲得，首先給用戶一些包含在XML文檔中的內容信息的一些例子，如圖3所示。這些信息沒有結構，要求用戶從這些例子中生成用戶查詢，自由選擇結構和標簽名，通過XML文檔來描述得到的30個用戶查詢。

圖3 用來生成查詢的例子

為了測試本文提出的方法，實現了文獻[24]中提到的相似度方法，在文本將之記為XMLSim，并用來進行測試比較。本文對用戶查詢和1 639個XML文檔首先離線簽名，通過粗糙過濾后，然后利用QXMLSim計算用戶查詢與相關XML文檔的相似度，并排序輸出結果。為了對結果進行評價，本文采用前k個檢索結果的查準率以及算法運行時間作為評價標準，如圖4和圖5所示。

圖4 經過粗糙過濾以及QXMLSim相似度計算與XMLSim的檢索運行時間比較

圖5 經過粗糙過濾以及QXMLSim相似度計算與XMLSim的平均查準率比較

通過圖4可以觀察到隨著數據量的逐漸增大，經過粗糙過濾以及QXMLSim相似度計算兩個步驟的運行時間大大降低，通過分析可以得出通過粗糙過濾可以有效地提高運行時間的結論。通過圖5，可以發現本文提出的方法在top k查準率略有提高，主要原因是利用了WordNet進行查詢擴展。

6 結束語

本文提出一個通過空間換時間的一種有效的檢索方法，將檢索過程分為兩步，首先是過濾階段，利用簽名技術，將大量無關的XML文檔進行過濾，得到可能與用戶查詢相關的文檔，該方法大大縮減XML數據查詢集，降低精確匹配過程中的計算復雜度。其次在精確匹配階段，綜合考慮了元素的相似度和路徑的結構信息，計算XML文檔之間的相似度。通過實驗表明本文提出的方法在運行時間上有了較大的提高，查準率也略有提高。

[1]XPath：XML path language（XPath）2.0.[EB/OL].[2011-12-18].http：//www.w3.org/TR/xpath20/.

[2]XQuery 1.0：an XML query language（Second Edition）[EB/OL].[2011-12-18].http：//www.w3.org/TR/xquery/.

[3]孔令波，世渭，楊冬青，等.XML信息檢索中最小子樹根節點問題的分層算法[J].軟件學報，2007，18（4）：919-932.

[4]萬常選，魯遠.基于權重查詢詞的XML結構查詢擴展[J].軟件學報，2008，19（10）：2611-2619.

[5]劉喜平，萬常選，劉德喜，等.有效的XML模糊內容與結構檢索和計分[J].計算機研究與發展，2010，47（6）：1070-1078.

[6]胡錦南.面向XML文檔集的檢索技術研究與系統實現[D].合肥：中國科學技術大學，2009.

[7]向永清，鄧志鴻，于航，等.面向XML文檔的二級索引技術及其在XML關鍵詞檢索中的應用研究[J].計算機研究與發展，2009，46（z2）：748-755.

[8]Tekli J，Chbeir R，Yétongnon K.An overview on XML similarity：background，currenttrends and future directions[J].Computer Science Review，2009，3（3）：151-173.

[9]Shasha D，Zhang K.Approximate tree pattern matching[M]//Pattern matching in strings，trees and arrays.[S.l.]：Oxford University Press，1995.

[10]Zhang K，Shasha D.Simple fast algorithms for the editing distance between trees and related problems[J].SIAM Journal of Computing，1989，18（6）：1245-1262.

[11]Chawathe S，Rajaraman A，Garcia-Molina H，et al.Change detection in hierarchically structured information[C]//Proceedings ACM SIGMOD，Canada，1996：26-37.

[12]Cobéna G，Abiteboul S，Marian A.Detecting changes in XML documents[C]//Proceedings of the IEEE International Conference on Data Engineering，2002：41-52.

[13]Chawathe S.Comparing hierarchical data in external memory[C]//Proceedings of the VLDB Conference，1999：90-101.

[14]Nierman A，Jagadish H V.Evaluating structural similarity in XML documents[C]//Proceedings of the 5th ACM SIGMOD International Workshop on the Web and Databases（WebDB），2002：61-66.

[15]Fuhr N，Gro?johann K.XIRQL：a query language for information retrieval[C]//Proceedings of ACM-SIGIR，New Orleans，2001：172-180.

[16]Grabs T，Schek H J.Generating vector spaces on-thefly for flexible XML retrieval[C]//Proceedings of ACM SIGIR’02 Workshop on XML and Information Retrieval，2002：4-13.

[17]Schlieder T，Meuss H.Querying and ranking XML documents[J].Journal of the American Society for Information Science，2002，53（6）：489-503.

[18]Pokorny J，Rejlek V.A matrix model for XML data[C]//the 6th International Baltic Conference DB&IS，2005：53-64.

[19]Kriegel H P，Sch?nauer S.Similarity search in structured data[C]//Proceedingsofthe 5th InternationalConference on Data Warehousing and Knowledge Discovery（DaWaK 03），Czech Republic，2003：309-319.

[20]Rafiei D，Moise D，Sun D.Finding syntactic similarities between XML documents[C]//Proceedingsofthe 17th International Conference on Database and Expert Systems Applications（DEXA），2006：512-516.

[21]WordNet[EB/OL].[2011-12-18].http：//wordnet.princeton.edu.

[22]Song Ling，Li Shengen，Lv Qiang，et al.An approach for measuring similarity between XML documents[C]//6th InternationalConferenceon Fuzzy Systemsand Knowledge Discovery，2009，7：410-414.

[23]Song Ling，Ma Jun，Lei Jingsheng，et al.Semantic structural similarity measure for clustering XML documents[C]//Lecture Notes in Computer Science（LNCS），2009：232-241.

[24]Nayak R，Iryadi W.XML schema clustering with semantic and hierarchical similarity measures[J].Knowledge-Based Systems，2007，20（4）：336-349.