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

基于關(guān)鍵詞權(quán)重的XML查詢結(jié)果排序方法①

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

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

XML; 關(guān)鍵字查詢; 關(guān)鍵詞權(quán)重; 結(jié)果排序

在信息檢索領(lǐng)域, 關(guān)鍵詞搜索是一種簡(jiǎn)單而高效的信息獲取方式. 與XML結(jié)構(gòu)化查詢相比, XML關(guān)鍵字查詢?yōu)橛脩籼峁┝朔浅：?jiǎn)單實(shí)用的查詢接口, 操作比較簡(jiǎn)單、靈活, 對(duì)用戶而言是一種比較友好且便捷的查詢方式. 此外, 選擇關(guān)鍵字查詢不需要額外學(xué)習(xí)復(fù)雜的查詢語(yǔ)言和書寫準(zhǔn)確的查詢表達(dá)式, 更不需要深入了解XML復(fù)雜的文檔結(jié)構(gòu), 用戶只需要提供查詢內(nèi)容的關(guān)鍵字就可以檢索需要的信息.

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

1 問題的提出

考慮圖1所示的XML文檔實(shí)例, 關(guān)鍵字查詢Q1為“xml, keyword, twig”, 用戶的查詢意圖是要搜索有關(guān)XML、Keyword和twig的文獻(xiàn)資料. 查詢結(jié)果得到兩個(gè)SLCA(最近最小公共祖先) 即SLCA1: Artile1和SLCA2: Artile3. 將查詢Q1修改為查詢Q2“xml, twig, keyword”后 Artile1 和Artile3 仍然是查詢后的結(jié)果.對(duì)于當(dāng)前的查詢和排序方法而言, 查詢Q1和Q2沒有太大的區(qū)別, 因?yàn)樗鼈冇上嗤年P(guān)鍵字組成. 但是查詢Q1和Q2的查詢意圖是有區(qū)別的, 查詢Q1強(qiáng)調(diào)的是keyword查詢而查詢Q2更強(qiáng)調(diào)twig查詢. 對(duì)于查詢Q1, Artile1更符合用戶的查詢意圖, 是一篇有關(guān)于XML keyword查詢的文獻(xiàn). 而對(duì)于查詢Q2, Artile3明顯更符合用戶的查詢意圖, 是一篇與XML twig查詢相關(guān)的文獻(xiàn), 僅僅是涉及到了keyword查詢的知識(shí).因此, 針對(duì)查詢Q1和查詢Q2, 查詢結(jié)果可以相同但是最后返回用戶的查詢結(jié)果排序應(yīng)該是有所差異的.

圖1 XML文檔實(shí)例

由此可見, 即使兩個(gè)查詢中包含的關(guān)鍵詞是相同的, 只是關(guān)鍵詞的順序不同, 為反映查詢意圖的差異性, 查詢結(jié)果雖然相同但排序結(jié)果也應(yīng)該有所不同.因此, 在查詢結(jié)果排序時(shí)應(yīng)該考慮關(guān)鍵詞的順序因素.

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

2 有關(guān)概念和術(shù)語(yǔ)

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

定義2. Dewey編碼. 給定對(duì)應(yīng)XML數(shù)據(jù)的標(biāo)簽有向樹G=(V, E, R, A), G中任意結(jié)點(diǎn)的擴(kuò)展Dewey編碼由下列規(guī)則確定:

(1) 根結(jié)點(diǎn)r的Dewey編碼為“0”.

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

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

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

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

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

定義5. 權(quán)重關(guān)系樹[1]. 在搜索所得到的結(jié)果SLCA中保留包含關(guān)鍵字結(jié)點(diǎn), 刪除所有不包含關(guān)鍵字的結(jié)點(diǎn)并為關(guān)鍵字結(jié)點(diǎn)設(shè)置權(quán)重, 從而形成僅包含所有關(guān)鍵字的樹形結(jié)構(gòu).

定義6. SLCA的重要程度. 權(quán)重關(guān)系樹中所有結(jié)點(diǎn)的重要程度之和作為整個(gè)關(guān)系樹的重要程度, 即關(guān)系樹對(duì)應(yīng)的SLCA結(jié)點(diǎn)的重要程度.

3 基于關(guān)鍵詞權(quán)重的排序方法

3.1 Stack算法

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

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

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

(3) 判斷最長(zhǎng)的公共前綴, 對(duì)不包含最長(zhǎng)的公共前綴的條目進(jìn)行出棧處理. 當(dāng)且僅當(dāng)Keywords[i] = true(i[0,∈k]), 并且不會(huì)被下面的條目改變狀態(tài)時(shí)Stack中保存的元素即為目標(biāo)SLCA結(jié)點(diǎn), 所有目標(biāo)SLCA 結(jié)點(diǎn)構(gòu)成的集合即為SLCA結(jié)點(diǎn)集.

3.2 根據(jù)關(guān)鍵詞的權(quán)重設(shè)置關(guān)系樹的關(guān)鍵字結(jié)點(diǎn)權(quán)重

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

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

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

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

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

4 根據(jù)結(jié)點(diǎn)重要程度對(duì)查詢結(jié)果排序

4.1 關(guān)鍵字結(jié)點(diǎn)的重要程度

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

在權(quán)重關(guān)系樹中, 不同位置的關(guān)鍵字結(jié)點(diǎn)對(duì)應(yīng)的對(duì)查詢結(jié)點(diǎn)Q的要求是不同的, 不同的關(guān)鍵字的結(jié)點(diǎn)對(duì)應(yīng)的權(quán)重也是不相同的, 因此關(guān)系樹中各關(guān)鍵字結(jié)點(diǎn)相對(duì)于查詢結(jié)點(diǎn)的重要程度是不同的. 單就結(jié)構(gòu)方面而言, 關(guān)系樹中查詢結(jié)點(diǎn)的子結(jié)點(diǎn)是最重要, 查詢結(jié)點(diǎn)的后代結(jié)點(diǎn)中距離查詢結(jié)點(diǎn)的層次越深, 結(jié)點(diǎn)相對(duì)于查詢結(jié)點(diǎn)的重要程度就越低. 如圖2所示, 結(jié)點(diǎn)的重要程度依次為a1＞a2, b1＞b2＞b3, c1＞c2＞c3.

圖2 關(guān)系樹

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

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

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

按上述方法, 假設(shè)輸入的關(guān)鍵字為a2, b2, c3, 設(shè)定權(quán)重遞減率為R, 則對(duì)應(yīng)的關(guān)鍵字結(jié)點(diǎn)的重要程度為:

4.2 非關(guān)鍵字結(jié)點(diǎn)的重要程度

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

其中Ni為每一層的非關(guān)鍵字結(jié)點(diǎn)的數(shù)量, k也可以看做是每一層的非關(guān)鍵字結(jié)點(diǎn)的權(quán)重大小.

每個(gè)SLCA的重要程度可以表示為關(guān)鍵字結(jié)點(diǎn)和非關(guān)鍵字結(jié)點(diǎn)的和, 為突出關(guān)鍵字結(jié)點(diǎn)的重要程度的重要性, 我們適當(dāng)降低了非關(guān)鍵字結(jié)點(diǎn)權(quán)重在SLCA的重要程度中所占的比重, 每個(gè)SLCA的重要程度即可表示為:

其中, S1表示為所有關(guān)鍵字結(jié)點(diǎn)的重要程度的總和.

4.3 排序算法

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

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

由每個(gè)結(jié)點(diǎn)的重要程度統(tǒng)計(jì)每個(gè)Ti的重要程度; if 兩個(gè)結(jié)點(diǎn)是father-childhood關(guān)系

father←a*childhood* Wi // 為每個(gè)關(guān)鍵詞的權(quán)重值

else if ancestor-offspring .//祖先-后代關(guān)系

ancestor←b*offspring* Wi.

計(jì)算所有非關(guān)鍵字節(jié)點(diǎn)的重要程度之和;

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

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

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

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

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

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

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

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

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

表2 Stack算法與本文排序結(jié)果準(zhǔn)確率的對(duì)比

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

圖3 Stack算法與本文排序方法準(zhǔn)確率的對(duì)比

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

6 結(jié)語(yǔ)

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

1 任建華,周建,孟祥福,等.基于關(guān)鍵字之間結(jié)構(gòu)關(guān)系的XML查詢結(jié)果排序方法.計(jì)算機(jī)科學(xué),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關(guān)鍵詞搜索結(jié)果排序方法.小型微型計(jì)算機(jī)系統(tǒng),2014,(12):2681–2685.

9 孟小峰.XML數(shù)據(jù)管理.北京:清華大學(xué)出版社, 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ù)查詢和檢索技術(shù).北京:清華大學(xué)出版社,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;收到修改稿時(shí)間:2016-08-18

10.15888/j.cnki.csa.005683