魏東平, 苑志朋(中國石油大學(華東) 計算機與通信工程學院, 青島 266580)

基于關鍵詞權重的XML查詢結果排序方法①

魏東平, 苑志朋
(中國石油大學(華東) 計算機與通信工程學院, 青島 266580)

XML關鍵字查詢結果質量不高的一個很重要的原因是查詢關鍵詞難以反映用戶真實的查詢意圖, 而給關鍵詞設置權重在一定程度上可以解決這一難題. 本文結合關鍵字之間的結構關系提出了一種新的結果排序方法, 該方法給查詢關鍵詞設置權重, 并參照查詢關鍵詞的權重給包含關鍵字的結點設定結點權重, 然后根據(jù)關系樹中的結點權重和關鍵詞之間結構關系[1]統(tǒng)計SLCA結點的重要程度, 再以此依據(jù)對查詢結果進行排序, 最后返回給用戶有序的查詢結果. 實驗結果和分析表明, 提出的排序方法具有較高的準確率, 能夠較好地滿足用戶查詢的需求和偏好.

XML; 關鍵字查詢; 關鍵詞權重; 結果排序

在信息檢索領域, 關鍵詞搜索是一種簡單而高效的信息獲取方式. 與XML結構化查詢相比, XML關鍵字查詢?yōu)橛脩籼峁┝朔浅：唵螌嵱玫牟樵兘涌? 操作比較簡單、靈活, 對用戶而言是一種比較友好且便捷的查詢方式. 此外, 選擇關鍵字查詢不需要額外學習復雜的查詢語言和書寫準確的查詢表達式, 更不需要深入了解XML復雜的文檔結構, 用戶只需要提供查詢內容的關鍵字就可以檢索需要的信息.

但是, 由于XML數(shù)據(jù)具有復雜的結構信息, 簡單的關鍵字查詢方法在準確表達查詢意圖方面差強人意.一種比較有效的方法是對查詢結果進行排序. 對XML關鍵字查詢結果的排序方法的研究已經(jīng)取得了許多成果. XRank[2]將信息檢索中的PageRank方法擴展到XML排序, 使XML文檔的結構特征反映在排序中.在XSEarch[3]中使用了一種基于tf*idf的排序機制對查詢結果進行排序. EASE[4]將基于tf*idf的信息檢索排序機制與基于結構緊湊度的數(shù)據(jù)庫排序機制相結合,實現(xiàn)在異構數(shù)據(jù)上的關鍵詞搜索. XReal[5]設計了一個基于tf*idf的排序機制. 文獻[6]則提出了一種XML關鍵詞查詢結果類型的推導方法, 但是沒有對查詢結果進行排序. 文獻[7]則提出了一種可以有效排列組合成用戶容易理解的查詢結果.

1 問題的提出

考慮圖1所示的XML文檔實例, 關鍵字查詢Q1為“xml, keyword, twig”, 用戶的查詢意圖是要搜索有關XML、Keyword和twig的文獻資料. 查詢結果得到兩個SLCA(最近最小公共祖先) 即SLCA1: Artile1和SLCA2: Artile3. 將查詢Q1修改為查詢Q2“xml, twig, keyword”后 Artile1 和Artile3 仍然是查詢后的結果.對于當前的查詢和排序方法而言, 查詢Q1和Q2沒有太大的區(qū)別, 因為它們由相同的關鍵字組成. 但是查詢Q1和Q2的查詢意圖是有區(qū)別的, 查詢Q1強調的是keyword查詢而查詢Q2更強調twig查詢. 對于查詢Q1, Artile1更符合用戶的查詢意圖, 是一篇有關于XML keyword查詢的文獻. 而對于查詢Q2, Artile3明顯更符合用戶的查詢意圖, 是一篇與XML twig查詢相關的文獻, 僅僅是涉及到了keyword查詢的知識.因此, 針對查詢Q1和查詢Q2, 查詢結果可以相同但是最后返回用戶的查詢結果排序應該是有所差異的.

圖1 XML文檔實例

由此可見, 即使兩個查詢中包含的關鍵詞是相同的, 只是關鍵詞的順序不同, 為反映查詢意圖的差異性, 查詢結果雖然相同但排序結果也應該有所不同.因此, 在查詢結果排序時應該考慮關鍵詞的順序因素.

對于XML 關鍵詞查詢, 不能簡單地看作是幾個關鍵詞的集合, 而應該將其看作是幾個關鍵詞的序列,在這個序列中隱含了某些真實的查詢意圖[8]. 為關鍵詞設置權重可以在一定程度上反應用戶的真實查詢意圖, 進而優(yōu)先返回用戶需要的查詢結果.

2 有關概念和術語

定義1. XML樹模型[9]. 一個XML文檔可以看成是帶標簽的有向樹D(r, V, E), r表示樹的根結點, V表示結點集合, E表示邊的集合.

定義2. Dewey編碼. 給定對應XML數(shù)據(jù)的標簽有向樹G=(V, E, R, A), G中任意結點的擴展Dewey編碼由下列規(guī)則確定:

(1) 根結點r的Dewey編碼為“0”.

(2) 在寬度優(yōu)先遍歷G的過程中, 如果結點v是結點u的第i個孩子結點, 那么結點v的Dewey編碼為“D(u).i-1”. 其中, D(u)表示結點u的Dewey編碼.

定義3. 關鍵字匹配集合[9]. 給定XML文檔D和關鍵字k, 用KMS(k)表示文檔D中所有匹配關鍵字k的結點集合, KMS(k)={v|vV, ∈k=tag(v)或k=val(v)}.

定義4. 最小最低公共祖先SLCA(smallest lowest common ancestor). 即它包含所有關鍵字的最緊致片段.如果文檔樹中結點V已經(jīng)包含所有查詢關鍵字, 那么V的祖先結點就不應該再作為SLCA返回. 給定查詢Q(k1,k2,…,kn), 我們說結果R滿足SLCA語義, SLCA結點必須滿足以下兩個條件:

(1) R至少包含全部查詢關鍵字一次, 所謂包含即關鍵字ki出現(xiàn)在以R為根的子樹下.

(2) R的任意后代結點都不可能同樣包含k1, k2, …, kn全部關鍵字.

定義5. 權重關系樹[1]. 在搜索所得到的結果SLCA中保留包含關鍵字結點, 刪除所有不包含關鍵字的結點并為關鍵字結點設置權重, 從而形成僅包含所有關鍵字的樹形結構.

定義6. SLCA的重要程度. 權重關系樹中所有結點的重要程度之和作為整個關系樹的重要程度, 即關系樹對應的SLCA結點的重要程度.

3 基于關鍵詞權重的排序方法

3.1 Stack算法

Stack[10]算法的具體描述如下:

(1) 獲取每個關鍵字倒排表, 選取關鍵字倒排表中最小Dewey編碼初始化棧.

(2) 從所有關鍵字倒排表中剩余的Dewey編碼中選取最小Dewey編碼進行進棧處理.

(3) 判斷最長的公共前綴, 對不包含最長的公共前綴的條目進行出棧處理. 當且僅當Keywords[i] = true(i[0,∈k]), 并且不會被下面的條目改變狀態(tài)時Stack中保存的元素即為目標SLCA結點, 所有目標SLCA 結點構成的集合即為SLCA結點集.

3.2 根據(jù)關鍵詞的權重設置關系樹的關鍵字結點權重

用戶在進行關鍵字查詢時輸入的關鍵字在一定程度上會反映出用戶的查詢意圖, 而關鍵詞的先后順序會體現(xiàn)出用戶對每個關鍵詞的重視程度. 本文主要是通過直接輸入關鍵詞的權重或關鍵詞的先后順序來確定關系樹中包含關鍵字的結點的權重. 在關鍵字查詢時用戶可以自己來指定每個關鍵詞的權重大小, 關鍵字查詢時輸入的查詢形式為(k1w1, k2w2, ……, knwn),其中, k為查詢關鍵詞, w為對應關鍵詞的權重. 這種由用戶直接確定關鍵詞權重的方式雖然不方便, 但是可以更好地體現(xiàn)出用戶的真實查詢意圖.

當用戶未指定每個關鍵詞的權重時由查詢系統(tǒng)為關鍵詞設置權重的大小. 我們設定權重時既要考慮到關鍵詞的順序又要考慮到關鍵字在文檔中出現(xiàn)的頻率,我們根據(jù)關鍵詞的先后順序并結合關鍵字在文檔中出現(xiàn)的頻率設定每個關鍵詞的權重大小, 查詢的關鍵詞的權重大小定義為:

其中, R(0＜R≤1)為關鍵詞權重遞減的比例系數(shù), N為文檔的總數(shù)量, fk為包含關鍵字k的文檔的數(shù)量. 例如查詢Q3(XML, DTD, Query), 用戶沒有指定每個關鍵詞的權重, 那么系統(tǒng)就會默認的設定關鍵詞的權重. 就體現(xiàn)關鍵詞順序因素的權重而言, 一般情況下第一個關鍵詞權重默認為1, 從第二個關鍵詞開始關鍵詞的部分權重會逐步遞減, 權重遞減率設定為R. 查詢Q3的關鍵詞權重就可以設置為XML: 1*ln(N/(fxml+1)), DTD: R*ln(N/(fDTD+1)), Query: R2*ln(N/(fQuery+1)), 其中R的值可以由用戶指定, 也可以由系統(tǒng)默認設定,目的就是為每一個關鍵詞預設好權重, 方便之后的結果排序.

由Stack算法求得的結點SLCA為根的子樹中不僅包含了所有的查詢關鍵詞而且反映了結果子樹中所有關鍵詞的結構關系, 遍歷以結點SLCA為根的結果子樹, 記錄每一層的非關鍵字結點并刪除每個SLCA中所有的非關鍵字結點, 對SLCA中的關鍵字結點進行權重設置, 按照輸入關鍵詞查詢時的設定的權重值為結果子樹中所有的關鍵字結點賦權重值, 可以得到結點為帶權重值的關鍵字的樹形結構, 該結果子樹中可以通過父——子關系和祖先——后代關系的位置關系反映出所有關鍵字之間的結構關系, 如算法1所示.

算法1. RTW(Relationship Tree with Weight)算法輸入: SLCA結點鏈表S, 關鍵詞權重輸出: 權重關系樹, 數(shù)組a For each SLCAS Do∈Traversal(SLCA);//遍歷以SLCA結點為根的子樹if 結點為非關鍵字結點{a[i]←每層非關鍵字結點個數(shù)

4 根據(jù)結點重要程度對查詢結果排序

4.1 關鍵字結點的重要程度

在查詢所得的SLCA轉化成為的關系樹中, 所有關鍵字結點的權重值與關鍵字結點對查詢結點的嚴格程度結合后可以反映出該關系樹對查詢結果的重要程度, 該關系樹對查詢結果的重要程度越高, 則該關系樹對應的查詢結果應該更加符合用戶的查詢意圖, 應該優(yōu)先返回給查詢用戶.

在權重關系樹中, 不同位置的關鍵字結點對應的對查詢結點Q的要求是不同的, 不同的關鍵字的結點對應的權重也是不相同的, 因此關系樹中各關鍵字結點相對于查詢結點的重要程度是不同的. 單就結構方面而言, 關系樹中查詢結點的子結點是最重要, 查詢結點的后代結點中距離查詢結點的層次越深, 結點相對于查詢結點的重要程度就越低. 如圖2所示, 結點的重要程度依次為a1＞a2, b1＞b2＞b3, c1＞c2＞c3.

圖2 關系樹

假設查詢結點Q的重要程度默認為1, 則設定中間結點的重要程度小于1. 設father=a*childhood, ancestor=b*offspring, 其中a, b分別為父親——孩子或祖先——后代重要程度的遞減系數(shù), 因此中間結點的重要程度為:

(1) 父親——孩子關系: pn=a*pn-1. 其中, pn是pn-1的孩子. 如圖2中: a1=a*1=a.

(2) 祖先——后代關系: pn=b*pn-1. 其中, pn是pn-1的后代. 如圖2中: c2=b*(a*1)=b*a.

按上述方法, 假設輸入的關鍵字為a2, b2, c3, 設定權重遞減率為R, 則對應的關鍵字結點的重要程度為:

4.2 非關鍵字結點的重要程度

根據(jù)在生成關系樹時返回的每一層非關鍵字結點的數(shù)量統(tǒng)計以SLCA結點為根的子樹中所有非關鍵字結點的重要程度, 相比較關鍵字結點的重要程度, 非關鍵字結點的重要程度所占比重要相對較低. 我們設定根節(jié)點的權重值為1, 從根節(jié)點往下每一層的非關鍵字結點的權重值逐漸減小, 我們設定權重的遞減率為k(0＜k≤1), 則每個SLCA中的所有非關鍵字結點的權重值為:

其中Ni為每一層的非關鍵字結點的數(shù)量, k也可以看做是每一層的非關鍵字結點的權重大小.

每個SLCA的重要程度可以表示為關鍵字結點和非關鍵字結點的和, 為突出關鍵字結點的重要程度的重要性, 我們適當降低了非關鍵字結點權重在SLCA的重要程度中所占的比重, 每個SLCA的重要程度即可表示為:

其中, S1表示為所有關鍵字結點的重要程度的總和.

4.3 排序算法

SLCA的重要程度可以反映出用戶對該SLCA的偏好程度, 在查詢結果中SLCA的重要程度越高就越符合用戶的查詢意圖, 應該將該查詢結果優(yōu)先返回給用戶. 本文使用基于關鍵詞權重并結合結構關系的排序算法—WS-Rank算法, 通過排序算法對SLCA的重要程度進行統(tǒng)計計算, 并根據(jù)SLCA重要程度的計算結果對所有的SLCA進行排序, 排序算法的目標就是使得重要程度高的查詢結果優(yōu)先返回給查詢用戶. WS-Rank算法如算法2所示.

算法2. WS-Rank算法輸入: 權重關系樹Ti; 關鍵詞權重Wi輸出: 順序SLCAs鏈表for each TiT do{∈{ TiTraversal(Ti);//遍歷Ti關系樹

由每個結點的重要程度統(tǒng)計每個Ti的重要程度; if 兩個結點是father-childhood關系

father←a*childhood* Wi // 為每個關鍵詞的權重值

else if ancestor-offspring .//祖先-后代關系

ancestor←b*offspring* Wi.

計算所有非關鍵字節(jié)點的重要程度之和;

根據(jù)SLCA的重要程度降序排列成鏈表

返回給用戶順序SLCAs鏈表 .//END

5 實驗

實驗是在一臺Intel(R) Core(TM) i3-2310M CPU @ 2.10GHz, 4.00GB內存, 500GB硬盤和Windows 7操作系統(tǒng)的PC機上進行的, 基于數(shù)據(jù)集BookDB.xml,針對本文提出的排序方用Java語言和eclipse3.0編譯工具借助Stack算法建立了XML關鍵字查詢系統(tǒng), 對排序方法進行驗證.

評價XML關鍵字查詢的一個重要指標是準確率.準確率(Precision)是指查詢結果中與用戶真實查詢意圖相關的元素所占總元素的比率[6]. 實驗中, 通過查詢系統(tǒng)對提出的排序方法進行測試, 并調查該系統(tǒng)用戶的使用情況, 驗證基于關鍵詞權重的XML關鍵字查詢結果排序方法的準確率. 驗證實驗邀請了5位測試者, 根據(jù)各自的需求和偏好, 在BookDB.xml上分別進行關鍵字測試查詢(見下表1).

表1 數(shù)據(jù)集上的5條測試查詢

完整的BookDB.xml數(shù)據(jù)集H中包含了大約50000個不同的元素, 從中查找所有與測試者真實查詢意圖相匹配的元素工作量太大. 因此, 我們在查詢測試時使用了抽樣數(shù)據(jù)集, 抽樣數(shù)據(jù)集Hi是從完整數(shù)據(jù)集中隨機抽取100條元素組成的, 實驗階段只需將在數(shù)據(jù)集Hi上的查詢排序結果與測試者在數(shù)據(jù)集Hi中標示出的滿足真實查詢意圖的記錄結果作對比. 值得注意的是, 對于本文排序方法, 如果排序后結果中與用戶查詢意圖相同的元素數(shù)量越多, 則排序算法的準確率就越高.

在權重關系樹中使用WS-Rank算法對關系樹中關鍵字之間的結構關系和結點的權重進行量化可以得到SLCA結點的重要程度, 進而得出查詢結果的重要程度. 本次試驗設定R=0.8(0＜R≤1), 由于0＜b＜a＜1, a2＜b, 通過計算可以對比每個權重關系樹的重要程度大小即SLCA結點的重要程度, 因此我們以SLCA的重要程度為依據(jù)對所有的SLCA進行排序, 重要程度高的查詢結果優(yōu)先返回給用戶.

將在數(shù)據(jù)集Hi上的經(jīng)查詢排序后得到的前10個返回結果與測試者在數(shù)據(jù)集Hi中標示出的前10個滿足真實查詢意圖的記錄結果作對比, 實驗結果見表2.準確率可以用得到的兩類結果數(shù)的比率表示, 即:

表2 Stack算法與本文排序結果準確率的對比

為更形象具體表現(xiàn)排序算法的查詢的準確性, 我們將Stack算法所得的結果與WS-Rank排序算法的查詢結果準確率作對比的柱狀圖如圖3所示.

圖3 Stack算法與本文排序方法準確率的對比

對比表2和圖3的實驗數(shù)據(jù), 經(jīng)過排序算法處理后返回的查詢結果與Stack算法直接得到的查詢結果的準確率相比, 查詢結果的準確率得到了明顯的提高,能夠更好地反映用戶的查詢意圖.

6 結語

本文提出了一種基于關鍵詞權重并結合關鍵字結構關系的XML關鍵字查詢結果排序方法. 該方法首先是通過Stack算法求解SLCA, 將得到的結果SLCA經(jīng)過RTW算法處理后得到權重關系樹, 根據(jù)權重關系樹中結點的權重值和關鍵字之間的結構關系以及量化每個SLCA的重要程度, 并以此為依據(jù)對所有SLCA進行排序, 返回給用戶有序的排序結果. 最終的實驗結果證明, 本文提出的WS-Rank排序方法能夠有效提高關鍵字的查詢的準確率. 更深入的研究主要是在提高結果排序的效率的同時如何考慮用戶的偏好, 考慮到用戶偏好的結果排序方法能夠更好地滿足用戶的查詢需求.

1 任建華,周建,孟祥福,等.基于關鍵字之間結構關系的XML查詢結果排序方法.計算機科學,2013,40(6):178–182.

2 Guo L, Shao F, Botev C, et al. XRANK: Ranked keyword search over XML documents. ACM SIGMOD International Conference on Management of Data. ACM. 2003. 16–27.

3 Mamou J, Kanza Y, Cohen S, et al. XSEarch: A semantic search engine for XML. International Conference on Very Large Data Bases-Volume. 2003. 45–56.

4 Li GL, Ooi BC, Feng JH, et al. EASE: An effective 3-in-1 keyword search method for unstructured, semi-structured and structured data. ACM SIGMOD International Conference on Management of Data. ACM. 2008. 903–914.

5 Bao Z, Ling TW, Chen B, et al. Effective XML keyword search with relevance oriented ranking. IEEE International Conference on Data Engineering. IEEE Computer Society. 2009. 517–528.

6 Li J, Liu C, Zhou R, et al. Suggestion of promising result types for XML keyword search. International Conference on Extending Database Technology. ACM. 2010. 561–572.

7 Liu Z, Cai Y, Shan Y, et al. Ranking Friendly Result Composition for XML Keyword Search. Conceptual Modeling. Springer International Publishing, 2015.

8 劉喜平.QWS-Rank:一種新穎的XML關鍵詞搜索結果排序方法.小型微型計算機系統(tǒng),2014,(12):2681–2685.

9 孟小峰.XML數(shù)據(jù)管理.北京:清華大學出版社, 2009.

10 Xu Y, Papakonstantinou Y. Efficient keyword search for smallest LCAs in XML databases. ACM SIGMOD International Conference on Management of Data. ACM. 2005. 537–538.

11 陸嘉恒.XML數(shù)據(jù)查詢和檢索技術.北京:清華大學出版社,2013.

Results Ranking Method of XML Search Based on Keyword Weight

WEI Dong-Ping, YUAN Zhi-Peng
(College of Computer and Communication Engineering, China University of Petroleum, Qingdao 266580, China)

A very important reason for low quality results of XML keyword searching is that it is difficult to reflect the user’s query intent. In this paper, setting keywords weight could resolve this problem to a certain extent. A new method of query results sort based on keywords weight and keywords structure is proposed. This method sets keywords weight and sets nodes weight for every node that contains keywords, according to keywords weight. The importance of the SLCA node is estimated according to the nodes weight in the relation tree and the relationship between keywords. The query results are sorted on the importance of SLCA nodes. The experimental results show that the proposed method has higher accuracy for sorting.

XML; keyword search; keyword weight; results sort

2016-07-16;收到修改稿時間:2016-08-18

10.15888/j.cnki.csa.005683