基于擴(kuò)展查詢表達(dá)式的XML關(guān)鍵字查詢

朱菁華,王曉玲

(復(fù)旦大學(xué)計(jì)算機(jī)科學(xué)技術(shù)學(xué)院,上海200433)

基于擴(kuò)展查詢表達(dá)式的XML關(guān)鍵字查詢

朱菁華,王曉玲

(復(fù)旦大學(xué)計(jì)算機(jī)科學(xué)技術(shù)學(xué)院,上海200433)

目前可擴(kuò)展標(biāo)示語言(XML)關(guān)鍵字查詢大多是基于最小公共祖先(LCA)語義子樹產(chǎn)生查詢結(jié)果,而未能加入除LCA語義子樹之外與用戶查詢意圖相關(guān)的結(jié)果。為解決該問題,提出一種基于擴(kuò)展查詢表達(dá)式的XML關(guān)鍵字查詢方法。將用戶查詢?nèi)罩咀鳛椴樵償U(kuò)展統(tǒng)計(jì)模型,對其進(jìn)行統(tǒng)計(jì)分析,并結(jié)合最佳檢索概念判斷是否需要擴(kuò)展查詢表達(dá)式。使用XML TF-IDF方法計(jì)算候選屬性的權(quán)重,根據(jù)初檢結(jié)果的上下文信息,利用聚類方法獲得與查詢意圖最相關(guān)的擴(kuò)展查詢關(guān)鍵字,從而擴(kuò)展查詢表達(dá)式。實(shí)驗(yàn)結(jié)果表明,與XSeek和基于語義詞典的查詢擴(kuò)展方法相比,該方法的平均F度量值分別提高了7%和17%,具有較高的查詢質(zhì)量。

信息檢索;可擴(kuò)展標(biāo)示語言;最小公共祖先語義;關(guān)鍵字查詢;查詢擴(kuò)展;上下文信息

1 概述

信息檢索中的一個主要挑戰(zhàn)就是如何精確判斷用戶的查詢意圖,而關(guān)鍵字查詢方式由于缺乏足夠的結(jié)構(gòu)和語義信息,使得其查詢結(jié)果往往無法令用戶滿意。如今,可擴(kuò)展標(biāo)示語言(eXtensible Markup Language,XML)由于其靈活性等優(yōu)點(diǎn),被廣泛應(yīng)用于Web上。所以,如何幫助用戶產(chǎn)生精確的查詢表達(dá)式對于XML關(guān)鍵字查詢是很有必要的。

目前,XML關(guān)鍵字查詢的研究大多都是基于最小公共祖先(Lowest Common Ancestor,LCA)概念來確定相關(guān)語義片段子樹[1]。針對LCA存在嵌套的問題,文獻(xiàn)[2]提出了最近最小公共祖先(Smallest LCA,SLCA)。SLCA是一個最小LCA子樹,包含所有關(guān)鍵字且該子樹的任一子樹都不再包含所有關(guān)鍵字。

雖然現(xiàn)在多數(shù)的XML關(guān)鍵字查詢方法通過對LCA語義片段的裁剪能有效地去除不相關(guān)的信息,但它們都是只針對LCA子樹中的內(nèi)容進(jìn)行裁剪,而把LCA子樹外的內(nèi)容認(rèn)為是不相關(guān)的。顯然這樣的查詢結(jié)果未必能滿足用戶的查詢意圖。由于XML文檔層次特點(diǎn)與用戶查詢意圖相關(guān)的內(nèi)容完全可能不在LCA子樹中,而基于多數(shù)LCA語義的XML關(guān)鍵字查詢方法,雖然可以過濾與查詢不相關(guān)的信息,但也會降低查詢的查全率。

為解決該問題,因此本文提出一種基于擴(kuò)展查詢表達(dá)式的方法?？偨Y(jié)了多數(shù)基于LCA語義的XML關(guān)鍵字查詢方法工作,并指出了它們的不足之處,即查詢結(jié)果受限于LCA語義子樹,未能加入LCA語義子樹外并與用戶查詢意圖相關(guān)的結(jié)果。本文主要解決了2個問題,即判斷查詢表達(dá)式是否需要擴(kuò)展和查詢表達(dá)式如何進(jìn)行擴(kuò)展。新的查詢表達(dá)式的檢索結(jié)果與初檢結(jié)果相比,會添加未被LCA語義子樹包含但與用戶查詢意圖相關(guān)的信息,從而實(shí)現(xiàn)“內(nèi)容+結(jié)構(gòu)”的XML關(guān)鍵字查詢擴(kuò)展。

2 相關(guān)工作

XSeek[3]是基于LCA語義子樹的XML關(guān)鍵字查詢的一個比較典型的方法。該方法借鑒關(guān)系數(shù)據(jù)庫中的ER模型思想為XML樹中的節(jié)點(diǎn)分類,同時用類似于XQuery的語法分析了關(guān)鍵詞查詢匹配模式,結(jié)合兩者生成的語義信息對SLCA子樹進(jìn)行裁剪。圖1是一個eBay在線拍賣的數(shù)據(jù)的XML樹。對于查詢{Seller Tony},觀察查詢語義可以猜測用戶想了解賣家Tony的相關(guān)信息。XSeek方法只返回圖中以“Seller”為根節(jié)點(diǎn)的子樹,而把其他內(nèi)容認(rèn)為是不相關(guān)的。顯然這樣的查詢結(jié)果未必能滿足用戶的查詢意圖,用戶完全可能對Payment和Shipping等信息感興趣。

圖1 eBay在線拍賣的XML文檔樹

目前,國內(nèi)外的查詢擴(kuò)展方法主要有3類:對語料庫或知識庫分析后的擴(kuò)展,局部分析方法和全局分析方法。根據(jù)語料庫獲得的查詢擴(kuò)展方法是利用語義知識詞典,然后甄選與初始查詢關(guān)鍵字概念相近或等同的詞來進(jìn)行查詢擴(kuò)展。如文獻(xiàn)[4-5]以WordNet為語義本體,能同時對查詢關(guān)鍵字的狹義詞、廣義詞、同義詞和近義詞等進(jìn)行匹配,有效地提升查詢質(zhì)量。但是,這種方法有著十分明顯的缺陷,即其擴(kuò)展的查詢關(guān)鍵字往往受限于參考的語料庫,并且只是簡單地根據(jù)語義概念進(jìn)行鏈接,從而導(dǎo)致很多無關(guān)的關(guān)鍵詞加入查詢表達(dá)式,進(jìn)而影響查準(zhǔn)率。文獻(xiàn)[6-7]以查詢?nèi)罩咀鳛檎Z料庫進(jìn)行分析和數(shù)據(jù)挖掘,能較好地保證擴(kuò)展用詞和原查詢以及查詢結(jié)果是相關(guān)聯(lián)的。但是其未能考慮諸如XML文檔這樣的半結(jié)構(gòu)化數(shù)據(jù),只適用于傳統(tǒng)的文本文檔。

局部分析方法的核心思想是通過連續(xù)2次的查詢來解決查詢表達(dá)式擴(kuò)展問題。通過初次查詢獲得最相關(guān)的K個結(jié)果作為查處擴(kuò)展詞的來源,然后,將權(quán)值較高的N個詞加入查詢表達(dá)式進(jìn)行新的查詢[8]。目前較流行的有相關(guān)反饋方法和偽相關(guān)反饋方法[9]。雖然局部分析方法是目前十分受歡迎和普通應(yīng)用的查詢擴(kuò)展方法,但其查詢質(zhì)量十分依賴初檢結(jié)果的相關(guān)性。換言之,如果第一次查詢后獲得文檔與用戶查詢意圖相關(guān)度較小時,其查詢擴(kuò)展的質(zhì)量較差。

以相似性詞典[10]等為代表的全局分析方法是在用戶提交查詢前,對所有文檔中的詞或詞組進(jìn)行統(tǒng)計(jì)分析,并計(jì)算各個詞或詞組間的關(guān)聯(lián)程度。當(dāng)用戶提交查詢后,根據(jù)先前計(jì)算的詞或詞組間的相關(guān)關(guān)系,把與查詢相關(guān)的詞添加獲得擴(kuò)展后的查詢表達(dá)式。全局分析方法的優(yōu)勢是可以十分有效地探究數(shù)據(jù)集中的詞間關(guān)系,但是這種方法僅限與符號層面的匹配,而無視了查詢關(guān)鍵詞與目標(biāo)文檔語義上的關(guān)聯(lián)程度。同時,當(dāng)數(shù)據(jù)集大小逐漸增大后,該方法在時間和空間上的開銷也十分高昂。

文獻(xiàn)[11]提出了結(jié)合2種擴(kuò)展方式的方法。該方法基于對初檢結(jié)果以及查詢?nèi)罩镜姆诸惡蛿?shù)據(jù)分析,獲得相關(guān)的擴(kuò)展詞。雖然該方法不僅面向XML數(shù)據(jù),同時也取得了較優(yōu)的查詢質(zhì)量,但是其查詢擴(kuò)展表達(dá)式仍舊是對LCA語義子樹的裁剪分類,未能有效考慮潛在的相關(guān)聯(lián)的信息。

3 數(shù)據(jù)模型

由于XSeek方法有較好的查詢質(zhì)量,因此本文提及的查詢結(jié)果子樹均是指用XSeek方法產(chǎn)生的LCA子樹。通過分析大部分XML文檔樹,可以發(fā)現(xiàn)XML文檔樹都是具有一定的語義,可以把XML文檔樹的節(jié)點(diǎn)從語義角度分為3類節(jié)點(diǎn):值節(jié)點(diǎn),屬性節(jié)點(diǎn)和實(shí)體節(jié)點(diǎn)。

定義1(值節(jié)點(diǎn)) 稱XML文檔樹T中葉子節(jié)點(diǎn)為值節(jié)點(diǎn)。例如,圖 1中的“Tony”和“848”等節(jié)點(diǎn)。

定義2(屬性節(jié)點(diǎn)) 稱XML文檔樹T中值節(jié)點(diǎn)的父親節(jié)點(diǎn)為屬性節(jié)點(diǎn)。例如,圖 1中的“SellerName”節(jié)點(diǎn)。

定義3(實(shí)體節(jié)點(diǎn)) XML文檔樹T中的節(jié)點(diǎn)若既不是屬性節(jié)點(diǎn)也不是值節(jié)點(diǎn),那么稱該節(jié)點(diǎn)為實(shí)體節(jié)點(diǎn)。例如,圖1中“Seller”和“HighBidder”等節(jié)點(diǎn)為實(shí)體節(jié)點(diǎn)。

對于XML文檔中既有葉子節(jié)點(diǎn)又有非葉子節(jié)點(diǎn)作為孩子節(jié)點(diǎn)的情況,認(rèn)為該節(jié)點(diǎn)屬于實(shí)體節(jié)點(diǎn)。

定義4(查詢結(jié)果子樹) 對于一個查詢Q和XML文檔樹T,按XSeek方法獲得一顆子樹t稱作查詢結(jié)果子樹。

定義5(實(shí)體序列) 對于查詢結(jié)果子樹t,按先后次序遍歷并記錄其中的實(shí)體節(jié)點(diǎn),所產(chǎn)生的序列稱作實(shí)體序列。

定義6(查詢上下文) 對于一個關(guān)鍵字查詢Q,其查詢上下文是:

其中,域ES為查詢結(jié)果子樹的實(shí)體序列;域WHE表示了查詢Q的限制條件,類似于SQL中的where集合;域SEL為查詢想要獲取的信息,類似于SQL中的select集合。

由于XML文檔為半結(jié)構(gòu)化數(shù)據(jù)且關(guān)鍵詞查詢方式不包含任何結(jié)構(gòu)信息,一個明顯的問題是如何確定域WHE和SEL的值。觀察SQL語言可知,查詢限制條件往往是包含了具體數(shù)值信息,而查詢目的則往往只提供不帶數(shù)值信息的數(shù)據(jù)類型信息。根據(jù)定義1～定義3可知,實(shí)體節(jié)點(diǎn)和屬性節(jié)點(diǎn)對應(yīng)于數(shù)據(jù)類型信息,而值節(jié)點(diǎn)則對應(yīng)數(shù)據(jù)值類型。根據(jù)以上分析并結(jié)合文獻(xiàn)[12]對XML關(guān)鍵詞查詢匹配模式的研究,本文由以下2個原則分別確定域WHE和SEL的值:

(1)如果關(guān)鍵字查詢中的某個關(guān)鍵字k1匹配某個實(shí)體節(jié)點(diǎn)或者屬性節(jié)點(diǎn),且不存在另一個關(guān)鍵字k2滿足:匹配某個值節(jié)點(diǎn),且該值節(jié)點(diǎn)與k1匹配的節(jié)點(diǎn)存在祖先-后代關(guān)系。那么關(guān)鍵字k1表示該查詢想要獲取的信息內(nèi)容,k1會被添加至SEL域中。

(2)未被添加至域SEL的關(guān)鍵字,即與值節(jié)點(diǎn)匹配的關(guān)鍵字,為查詢的限制條件,會被添加至域WHE。

4 擴(kuò)展查詢表達(dá)式的判斷

顯然,不是所有的查詢表達(dá)式都要擴(kuò)展,有些能完全滿足查詢意圖。因此,需要判斷哪些需要擴(kuò)展。

4.1 查詢結(jié)果分析

通常,用戶提交了查詢Qi后,如果其查詢結(jié)果子樹是相關(guān)的但缺少部分感興趣的內(nèi)容,會在Qi的基礎(chǔ)上提交新的查詢Qj。對于2個連續(xù)查詢Qi和Qj,如果Qj是對Qi的擴(kuò)展,那么它們兩者有一定的聯(lián)系。

例如,對圖 1的 XML文檔樹,如果 Qi是{IBM},Qj是{IBM Seller},Qi的查詢結(jié)果子樹以“ItemInfo”為根節(jié)點(diǎn),Qj的查詢結(jié)果子樹是Qi的查詢結(jié)果子樹加上以Seller為根節(jié)點(diǎn)的子樹。比較它們的查詢上下文可以發(fā)現(xiàn):Qi的ES是Qj的ES的子集,即Qj的結(jié)果是Qi的結(jié)果的結(jié)構(gòu)上的擴(kuò)展;它們的查詢限制條件,即域WHE,均為“IBM”,都是想查詢和“IBM”相關(guān)的信息,可以說它們的查詢意圖有一定的交集。不同的是 Qj還指出想要獲取“Seller”的信息。因此,可猜測Qj的查詢結(jié)果是對Qi的查詢結(jié)果的擴(kuò)充。換言之,查詢表達(dá)式Qj是對查詢表達(dá)式Qi的擴(kuò)展,即{IBM Seller}才是真正能獲得滿足用戶興趣的查詢。因?yàn)槿绻鸔i的結(jié)果是正確的但不能完全滿足查詢需求時,從語義上看,用戶不會改變他的查詢限制,但會加入新的查詢意圖,而從結(jié)構(gòu)上看,Qj的查詢子樹會比Qi的“大”且包含Qi的整個查詢子樹。

另外一個例子,如果Qi是{Tony SellerRating}, Qj是{Seller Tony ItemInfo}。雖然Qj在結(jié)構(gòu)上是對Qi的擴(kuò)充,但顯然它們不是感興趣的查詢結(jié)果擴(kuò)展。因?yàn)樗鼈儾淮嬖谌魏握Z義連續(xù)性。顯然Qi只是對屬性“SellerRating”的值感興趣,而Qj則是對“Seller”為“Tony”所拍賣的物品信息感興趣。通過觀察它們查詢上下文的域WHE便可作出判斷。因此,在這種情況下,Qj不能作為Qi的查詢擴(kuò)展表示式。

定義7(查詢表達(dá)式擴(kuò)展) 對于2個連續(xù)的查詢Qi和Qj,如果Qj是對Qi的查詢表達(dá)式擴(kuò)展,那么必須滿足以下條件:

4.2 查詢表達(dá)式擴(kuò)展決策策略

本文中查詢表達(dá)式擴(kuò)展的目的是為原本的查詢結(jié)果添加更多與查詢意圖相關(guān)的信息,即可等價看作查詢結(jié)果的擴(kuò)展。本文對于每一個查詢表達(dá)式的擴(kuò)展,等同于查詢結(jié)果子樹的擴(kuò)展,同時也可看作是對該實(shí)體信息的擴(kuò)展。

根據(jù)定義7對查詢?nèi)罩具M(jìn)行分析和統(tǒng)計(jì),可以得到每個實(shí)體信息的查詢結(jié)果擴(kuò)展幾率。顯然,每一個查詢結(jié)果的擴(kuò)展操作都會對搜索引擎帶來額外的開銷。眾所周知,用戶不僅要求搜索引擎可以返回相關(guān)的結(jié)果,同時也希望獲得良好的查詢處理時間。所以,對于確定哪些實(shí)體需要被擴(kuò)展這個問題便轉(zhuǎn)換為確定哪些實(shí)體的結(jié)果擴(kuò)展具有較高的收益和較低的代價。

定義8(查詢表達(dá)式擴(kuò)展代價) 對于2個查詢Qi與Qj,及其相應(yīng)的原始結(jié)果i和擴(kuò)展結(jié)果j,從i擴(kuò)展到j(luò)的代價是從i的根節(jié)點(diǎn)出發(fā)到j(luò)同時滿足如下2個條件的節(jié)點(diǎn)的路徑和:

(1)該節(jié)點(diǎn)只存在于j中而不存在于i中;

(2)該節(jié)點(diǎn)出現(xiàn)在Qj的查詢上下文中的域SEL內(nèi)。

仍以圖1所示的XML文檔樹為例,如果Qi為{IBM},Qj為{IBM Seller}。由定義7可知,Qj的結(jié)果是Qi結(jié)果的擴(kuò)展。此外,從定義6可知,域SEL的內(nèi)容反映每個查詢的意圖,而查詢表達(dá)式擴(kuò)展的目的是盡可能給用戶提供所有相關(guān)的信息。因此,如果要對當(dāng)前的查詢表達(dá)式擴(kuò)展只需添加最終結(jié)果中的域SEL中的節(jié)點(diǎn)信息。對Qi的查詢表達(dá)式擴(kuò)展應(yīng)該添加屬性“SellerName”和“SellerRating”。因此,根據(jù)定義8,對Qi查詢表達(dá)式擴(kuò)展代價是從節(jié)點(diǎn)“ItemInfo”到節(jié)點(diǎn)“Tony”和“848”的路徑長度之和,為8。

結(jié)合文獻(xiàn)[13]中的最佳檢索概念和概率排序原則,得到確定是否對結(jié)果(即實(shí)體)進(jìn)行擴(kuò)展的決策策略:

其中,Pi,j表示從初始結(jié)果i到最終結(jié)果j的擴(kuò)展概率;m為初始結(jié)果i有m種不同的最終結(jié)果;Tj表示生成結(jié)果j的代價,這里用該樹中邊的數(shù)目總和表示;Ei,k表示把初始結(jié)果i擴(kuò)充到最終結(jié)果k的擴(kuò)展代價。

由于對用戶查詢意圖猜測是一個概率問題,很難完全確定當(dāng)前結(jié)果是否能完全滿足用戶的查詢意圖,因此該決策策略要求右半部分值小于左半部分值,即要求如果為i進(jìn)行結(jié)果擴(kuò)展,那么該操作帶來的收益應(yīng)該大于該操作本身增加的系統(tǒng)負(fù)載。

5 擴(kuò)展查詢表達(dá)式的上下文信息添加

定義9(候選屬性) 對于XML文檔樹中任意一個屬性節(jié)點(diǎn)a和任意一個實(shí)體節(jié)點(diǎn)e,如果a不在以e為根節(jié)點(diǎn)的子樹里,那么屬性a稱作是實(shí)體e的候選屬性。

對于給定的實(shí)體e,把其所有的候選屬性構(gòu)成的集合稱為候選屬性集。如果要擴(kuò)展當(dāng)前查詢表達(dá)式,那么需要添加的上下文信息必定在該查詢結(jié)果子樹對應(yīng)的實(shí)體的候選屬性集中。顯然,不同的候選屬性其權(quán)重也不同。根據(jù) TF-IDF方法的思想[14],利用XML TF-IDF方法計(jì)算各候選屬性的權(quán)重,計(jì)算方法如下:

在完成了對候選屬性計(jì)算權(quán)重后,接下來是對不同的實(shí)體,確定添加多少候選屬性。本文使用非加權(quán)組平均法(Unweighted Pair Group Averaging Method, UPGMA)[15]為每個實(shí)體的候選屬性集進(jìn)行聚類,聚成2類。然后計(jì)算2個聚類的平均權(quán)值,舍棄最低的那個。剩余的那個聚類中的候選屬性可作為該實(shí)體對應(yīng)的查詢表達(dá)式的擴(kuò)展部分。

6 系統(tǒng)實(shí)現(xiàn)

圖2顯示了基于擴(kuò)展查詢表達(dá)式的系統(tǒng)結(jié)構(gòu),該系統(tǒng)分為在線和離線兩部分。

圖2 基于擴(kuò)展查詢表達(dá)式的系統(tǒng)結(jié)構(gòu)

在線部分的工作具體如下:

(1)當(dāng)用戶提交一個查詢后,系統(tǒng)用XSeek方法生成初步結(jié)果;

(2)當(dāng)前查詢表達(dá)式不需要被擴(kuò)展時,則直接輸出結(jié)果;

(3)當(dāng)前查詢表達(dá)式需要被擴(kuò)展時,系統(tǒng)會從離線生成的索引系統(tǒng)中快速獲取需要添加的信息(即候選屬性值),然后根據(jù)新的查詢表達(dá)式用XSeek輸出結(jié)果;

(4)對于每一個查詢,系統(tǒng)輸出結(jié)果的同時會按照設(shè)定記錄該查詢的相關(guān)內(nèi)容。

離線部分主要工作為:保存XML文檔和查詢?nèi)罩?查詢?nèi)罩窘y(tǒng)計(jì)分析和更新日志等信息。

值索引主要負(fù)責(zé)按照文檔順序存儲和關(guān)鍵字匹配的各個節(jié)點(diǎn)的Dewey編碼,以快速獲得和關(guān)鍵字匹配的節(jié)點(diǎn),該索引類似于倒排索引。

當(dāng)給定一個Dewey編碼時,Dewey索引負(fù)責(zé)提供給系統(tǒng)該節(jié)點(diǎn)的“入口”,包括該節(jié)點(diǎn)的名稱、孩子節(jié)點(diǎn)的數(shù)目、指向孩子節(jié)點(diǎn)和父親節(jié)點(diǎn)的指針以及該節(jié)點(diǎn)的類型(實(shí)體節(jié)點(diǎn)或?qū)傩怨?jié)點(diǎn)或值節(jié)點(diǎn))。因?yàn)橄到y(tǒng)會經(jīng)常遍歷連續(xù)的Dewey編碼,而B+樹的結(jié)構(gòu)能夠改進(jìn)局部地區(qū)數(shù)據(jù)檢索較為集中情況下的效率,所以Dewey索引通過B+樹的形式實(shí)現(xiàn)。

7 實(shí)驗(yàn)結(jié)果與分析

7.1 實(shí)驗(yàn)設(shè)置

實(shí)驗(yàn)運(yùn)行在一臺操作系統(tǒng)是64位Windows 7企業(yè)版的計(jì)算機(jī)上,CPU為Intel i5 2.50 GHz處理器,物理內(nèi)存為8.0 GB。實(shí)驗(yàn)中的XML文檔均來自于文獻(xiàn)[16]:關(guān)于UWM大學(xué)課程信息和關(guān)于eBay在線物品拍賣交易的數(shù)據(jù)。

將本文方法與XSeek和基于語義詞典的查詢擴(kuò)展[5]方法進(jìn)行比較,包括查準(zhǔn)率、查全率和 F度量值[17]。

7.2 查詢質(zhì)量對比

實(shí)驗(yàn)首先用XSeek方法生成系統(tǒng),以用戶一個月內(nèi)用該系統(tǒng)產(chǎn)生的4 982條記錄作為日志進(jìn)行分析統(tǒng)計(jì)工作。

對于評價查詢的效果,最終用戶通常最有發(fā)言權(quán)。因此,邀請5位志愿者參與到實(shí)驗(yàn)評估中。由于XML數(shù)據(jù)查詢結(jié)果信息的主要載體是屬性名稱和其屬性值,因此對于XML關(guān)鍵字查詢,查詢結(jié)果是否能滿足查詢需求就是判斷其感興趣的屬性是否出現(xiàn)在結(jié)果中。為了引導(dǎo)他們?yōu)槊總€查詢結(jié)果定義一個可用于評估的基準(zhǔn),該5位用戶獲悉了2個數(shù)據(jù)集所有的屬性名稱和其相關(guān)的語義。除此之外,他們并不知曉DTD和屬性層次分布等信息,從而保證實(shí)驗(yàn)的真實(shí)性與可靠性。這些用戶為每個數(shù)據(jù)集提供了5個查詢測試用例,如表1所示。限于篇幅,表2、表3顯示了部分查詢測試用例使用本文方法后擴(kuò)展的查詢表達(dá)式以及用戶給出的查詢意圖。

表1 查詢測試用例

表2 原始查詢與擴(kuò)展查詢

表3 QA1和QA4查詢

7.2.1 查準(zhǔn)率與查全率

查準(zhǔn)率與查全率的計(jì)算方法如式(3)和式(4)所示:

表4顯示了查準(zhǔn)率實(shí)驗(yàn)數(shù)據(jù)。對于QA1,本文方法的查準(zhǔn)率遠(yuǎn)低于XSeek方法,可以發(fā)現(xiàn)原因是QA1想查找滿足條件 SellerName為 wenaxion的SellerRating屬性值,可猜測該用戶只對該屬性內(nèi)容感興趣。在這種情況下,對實(shí)體SellerInfo的擴(kuò)展是多余的,因此,導(dǎo)致了本文方法對于QA2查準(zhǔn)率數(shù)值偏低。而對于和QA1相似的查詢QA2,可判斷QA2的查詢意圖是尋找售賣Sony電腦的賣家Mary的相關(guān)信息。對于QA2,本文查詢擴(kuò)展添加的屬性多數(shù)都是和查詢相關(guān)的,所以本文方法對于QA2的查準(zhǔn)率比QA1高的多。從表4可知,在多數(shù)情況下本文方法的查準(zhǔn)率與XSeek、基于語義詞典的查詢擴(kuò)展方法較接近。

表4 查準(zhǔn)率結(jié)果對比

表5顯示了查全率實(shí)驗(yàn)數(shù)據(jù)。對于QA2,XSeek方法產(chǎn)生的結(jié)果僅限于LCA子樹。由上文分析可知,該查詢意圖顯然不止該子樹,而本文方法的查全率數(shù)據(jù)明顯較優(yōu)。從表5可以發(fā)現(xiàn),本文方法在查全率方面優(yōu)于XSeek和基于語義詞典的查詢擴(kuò)展方法,說明了本文方法對于改進(jìn)查詢質(zhì)量的有效性。

表5 查全率結(jié)果對比

7.2.2 F度量值

為同時考慮查全率和查準(zhǔn)率,使用F度量值作為查詢質(zhì)量評價的標(biāo)準(zhǔn),計(jì)算方法如下所示:

其中,a用于衡量兩者的權(quán)重。如果a=1則認(rèn)為兩者同樣重要;如果a=0.5,則認(rèn)為查準(zhǔn)率更重要;如果a=2,則認(rèn)為查全率更加重要。本文認(rèn)為兩者同樣重要,因此a=1。

表6顯示了F度量值實(shí)驗(yàn)數(shù)據(jù)。基于語義詞典的查詢擴(kuò)展方法由于其擴(kuò)展詞來源過度依賴知識庫,而忽略了用戶查詢用詞與XML文檔間的語義聯(lián)系,因此其查準(zhǔn)率、查全率和F度量值均未優(yōu)于本文方法。綜合衡量所有查詢測試用例的查全率和查準(zhǔn)率實(shí)驗(yàn)數(shù)據(jù),可以發(fā)現(xiàn),本文方法在多數(shù)情況下都要優(yōu)于XSeek方法,由此證明本文方法的有效性。

表6 F度量值結(jié)果對比

8 結(jié)束語

本文重點(diǎn)研究了如何通過查詢表達(dá)式擴(kuò)展的方法改進(jìn)XML關(guān)鍵字查詢技術(shù)。通過擴(kuò)展查詢表達(dá)以及添加查詢表達(dá)式的上下文信息,實(shí)現(xiàn)本文方法,并對查詢?nèi)罩具M(jìn)行數(shù)據(jù)挖掘,減少了表達(dá)式擴(kuò)展方法對知識庫或初檢結(jié)果的依賴。實(shí)驗(yàn)結(jié)果表明,本文方法對查詢質(zhì)量,尤其是查全率和F度量值,起到了一定的優(yōu)化作用。今后將考慮如何更加準(zhǔn)確地判斷查詢意圖和解決LCA查詢語義二重性問題,使本文方法具有更好的普適性。

[1] Vagelis H,Nick K,Yannis P,et al.Keyword Proximity Search inXML Tree[J].IEEE Transactionson Knowledge and DataEngineering,2006,18(4): 525-539.

[2] Xu Yu,Papakonstantinou Y.Efficient Keyword Search for Smallest LCAs in XML Databases[C]//Proceedings of 2005 ACM InternationalConferenceonSpecial Interest Group on Management of Data.New York, USA:ACM Press,2005:529-538.

[3] Liu Zhiyang,ChenYi.IdentifyingMeaningfulReturn Information for XML Keyword Search[C]//Proceedings of 2007 ACM International Conference on Special Interest Group on Management of Data.New York,USA:ACM Press,2007:329-340.

[4] Snasel V,Moravec P,Pokorny J.WordNet Ontology Based Model for Web Retrieval[C]//Proceedings of 2005 International Workshop on Challenges in Web Information Retrieval and Integration.[S.l.]:IEEE Computer Society,2005:220-225.

[5] 王水利,黃廣君,霍亞格.基于語義分析的查詢擴(kuò)展方法[J].計(jì)算機(jī)工程,2011,37(16):77-79.

[6] Cui Han,Wen Jirong,Nie Jianyun,et al.Probabilistic Query Expansion Using Query Logs[C]//Proceedings of the 11th International Conference on World Wide Web.New York,USA:ACM Press,2002:325-332.

[7] Chirita P A,Firan C S,Nejdl W.Personalized Query Expansion for the Web[C]//Proceedings of the 30th International Conference on ACM Special Interest Group on Information Retrieval.New York,USA:ACM Press, 2007:7-14.

[8] Xu J,Croft W.Improving the Effectiveness of Information Retrieval with Local Context Analysis[J]. ACM Transactions on Information Systems,2000,18 (1):79-112.

[9] Ricardo Y B,Berthier N R.Modern Information Retrieval[M].[S.l.]:Pearson Education Limited, 1999:16-65.

[10] Qiu Yonggang,Frei H.Concept Based Query Expansion [C]//Proceedings of the 16th International Conference on ACM SpecialInterestGroup on Information Retrieval.New York,USA:ACM Press,1993:160-169.

[11] Liu Ziyang,NatarajanS,ChenY.QueryExpansion Based on Clustered Results[J].Proceedings of the VLDB Endowment,2011,4(6):350-361.

[12] Bao Zhifeng,Ling T W,Chen Bo,et al.Effective XML Keyword Search with RelevanceOriented Ranking [C]//Proceedings of 2009 IEEE International Conference on Data Engineering.Washington D.C., USA:IEEE Computer Society,2009:517-528.

[13] Chauduri S,Das G,Hristidis V,et al.Probabilistic Ranking of Database Query Results[C]//Proceedings of the 30th International Conference on Very Large Data Bases.[S.l.]:ACM Press,2004:888-899.

[14] Paik J H.A NovelTF-IDF WeightingSchemafor Effective Ranking[C]//Proceedings of the 36th International Conference on ACM Special Interest Group on Information Retrieval.New York,USA:ACM Press, 2013:343-352.

[15] Helmer S.Measuring the Structural Similarity of Semistructured Documents Using Entropy[J].The VLDB Journal,2012,21(5):1022-1032.

[16] UW XML Data Repository[EB/OL].(2012-05-17). http://www.cs.washington.edu/research/xmldatasets.

[17] Croft B,Metzler D.Search Engines:Information Retrieval in Practice[M].[S.l.]:Addison-Wesley,2009:286-287.

編輯 陸燕菲

XML Keyword Search Based on Extended Query Expression

ZHU Jing-hua,WANG Xiao-ling
(School of Computer Science,Fudan University,Shanghai 200433,China)

Most existing eXtensible Markup Language(XML)keyword searches are based on Lowest Common Ancestor(LCA)semantics tree to generate search result,but they do not consider the data which is not included in LCA semantics tree while is relevant with user search intention.To solve this problem,an XML keyword query method based on extended query expression is proposed.The query expansion statistical model is based on user query log.Through analyzing query log and combined with optimal retrieval concept,it can judge whether the query expression should be expanded.After that,an XML TF-IDF method is employed to calculate the weight of candidate attribute.According to the context information and using cluster method,it gets the query expression keywords which are most relevant with search intention.Then the expanded query expression is generated.Compared with XSeek and semantics dictionary based query expression method,experimental result shows this method can improve the query quality by average 7%and 17%in F-measure respectively.

information retrieval;eXtensive Markup Language(XML);Lowest Common Ancestor(LCA)semantic; keyword search;query expansion;context information

1000-3428(2014)10-0025-07

A

TP391

10.3969/j.issn.1000-3428.2014.10.006

國家自然科學(xué)基金資助項(xiàng)目(60773075)。

朱菁華(1985-),男,碩士研究生,主研方向:XML信息檢索,數(shù)據(jù)庫技術(shù);王曉玲,教授、博士。

2013-11-05

2013-11-27E-mail:jh_zhu@fudan.edu.cn

中文引用格式:朱菁華,王曉玲.基于擴(kuò)展查詢表達(dá)式的XML關(guān)鍵字查詢[J].計(jì)算機(jī)工程,2014,40(10):25-31.

英文引用格式:Zhu Jinghua,Wang Xiaoling.XML Keyword Search Based on Extended Query Expression[J]. Computer Engineering,2014,40(10):25-31.