以目標節點為導向的XML關鍵詞查詢和排序

李瑞霞 劉仁金 周先存

以目標節點為導向的XML關鍵詞查詢和排序

李瑞霞 劉仁金 周先存

(皖西學院信息工程學院 安徽 六安 237012)

為了準確推斷用戶的查詢意圖，提出一個XML關鍵詞查詢和排序的方法。該方法首先根據XML文檔結構和語義，分別建立標簽信息表和文本信息表表示文檔的結構和數據，然后通過標簽和文本兩個指標確定查詢關鍵詞和目標節點的相似性得分，給出排序方法。同時給出該方法實現的算法，并通過實驗驗證了該方法的有效性。實驗結果表明，該方法可以更準確地推斷用戶查詢的目標節點。

XML

查詢 排序 目標節點

0 引 言

XML因其結構靈活并易于擴展，已成為當前數據表示的主流形式。對于XML的關鍵詞查詢也是許多學者的研究熱點，借助查詢語言XPath、XQery可以進行準確的查詢，但要求用戶對XML文檔結構有所了解，并熟悉其語法，該方法未能廣泛應用。針對XML的關鍵詞查詢因其簡單易用，已成為主要的信息檢索方法。XML關鍵詞查詢方面有大量的研究工作。文獻[1]把XML看作一個樹結構，通過計算LCA，專門提出“meer operator”的概念進行查詢，其結果類型依賴XML文檔的實例。文獻[2]要求用戶了解XML文檔的部分知識實現查詢，設計了MLCS算法。2005年文獻[3]提出了SLCA的概念并且設計了三種有效的算法實現了一個XKSearch搜索系統。2007年文獻[4]基于SLCA，同時結合了“AND”、“OR”操作進行關鍵字查詢。文獻[5]提出了XSeek,通過驗證查詢關鍵詞和XML結構的匹配模式獲得返回節點。文獻[6,7]利用多個指標識別用戶的搜索意圖并進行了結果排序，但是該方法沒有考慮包含文本節點的葉子節點的作用，因此并不能準確地識別目標節點。對于結果排序方面，2003年文獻[8]提出了XRank方法，計算LCAs處理XML關鍵字相似性查詢。該方法返回的結果是XML文檔的部分片段。文獻[9]返回的是具有語義關系的片段，但是由于該方法要求用戶需了解文檔的結構，因此該方法有其局限性。文獻[10]利用TF-IDF結合文檔結構進行異構數據查詢及排序。文獻[11]利用統計學的思想進行檢索結果排序。以上方法都是基于LCA及其變體，并沒有從根本上解決用戶的搜索意圖及結果排序的問題。

在XML關鍵字查詢中準確地識別用戶的搜索意圖并將最相關的結果進行排序已經成為一個具有挑戰性的問題。由于在XML關鍵詞查詢結果中包含大量目標節點，導致提供給用戶的結果并不能滿足其需求，而且可能漏掉相關的結果。本文的目標是要推斷符合用戶查詢意圖的目標節點并且返回最相關的結果。該方法中，首先分別構建一個標簽信息表用來存儲文檔的元素和屬性節點，一個文本信息表用來存儲文檔的元素和屬性的取值；然后通過檢索兩個表初步推斷目標節點的類型，最后計算目標節點和關鍵詞的相似性得分,并給出結果排序方法。

1 相關工作

在文中XML文檔可以用一個帶有根節點的標簽樹表示t=(r,NE,NV)。其中，r表示根節點；NE為元素節點和屬性節點的集合；NV代表元素節點和屬性節點的取值的集合。根據XML文檔所包含的結構和語義信息[12,13]，本文作如下定義:

定義1 (標簽節點)XML文檔中的元素節點和屬性節點的總稱，存儲標簽節點相關信息的表稱為標簽信息表。

定義2 (文本節點)XML文檔中的表示元素節點和屬性節點的取值，存儲文本節點相關信息的表稱為文本信息表。

定義3 (前綴路徑)XML文檔中用前綴路徑表示從根節點到當前節點的所經過的路徑，用path表示，存儲在標簽信息表中。

如圖1所示，XML文檔包含若干節點，其中″dblp″可以看作是根節點，″phdthesis″、″proceedings″等表示文檔結構的節點就是標簽節點，″title″、″publishing″等為葉子節點，而″280″、″1998″等則表示葉子節點或者屬性的取值，也稱文本節點。

圖1 一個XML文檔樹的例子

2 目標節點推斷打分及排序方法

關鍵詞查詢的目標是從XML文檔集中找到與給定關鍵詞最相關的文檔或片段。本文提出的方法利用匹配XML文檔的標簽和文本兩個指標來識別目標節點，進而綜合兩個指標的相似性得分，最后給出了排序方法。主要分為如下幾個步驟：

(1) 為了在查詢過程中能夠識別用戶查詢目標是標簽還是文本，對XML文檔分別建立標簽信息表和文本信息表；

(2) 對于一個給定的查詢，利用兩個指標進行匹配確定目標節點類型；

(3) 利用對數函數和概率函數計算查詢關鍵詞和標簽的相似性找到相關的目標節點；

(4) 計算包含文本節點的葉子節點和查詢關鍵字之間的相似性，進一步識別目標節點；

(5) 通過綜合兩個指標的相似性得分，對查詢結果進行排序。

下面分別介紹各個步驟的實現方法。

2.1 兩個指標

在文獻[6,7]中提到了頻率表，但是沒有確定查詢關鍵字是結構節點還是文本節點，所以導致查詢變得更復雜。為了克服該問題，本文提出的方法確定了兩個指標，即標簽和文本。對于某特定的XML文檔，標簽信息表存儲了相應的標簽信息(標簽名tsn，標簽在目標節點及其子樹中出現的次數ft，目標節點的前綴路徑path)。同樣，文本信息表里存儲了相應的文本節點信息(文本值d，包含該文本節點的葉子節點的標簽名tln，該文本節點在葉子節點中出現的次數fd)。由此看出，文本信息表里也包含了葉子節點的信息，所以兩個表共享XML文檔的信息。為了簡化查詢過程，本文分別對標簽和文本來處理。

2.2 確定目標節點的類型

對于一個給定的XML查詢，首先在標簽信息表里查找匹配的關鍵詞，如果查找成功，則該查詢的目標是標簽記為Kt，同時可以從標簽信息表獲得標簽名tsn，標簽在目標節點及其子樹中出現的次數ft，目標節點的前綴路徑path等信息；否則就從文本信息表里查找，如果匹配成功，則該查詢的目標是文本信息記為Kd，包含該文本的葉子節點tln可以從該表獲得，而該葉子節點的其他信息ft，和path則從標簽信息表獲得。

2.3 相似性得分

XML關鍵詞查詢中，關鍵詞可能在標簽或者文本中出現一次或者一次以上，若找到一個以上的匹配結果，則需要找到最優的目標節點。因此本文借助對數函數和統計學的思想，計算檢索關鍵詞和目標節點的相似性得分如下：

(1)

式中，k表示某查詢q中的某個關鍵詞，Tt表示標簽信息里的標簽，D表示文本信息里的文本值，f(tk)表示在每個前綴路徑上標簽和關鍵詞匹配的次數，f(td)表示關鍵詞匹配的文本值在葉子節點中出現的次數，f(tk,td)表示在查詢中標簽和文本值結合的次數，rf是[0,1]之間的衰減因子,d(T)表示XML文檔中目標節點的所在的層次，rfd(T)的作用是為了減少多層次嵌套帶來的影響。

從式(1)分析可以看出，該相似性得分并沒有考慮文本節點及其所在的葉子節點的作用，因此通過下面的處理進一步查找最優的目標節點。

在文本信息表中查找匹配的文本，進而可以找到包含該文本值的葉子節點，因此我們借助標簽信息表選擇節點所在的前綴路徑上出現次數最多的節點作為目標節點。通過如下的方法計算前綴路徑上找到的目標節點和查詢關鍵詞之間的相似性。

(2)

于是，最后的目標節點和查詢關鍵詞相似性得分可以通過下式表示：

Similarity Score=Mscore+S(X)

(3)

由此可以看出，相似性函數綜合了標簽和文本兩個指標進行匹配，從而可以獲得最優的目標節點。

2.4 排 序

通常，我們認為和查詢關鍵詞相似性得分較高的節點應該是最相關的結果，應該優先呈現給用戶。因此，本文通過如下的方法確定最終目標節點。

G=Max{Mscore+S(x)}

(4)

下式表示目標節點的排序方法：

(5)

3 主要實現算法和實驗結果分析

3.1 主要實現算法

本文首先解析XML文檔，抽取文檔中元素或者屬性節點的標簽名tsn、該節點的前綴路徑path、文本節點的前綴路徑path、節點值d、標簽在目標節點及其子樹中出現的次數ft、包含該文本節點的葉子節點的標簽名tln以及該文本節點在葉子節點中出現的次數fd等信息，進而獲得標簽和文本信息，構建標簽信息表的的方法命名為tag_info table。構建文本信息表的方法命名為data_info table,另外一個存儲前綴路徑信息的方法命名為path_info table。其中的空間復雜度為O(Nsn)，而Nsn則和XML文檔中標簽節點和文本節點的數量高度相關。主算法見算法1，分別包括三個程序:首先，通過get_IndexInfo獲得關鍵詞匹配標簽和包含了文本的葉子節點的信息；對于每個前綴路徑，程序get_MutualScore計算匹配的標簽和葉子節點的綜合相似性得分；最后，程序get_SimilarityScore計算出葉子節點和查詢關鍵詞的相似性，從而通過排序的方法得到目標節點。

算法1 關鍵詞查詢中的目標節點計算方法

輸入：包含了n個關鍵詞的查詢Q

1 get_IndexInfo(query keywords)

2 get_MutualScore(keyword match)

3 get_SimilarityScore(data keywords)

算法2檢索標簽信息表和文本信息表確定檢索目標是標簽還是文本，同時獲得檢索到的標簽名、出現次數等信息。程序Get_IndexInfo檢查標簽信息表中是否包含查詢關鍵詞，同時，通過調用dataExist檢查文本信息表中是否包含查詢關鍵詞(1-5行)。然后，對于每個標簽關鍵詞kt調用了getFromTaginfo得到關鍵詞匹配的標簽節點相關信息，存儲于taglist和slist(6-10行)。同樣，對于文本關鍵詞調用getFromDatainfo得到包含該節點的葉子節點的相關信息，并存儲于datalist和slist。

算法2 Get_IndexInfo(query)

input: Query Q containing n keywords

1 for each keyword ki ∈Query do

2 if taglist(ki)= true then

3 { kiis a tag keyword}

4 else if dataExist(ki) = true then

5 { kiis a data keyword}

6 for each tag keyword∈Query do

7 rs = getFromTaginfo (tki)

8 while ( rs.next)

9 result = tsn+ft+path

10 taglist(result)； slist(result)

11 for each data keyword∈Query do

12 rs=getFromDatainfo(ai)

13 while (rs.next)

14 result = tln+fti十path

15 datalist (result)； slist (result)

16 return slist0:

對于一個查詢Q，若包含了n個關鍵詞，則算法2的時間復雜度最壞的情況可以表示為O(n+nt×kmt+nd×kmd)，n表示查詢關鍵詞的數量，nt和kmt分別代表標簽節點和可以匹配的標簽關鍵詞的數量；同樣，nd和kmd表示文本節點和可以匹配的葉子節點的數量。

算法3綜合標簽和文本兩個方面得到目標節點和關鍵詞之間的相似性得分。

算法3 Get_MutualScore(query,keyword match)

1 for each keyword matching tag ∈ Query do

2 f(tk) =getTagFrequency (query)

3 for each keyword matching data value ∈ Query do

4 f(td)=getDataFrequency(query)

5 Based on combination of tag and data in query, assign a value to cvalue

6 for each result ∈ slist() do

7 Splitpath from slist(); tagpath(path)

8 Based on cvalue. Construct queryStringqueries(queryString)

9 for (each queryString ∈ queries()) do

10 d = getCombinedFrequency (queryString)

11 f(tk,td) + = d

12 msum = lg(f(tk,td)/lg(f(tk)*f(td))

13 mscore = Msum*rdepth(T)

14 mlist(path, mscore)

15 retum mlist0:

算法4檢索文本信息表，進一步計算了文本節點所在的葉子節點和查詢之間的相似性，結合算法3進行了最終相似性得分的計算，并給出了排序的方法。

算法4 Get_similarityScore(data keyword)

1 for each datakeywords E Query do

2 rs = getFromData _info(dki)

3 while ( rs.next)

4 result = d +fd+tln+ id

5 dsimilar(result)

6 for each result ∈dsimilar() do

7 Get tag with biggest frequency; ltag= tln+fd+id

8 stag(ltag)

9 for each ltag ∈ stag do

10 rs = caIIReferences(id)

11 while (rs.next)

12 Get frequency fdGet path of ltag from path_info

13 for each data ∈ mlist do

14 if path in mList =poth from path_info then

15 Get mscore from mList

16 f=fd

17 S(x) =f + Lg(f)

18 SimilarityScore = mscore +S(x) ;

19 Grading = Max(SimilarityScore)

20 retum SimilarityScore

通過分析可以看出，在本方法中標簽信息表最壞的空間復雜度為O(Nsn)，文本信息表最壞的空間復雜度為O(D×Nln)。在Xreal中頻率表最快空間復雜度為O(K×N)，式中K表示不同的關鍵詞的數量，N表示節點類型的數量，因此本文的空間復雜度比Xreal降低了。

3.2 實驗分析

我們利用Java語言實現了基于前述算法的一個推斷目標節點的XML關鍵詞檢索原形系統。對比算法選擇了Xreal，測試數據集使用實際的DBLP數據集(127 MB)，實驗平臺是Intel 2.8 GHz Pentium D 處理器，1 GB RAM，Windows 7操作系統。測試選取了70篇文檔。表1表示其中10組數據的測試結果，對比結果表明本文提出的方法能更準確的推斷用戶的查詢意圖。圖2對比了二者的查全率和查準率。圖2中(a)和(b)橫坐標代表測試的7組數據，縱坐標分別代表每組數據的查全率和查準率。由圖2 可見，本文提出的方法效果更優。

表1 DBLP數據集上的測試結果

圖2 DBLP上的檢索性能

4 結 語

本文提出了XML關鍵詞查詢中推斷目標節點的方法。首先構建了標簽信息表和文本信息表用來存儲XML文件的元素節點和文本節點，通過分別匹配兩個表識別查詢目標是標簽還是文本，以此解決查詢關鍵詞二義性的問題。然后借鑒對數函數和概率函數的思想分別對標簽信息和文本信息計算得到綜合相似性得分，最后對得分結果進行排序。給出了該方法實現的主要算法，并通過實驗驗證了該方法的可行性。結果表明，利用該方法可以得到理想的檢索目標。今后將進一步優化算法，并結合其中的語義進行研究[14,15]，以期能得到更好的結果。

[1] Schmidt A,Kersten M,Windhouwer M.Querying XML documents made easy:Nearest concept queries[C]//Proceedings of the 17th International Conference on Data Engineering (ICDE),Heidelberg,April 2-4,2001,IEEE Computer Society,2001.

[2] Li Y,Yu C,Jagadish H V.Schema-free XQuery[C]//Proceedings of the 30th International Conference on Very Large Data Bases(VLDB),Toronto,August 30-September 3,2004,Morgan Kaufmann Press,2004.

[3] Xu Y,Papakonstantinou Y.Efficient keyword search for smallest LCAs in XML databases[C]//Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD),Baltimore,June 13-16,2005,ACM Press,2005.

[4] Sun C,Chan C Y,Goenka A K.Multiway SLCA-based keyword search in XML data[C]//Williamson C L eds: Proceedings of the 16th International Conference on World Wide Web(WWW),Banff,May 8-12,2007,ACM Press,2007.

[5] Liu Z,Chen Y.Identifying meaningful return information for XML keyword search[C]//Proceedings of the ACM SIGMOD International Conference on Management of Data(SIGMOD),Beijing,June 11-14,2007,ACM Press,2007.

[6] Bao Z,Ling T W,Chen B,et al.Effective XML keyword search with relevance oriented ranking[C]//Proceedings of the 25th International Conference on Data Engineering(ICDE), Shanghai, March 29 - April 2,2009,IEEE Press,2009.

[7] Bao Z,Lu J,Ling T W.XReal:AN interactive XML keyword searching[C]//Proceedings of the 19th ACM Conference on Information and Knowledge Management(CIKM),Tronto,October 26-30,2010,ACM Press,2010.

[8] Guo L,Shao F,Botev C,et al.XRANK:Ranked keyword search over XML documents[C]//Proceedings of the 2003 ACM SIGMOD Conference on Management of Data,California,June 9-12,2003,ACM Press,2003.

[9] Cohen S,Mamou J,Kanza Y Sagiv.XSEarch: A semantic search engine for XML[C]//Proceedings of the 29th International Conference on Very Large Data Bases(VLDB),Berlin,September 9-12,2003,Morgan Kaufmann Press,2003.

[10] Li G,Ooi B C,Feng J,et al.EA SE:An effective 3-in-l keyword search method for unstructured,semi-structured and structured data[C]//Proceedings of the International Conference on Management of Data(SIGMOD),Vancouver,June 9-12,2008,ACM Press,2008.

[11] Termehchy A,Winslett M.Using structural information in XML keyword search effectively[J].ACM Trans on Database System(TODS),2011,36(1):1-35.

[12] 郭文琪,陳群,婁穎.一種推斷XML關鍵字檢索目標節點的方法[J].計算機工程,2012,38(8):41-49.

[13] 張欣毅.XML簡明教程[M].北京:清華大學出版社,2009:46-55.

[14] 黃瑞,史忠植.一種新的Web異構語義信息搜索方法[J].計算機研究與發展,2008,45(8):1338-1345.

[15] 李瑞霞,蘇守寶,周先存.一種基于語義相關度的XML關鍵字查詢排序方法[J].吉林大學學報:理學版,2013,51(6):1118-1122.

TARGET NODE-ORIENTED XML KEYWORD QUERY AND RANKING

Li Ruixia Liu Renjin Zhou Xiancun

(SchoolofInformationEngineering,WestAnhuiUniversity,Lu’an237012,Anhui,China)

In order to accurately conclude user’s query intent, we proposed an XML keyword query and ranking method. First, according to the structure and semantics of XML document, the method sets up tag_info table and text_info table respectively to represent the document structure and data, then determines the score of similarity between querying keywords and target node by two indicators of label and text, and gives the sorting approach as well as the algorithm to implement the method. Finally, we verified the effectiveness of the method through experiment; experimental results showed that the proposed method could more accurately conclude the target node of users query.

XML

2014-08-24。國家自然科學基金青年基金項目(6130 3209)；安徽省高等學校省級自然科學研究重點項目(KJ2013A255)。李瑞霞，副教授，主研領域：智能數據挖掘及應用。劉仁金，教授。周先存，副教授。

TP301

A

10.3969/j.issn.1000-386x.2016.04.008

query Sorting Target node