XML文檔語義檢索方法研究

莫正波，宋 玲，呂 強(qiáng)，鄧 薇

1.青島理工大學(xué) 理學(xué)院，山東 青島 266033

2.山東建筑大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，濟(jì)南 250101

3.國網(wǎng)技術(shù)學(xué)院 電網(wǎng)檢修培訓(xùn)部，濟(jì)南 250002

4.山東科技大學(xué) 基礎(chǔ)課部，山東 泰安 271021

XML是一種元標(biāo)記語言，它提供描述結(jié)構(gòu)化資料的格式，可用于創(chuàng)建標(biāo)記語言。它以其良好的數(shù)據(jù)存儲(chǔ)格式、可擴(kuò)展性、高度結(jié)構(gòu)化、便于網(wǎng)絡(luò)傳輸?shù)葍?yōu)勢在許多領(lǐng)域得到廣泛應(yīng)用，XML便于網(wǎng)頁信息組織，不僅能滿足不斷增長的網(wǎng)絡(luò)應(yīng)用需求，而且還能夠確保在與網(wǎng)絡(luò)進(jìn)行交互時(shí)，具有良好的可靠性與互操作性。XML具有可擴(kuò)展性、靈活性以及自描述性。隨著XML的數(shù)據(jù)存儲(chǔ)、網(wǎng)絡(luò)信息交互、數(shù)據(jù)發(fā)現(xiàn)和挖掘、XML版本控制、半結(jié)構(gòu)數(shù)據(jù)的整合、以及XML文檔檢索的蓬勃發(fā)展，使得XML的檢索目前來說始終是一個(gè)研究重點(diǎn)。

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

圖1 一個(gè)XML文檔及其樹表示

1 相關(guān)研究

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

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

2 語義檢索方法框架

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

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

圖2 算法流程圖

3 XML文檔過濾

3.1 布隆過濾器

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

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

3.2 用戶查詢詞的語義擴(kuò)展

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

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

用戶在進(jìn)行查詢時(shí)，通過多條查詢路徑，構(gòu)成路徑查詢集。如用戶的查詢是author為Fabio并且title為data mining，對用戶查詢集中的每個(gè)詞進(jìn)行同義詞查詢擴(kuò)展并逐一進(jìn)行簽名獲得其對應(yīng)的向量。

解析數(shù)據(jù)集中的每個(gè)XML，把它的所有標(biāo)簽節(jié)點(diǎn)、屬性節(jié)點(diǎn)、值節(jié)點(diǎn)全部解析出來，得到對應(yīng)的文本文檔，將其通過與以上類似的方法利用布隆過濾器進(jìn)行數(shù)字簽名。

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

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

4 用戶查詢與XML文檔相似度的計(jì)算

用戶查詢與XML文檔之間的相似度與它們之間的共性和差別相關(guān)，它們所擁有的共性越多，則相似度越大，差異越多，則相似度越小。由于XML文檔可擴(kuò)展性和高度結(jié)構(gòu)化的特點(diǎn)，XML文檔之間相似度比較至少要涉及到兩個(gè)層次：結(jié)構(gòu)的比較以及標(biāo)簽（label）名和內(nèi)容的比較。因?yàn)槁窂侥軌虿糠直硎綳ML的拓?fù)浣Y(jié)構(gòu)，所以可以基于路徑來表示文檔的結(jié)構(gòu)信息，并考慮路徑上標(biāo)簽的語義信息來計(jì)算XML文檔間的相似度。概括來說，首先將XML文檔解析成標(biāo)簽樹，將標(biāo)簽樹分解為從根到葉子節(jié)點(diǎn)的路徑集，因此通過比較路徑集之間的相似度得到文檔之間的相似度。對于路徑之間相似度比較需要考慮路徑元素之間的語言相似性和結(jié)構(gòu)位置的相對有序性。在以往的工作中，提出了一種計(jì)算基于XML結(jié)構(gòu)特征和語義內(nèi)容特征計(jì)算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)為節(jié)點(diǎn)xi,yj之間的編輯相似度和語義相似度的最大值。由于在XML文檔中，層次高的節(jié)點(diǎn)（離根節(jié)點(diǎn)更近的節(jié)點(diǎn)）往往比層次低的節(jié)點(diǎn)（離根節(jié)點(diǎn)較遠(yuǎn)的節(jié)點(diǎn)）更能反映文檔的結(jié)構(gòu)信息，在計(jì)算相似度時(shí)，必須把節(jié)點(diǎn)所處的層次考慮在內(nèi)。為了反映這一特點(diǎn)，本文對路徑中各個(gè)節(jié)點(diǎn)賦不同的權(quán)值，越靠近根節(jié)點(diǎn)，被賦予的權(quán)值越大，也就意味著對路徑相似度的貢獻(xiàn)越大。有權(quán)路徑就是對路徑中的每個(gè)節(jié)點(diǎn)都賦給一個(gè)非負(fù)數(shù)的權(quán)值。路徑p的最大深度為h，對于節(jié)點(diǎn)x位于第m層（從葉子節(jié)點(diǎn)到x的路徑長度），那么x的權(quán)重就被賦值為γh-m(0＜γ≤1),其中γ為一參數(shù)。

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

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

5 實(shí)驗(yàn)

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

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

圖3 用來生成查詢的例子

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

圖4 經(jīng)過粗糙過濾以及QXMLSim相似度計(jì)算與XMLSim的檢索運(yùn)行時(shí)間比較

圖5 經(jīng)過粗糙過濾以及QXMLSim相似度計(jì)算與XMLSim的平均查準(zhǔn)率比較

通過圖4可以觀察到隨著數(shù)據(jù)量的逐漸增大，經(jīng)過粗糙過濾以及QXMLSim相似度計(jì)算兩個(gè)步驟的運(yùn)行時(shí)間大大降低，通過分析可以得出通過粗糙過濾可以有效地提高運(yùn)行時(shí)間的結(jié)論。通過圖5，可以發(fā)現(xiàn)本文提出的方法在top k查準(zhǔn)率略有提高，主要原因是利用了WordNet進(jìn)行查詢擴(kuò)展。

6 結(jié)束語

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

[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信息檢索中最小子樹根節(jié)點(diǎn)問題的分層算法[J].軟件學(xué)報(bào)，2007，18（4）：919-932.

[4]萬常選，魯遠(yuǎn).基于權(quán)重查詢詞的XML結(jié)構(gòu)查詢擴(kuò)展[J].軟件學(xué)報(bào)，2008，19（10）：2611-2619.

[5]劉喜平，萬常選，劉德喜，等.有效的XML模糊內(nèi)容與結(jié)構(gòu)檢索和計(jì)分[J].計(jì)算機(jī)研究與發(fā)展，2010，47（6）：1070-1078.

[6]胡錦南.面向XML文檔集的檢索技術(shù)研究與系統(tǒng)實(shí)現(xiàn)[D].合肥：中國科學(xué)技術(shù)大學(xué)，2009.

[7]向永清，鄧志鴻，于航，等.面向XML文檔的二級索引技術(shù)及其在XML關(guān)鍵詞檢索中的應(yīng)用研究[J].計(jì)算機(jī)研究與發(fā)展，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.