面向檢索服務(wù)的詞干提取與相關(guān)排序優(yōu)化研究

朱 艷, 張敬偉, 楊 青, 胡曉麗, 單美靜

(1.桂林電子科技大學(xué) 廣西可信軟件重點實驗室,廣西 桂林 541004;2.桂林電子科技大學(xué) 廣西自動檢測技術(shù)與儀器重點實驗室,廣西 桂林 541004;3.華東政法大學(xué) 刑事法學(xué)院,上海 201620)

云計算、大數(shù)據(jù)等新技術(shù)的興起,以及電子商務(wù)、網(wǎng)絡(luò)自媒體、娛樂通訊等互聯(lián)網(wǎng)產(chǎn)業(yè)的蓬勃發(fā)展使得信息量呈現(xiàn)指數(shù)級增長。據(jù)統(tǒng)計[1],全球每年產(chǎn)生的數(shù)據(jù)量高達1～2 EB,其中非紙質(zhì)信息就占了99.7%。盡管大數(shù)據(jù)技術(shù)、深度學(xué)習(xí)以及神經(jīng)網(wǎng)絡(luò)計算能力的進步加速了信息處理能力的提升,但對信息過載問題的緩解仍舊微乎其微。在關(guān)注度有限的情況下,如何短時間內(nèi)從指數(shù)級增長的數(shù)據(jù)中獲取有效信息成為了亟待解決的問題,而搜索引擎則是人們提取信息的有效方式之一。

隨著互聯(lián)網(wǎng)行業(yè)的快速發(fā)展,搜索用戶的信息需求日益復(fù)雜,同時檢索詞也逐漸變得多樣化,一個詞常有多種不同形態(tài),這些都對語料庫學(xué)習(xí)的準(zhǔn)確度產(chǎn)生一定影響。研究表明[2],若檢索詞未進行詞形規(guī)范化,可能會造成重要的檢索結(jié)果缺失或存在過多無關(guān)的文檔出現(xiàn)在檢索結(jié)果列表的情況,而若檢索詞為主題詞表中的詞語,則能有效提高檢索結(jié)果的準(zhǔn)確率與查全率。因此,在信息檢索與文本挖掘研究中,需要對單詞進行歸一化處理,以提高文本處理的效率,其中詞干提取是詞形歸一化的核心技術(shù)之一。然而現(xiàn)有的詞干提取算法普遍存在詞干提取不足、詞干提取準(zhǔn)確率不高等問題,無法有效改善龐大的文本詞匯量與關(guān)鍵詞特征缺失的矛盾問題,導(dǎo)致搜索引擎的時空復(fù)雜度偏高而查詢效率偏低。為解決文本查詢處理面臨的“高維-稀疏”問題,通過優(yōu)化詞干分析算法對文本向量空間進行降維處理,以減少詞項的數(shù)量,從而提高文本處理效率。

此外,為了減少系統(tǒng)在相關(guān)排序過程中的時間及硬件資源消耗,查詢優(yōu)化技術(shù)逐漸受到學(xué)術(shù)界及工業(yè)界的重視。其中,top-k查詢排序是信息檢索領(lǐng)域廣泛應(yīng)用的查詢處理優(yōu)化技術(shù)之一。相關(guān)文檔top-k排序基于查詢-文檔的相似度得分,以及具體的得分聚合函數(shù)從海量文本數(shù)據(jù)中返回k個最大的得分排名結(jié)果?，F(xiàn)有的top-k排序研究大多是確定了整體的top-k結(jié)果后,才會停止排序過程。盡管這種方式通過詳盡遍歷所有文檔和詞項能夠保證檢索質(zhì)量,但同時對海量文檔的處理也產(chǎn)生了不可忽視的查詢延遲。研究表明[3-4],響應(yīng)時間過長直接影響用戶體驗,造成潛在利益的巨大損失。目前對于查詢延遲的處理,大多通過將文檔集合劃分到若干服務(wù)器來管理,但這種方式仍存在尾延遲[5-11]的問題。對于大規(guī)模分布式系統(tǒng)來說,尾延遲現(xiàn)象更加普遍,甚至?xí)?yán)重影響服務(wù)的整體性能。而隨時排序算法能夠在給定時間預(yù)算內(nèi)或給定倒排段處理數(shù)量下,隨時停止檢索過程,從而控制查詢延遲。因此,當(dāng)存在一定查詢負載時,利用隨時排序算法能夠大大降低整個系統(tǒng)的資源損耗及維護成本,解決普遍存在的高百分比尾延遲問題[12],以適應(yīng)服務(wù)水平協(xié)議對響應(yīng)時間的要求。

基于對上述問題的思考,在文本預(yù)處理與相關(guān)排序2個方面進行了深入研究:

首先,在文本預(yù)處理階段,設(shè)計了詞形規(guī)范化算法(advanced porter stemmer,簡稱APS),解決了現(xiàn)有算法存在的詞干提取不足、詞干提取準(zhǔn)確率高等問題。該算法基于屈折派生形態(tài)學(xué)調(diào)整了規(guī)則函數(shù)的定義,優(yōu)化了特征詞提取,并且補充了不規(guī)則動詞以及若干后綴的處理,同時添加了對停用詞過濾的支持。針對APS算法的評價,在3個真實的數(shù)據(jù)集上開展實驗,驗證了APS優(yōu)化算法對于解決詞干不足問題的有效性以及提高詞干提取準(zhǔn)確率的真實性。

其次,在相關(guān)排序階段,設(shè)計了基于一次一得分(score-at-a-time,簡稱SAAT)查詢處理策略的隨時排序算法(SAAT-anytime ranking,簡稱SAR)。該算法能夠在處理完指定數(shù)量的倒排段后或給定時間預(yù)算內(nèi)提前終止查詢過程,大大減少了查詢評估延遲時間,在犧牲可接受范圍內(nèi)檢索質(zhì)量的情況下,能夠返回較為準(zhǔn)確的檢索結(jié)果,解決了現(xiàn)有方法普遍存在的尾延遲問題。在2個真實的大型TREC標(biāo)準(zhǔn)數(shù)據(jù)集ClueWeb09b和ClueWeb12-B13上進行了實驗,通過檢索質(zhì)量評價指標(biāo)nDCG@10對SAR 算法進行了評估,并記錄了在給定時間預(yù)算下的查詢延遲、減少的倒排段處理數(shù)量,驗證了SAR算法對于控制尾部延遲時間的有效性。

1 相關(guān)工作

近年來,搜索引擎的優(yōu)化問題已被廣泛研究。在互聯(lián)網(wǎng)信息量以指數(shù)級增長,信息過載問題愈發(fā)嚴(yán)峻的時代背景下,如何盡快找到滿足用戶需求的文檔內(nèi)容,提高信息檢索的效率日益成為研究者關(guān)注的焦點問題,這也為科學(xué)研究提供了動力。本節(jié)將主要圍繞詞干提取與相關(guān)查詢2個方面對以往工作進行總結(jié)概括。

1.1 詞干提取

根據(jù)詞干提取方法的實現(xiàn)原理,可以將其歸為4類:基于規(guī)則的詞綴刪除方法[13-17]、基于詞典查找的方法[18]、基于單詞分布規(guī)律的統(tǒng)計方法[19-21]以及混合方法[22-24]?；谠~典查找的方法在權(quán)威詞典的支持下,結(jié)果更加準(zhǔn)確,能夠處理部分不規(guī)則變換詞,但遍歷詞典查找費時且對詞典具有依賴性?；诮y(tǒng)計的方法主要是針對詞典中未收錄的詞以及不規(guī)則變化詞,通過統(tǒng)計單詞規(guī)律對單詞進行規(guī)范化,因此不受語種限制,但識別出的詞干誤差較大,且準(zhǔn)確率不穩(wěn)定。二者更適用于對小語種單詞的詞干提取。而混合型方法雖然融合了多種方法的優(yōu)勢,詞干提取的準(zhǔn)確率更高,但算法流程復(fù)雜,需要考慮的因素過多,且需要多種背景知識的支持,因此限制較大,效率較低。而基于規(guī)則的詞綴刪除方法能夠快速處理常規(guī)詞的變換,適用范圍更廣。因此,主要針對基于規(guī)則的詞綴刪除方法進行改進優(yōu)化。

基于規(guī)則的詞綴刪除方法利用單詞屈折派生形態(tài)中具備的內(nèi)在規(guī)律,對單詞中的詞綴進行處理。1968年,Lovins[13]提出了有效的同名詞干提取Lovins算法,該算法基于最長匹配原則對照詞綴列表去除單詞后綴后,匹配規(guī)則列表中的轉(zhuǎn)換規(guī)則,重新對單詞進行編碼,將詞干轉(zhuǎn)換為有效單詞,最終提取出詞干。其優(yōu)點是規(guī)則簡單,且能夠處理某些疊詞結(jié)尾的單詞以及不規(guī)則單詞復(fù)數(shù);但缺點是非常耗時,且詞干提取的準(zhǔn)確率不高。針對Lovins算法的規(guī)則和匹配方法存在的不足,Dawson[14]提出了同名方法Dawson算法。該算法基于部分匹配的思想,在限制條件下匹配相同詞干,擴展了Lovins算法,并解決了拼寫異常問題。Dawson算法是單程非迭代算法,因此執(zhí)行速度快,但該算法的缺點是復(fù)雜,且缺乏標(biāo)準(zhǔn)的可重用實現(xiàn)。Lancaster(Paice/Husk)[15]算法是一種迭代算法,通過判斷是否需要再次提取詞干循環(huán)執(zhí)行匹配流程。該算法通過將單詞最后一個字符作為索引尋找適用規(guī)則,每條規(guī)則決定是否對后綴進行刪除或替換,若規(guī)則不匹配或滿足詞干提取結(jié)束條件,則終止流程,輸出詞干。Lancaster算法的優(yōu)點是,每次迭代都會應(yīng)用規(guī)則進行刪除和替換,降低了詞干提取不足的概率;但缺點是算法繁雜,可能會出現(xiàn)詞干過度提取的情況。Porter Stemmer(波特詞干)[16-17]算法自提出以來便廣受歡迎,現(xiàn)已廣泛應(yīng)用于信息檢索領(lǐng)域以及多種檢索系統(tǒng)中,如Lucene、Solr等。波特詞干算法對許多基本算法進行了改進和優(yōu)化,主要用于對英文單詞中通用形態(tài)以及屈折詞綴進行剔除。盡管該算法在多種算法基礎(chǔ)上做出了改進,但缺乏對不規(guī)則動詞、不規(guī)則名詞復(fù)數(shù)以及多種詞綴的考慮,因此仍存在詞干提取不足以及詞干提取準(zhǔn)確率不高等問題,需進一步優(yōu)化。

1.2 相關(guān)排序

將文檔數(shù)據(jù)與查詢信息進行預(yù)處理后,需要對文檔和查詢的相關(guān)度進行計算,進而根據(jù)得分高低對相關(guān)文檔進行排序,最后返回給用戶得分top-k的文檔結(jié)果,這個排序的過程稱為相關(guān)排序。目前搜索引擎的排序策略往往建立在所有文檔的相關(guān)度得分上,然而窮盡處理所有候選結(jié)果所花費的時間和資源開銷過大。在當(dāng)下互聯(lián)網(wǎng)的數(shù)據(jù)規(guī)模以指數(shù)級增長的背景下,為了提升查詢性能,相關(guān)優(yōu)化技術(shù)不斷推陳出新。目前主流的查詢效率優(yōu)化技術(shù)包括剪枝算法、選擇搜索以及隨時排序算法等。

動態(tài)剪枝算法以處理盡可能少的相關(guān)文檔為目標(biāo),采用跳躍式訪問倒排列表的方式來減少對無關(guān)或相關(guān)度較低的文檔的處理,避免對所有文檔的遍歷和訪問,從而提高查詢效率。動態(tài)剪枝算法能夠保證top-k個文檔列表的計算是安全的,也就是說使用動態(tài)剪枝算法與窮盡查詢方法得到的查詢結(jié)果相同。常用的動態(tài)剪枝算法有MaxScore[25]、WAND[26]、BMW[27-28]以及VBMW[29]等。但有研究表明[30],剪枝算法執(zhí)行尾部查詢所花費的時間比平均查詢延遲時間要多若干數(shù)量級。

選擇搜索在搜索構(gòu)建時,將文檔集合按照主題劃分,理想情況下每個分片都包含一組主題相關(guān)的文檔[31-32]。傳入的每個用戶查詢都由代理流程預(yù)測被劃分的集合分片,然后由劃分的分片處理查詢,最后將分片結(jié)果匯總。每個分片的處理過程都能應(yīng)用動態(tài)剪枝算法。該方法的優(yōu)點是,能夠有效減少工作負載,查詢效率高; 但缺點是,由于只有部分分片對查詢進行處理,算法得到的結(jié)果可能會與窮盡查詢算法得到的結(jié)果有所偏差。

隨時排序算法實現(xiàn)基于影響力排序的索引(impact-ordered index)。相對于一次一文檔(term-at-atime)查詢處理策略,SAAT 查詢策略能夠根據(jù)影響力得分來處理文檔的優(yōu)先級[32-33],可在避免遍歷所有文檔的情況下,輸出較為準(zhǔn)確的排序結(jié)果,更有利于提前終止文檔相關(guān)度計算流程,這與隨時排序的目標(biāo)相同,因此隨時排序算法大都基于SAAT 策略。當(dāng)響應(yīng)時間預(yù)先由服務(wù)水平協(xié)議確定時,查詢處理過程必須支持可中斷,隨時排序算法針對此類情況給出了解決方案。隨時排序算法在給定時間預(yù)算內(nèi)返回盡可能準(zhǔn)確的結(jié)果,且檢索結(jié)果質(zhì)量隨著預(yù)算時間的延長而成正比提升[34-35]?；谝陨侠碚?在相關(guān)排序階段通過設(shè)計基于SAAT策略的隨時排序算法來控制查詢延遲時間。

2 基于改進Porter Stemmer的APS算法

針對Porter Stemmer存在的詞干提取不足以及詞干提取準(zhǔn)確率不高等問題,對波特詞干算法進行改進,設(shè)計了APS算法。該算法重新編碼了規(guī)則函數(shù),優(yōu)化了特征詞提取,并補充了不規(guī)則動詞以及若干后綴的處理,同時添加了對停用詞過濾的支持。

為使算法描述更清晰,首先對以下定義進行說明:

定義1 元音(Vowel)。a,e,i,o,u五個字母。

定義2 輔音(Consonant)。除元音外的其他字母。

定義3 給定單詞T,以詞綴S1結(jié)尾,若詞干滿足指定條件condition,則由新詞綴S2代替S1,即:(condition)S1→S2。 (1)

定義4 屈折形態(tài)(Inflexion)。單詞或詞根受語法影響,加上屈折詞綴后的形態(tài),包括單詞復(fù)數(shù)形式如“apples”等、不同時態(tài)形式如“l(fā)ooked”等、以及分詞形式如“walking”等。

定義5 派生形態(tài)(Morphological Derivation)。單詞或詞根在句法范疇基礎(chǔ)上,添加實質(zhì)性的詞綴后所派生的形態(tài),如illegal,irregular等。

定義6 疊字(Double)。由單個字母重疊而成的詞綴,如tt、mm、nn等。

定義7 復(fù)合詞綴(Double Suffix)。由多個詞綴整合而成的形態(tài),如由general附加ize后綴和ation后綴整合得到generalization,其中g(shù)eneralization的詞綴為復(fù)合詞綴。

APS算法基于英文單詞形態(tài)特征及屈折派生形態(tài)學(xué),針對波特詞干算法存在的不足,做以下優(yōu)化:

1)對不規(guī)則動詞變位與復(fù)數(shù)的特例進行補充。波特詞干算法忽略了2種不規(guī)則詞形式的處理:①不符合任何特征規(guī)則的動詞,例如單詞“buy”及其過去式“bought”。對于此類情況,通過枚舉不規(guī)則動詞形式進行改善;②符合一般規(guī)則特征的單詞,例如以-foot結(jié)尾的單詞復(fù)數(shù)形式以-feet結(jié)尾。對于此類情況,通過添加對規(guī)則的補充可以得到改善。表1為波特詞干算法與APS算法處理前后的對照示例1。

表1 波特詞干算法與APS算法處理對照示例1

2)對以-s結(jié)尾的動詞及其分詞形式的處理進行優(yōu)化。波特詞干算法對于以-s結(jié)尾的動詞分詞形式的處理方式是直接去除末尾的-ed或-ing,保留末尾的-s。在該規(guī)則下,對于“focus”與其復(fù)數(shù)“focuses”,存在將“focuses”轉(zhuǎn)化為詞干“focus”,而將“focus”轉(zhuǎn)化為“focu”的錯例。針對此類情況,通過優(yōu)化規(guī)則可以改善:若以-s結(jié)尾,但不以ss結(jié)尾的單詞,一律轉(zhuǎn)化為s。表2為波特詞干算法與APS算法處理前后的對照示例2。

表2 波特詞干算法與APS算法處理對照示例2

3)對以-y結(jié)尾單詞的詞干合并方式進行優(yōu)化。波特詞干算法對于以-y結(jié)尾的單詞的處理方式是:若包含元音,則將-y轉(zhuǎn)變?yōu)?i;另外,針對以-ies結(jié)尾的單詞處理方式是:將ies轉(zhuǎn)變?yōu)閕。這種規(guī)則能正確處理包含元音的單詞,例如carry→carries,marry→marries等。但對于不包含元音的詞干則不適用,例如cry-cries-cried,則會被轉(zhuǎn)化為cry-cri-cri-cry。

同理,以-ye結(jié)尾的單詞也不適用,因為末尾的e最終會去除。針對此類情況,通過優(yōu)化規(guī)則:首先將分詞后綴-es/-ed/-ing去除,然后刪除規(guī)則“若包含元音,則將末尾的y轉(zhuǎn)變?yōu)閕”,即保持末尾的-y不變。表3為波特詞干算法與APS算法處理前后的對照示例3。

表3 波特詞干算法與APS算法處理對照示例3

4)對以雙輔音結(jié)尾的單詞及其衍生詞的處理進行優(yōu)化。波特詞干算法對于以非‘l’、‘s’或‘z’雙輔音結(jié)尾單詞的分詞形式處理方式是:去除一個輔音,保留一個輔音。在這種規(guī)則下,會出現(xiàn)錯將單詞“ebbed”轉(zhuǎn)換為“eb”,而“ebb”轉(zhuǎn)換為“eb”的錯誤案例。另外,若存在以-z結(jié)尾的單詞,但其分詞加了疊詞詞綴即-zz,例如單詞“whiz”的過去分詞“whizz”,“whiz”本身會轉(zhuǎn)化為“whiz”,而過去分詞“whizz”則轉(zhuǎn)化為“whiz”,誤判情況出現(xiàn)。針對以上情況,可優(yōu)化規(guī)則:刪除所有以除-l雙輔音結(jié)尾單詞的輔音字母,對于以雙輔音-ll結(jié)尾的單詞,若m＞1,則刪除一個輔音。表4為波特詞干算法與APS算法處理前后的對照示例4。

表4 波特詞干算法與APS算法處理對照示例4

5)對部分現(xiàn)在分詞以及過去分詞衍生詞的處理進行優(yōu)化;波特詞干算法忽略了對現(xiàn)在分詞、過去分詞衍生詞的處理,例如“study”轉(zhuǎn)化為 “studi”,而“studiedly”卻轉(zhuǎn)化為“studiedli”。對于該類情況的處理,APS補充了對該類詞的轉(zhuǎn)化規(guī)則。表5為波特詞干算法與APS算法處理對照示例5。

表5 波特詞干算法與APS算法處理對照示例5

6)補充了若干后綴的處理。針對波特詞干算法忽略-tor、-sory、-ship等若干詞綴,APS算法進行了補充。另外對于單詞的復(fù)合后綴的漏判問題,通過由后綴枚舉所有可能的復(fù)合后綴進行優(yōu)化。例如,由詞綴-ate衍生出的-ative、-atic等詞綴都將被對應(yīng)到詞綴-ate。表6為部分詞綴轉(zhuǎn)換示例。

表6 APS算法詞綴轉(zhuǎn)換示例

APS 算法進行詞干提取的整體流程如圖1所示。由圖1可知,APS算法對詞干的提取主要包括5個步驟:第一步,處理單詞的屈折形態(tài),包括單詞的復(fù)數(shù)、現(xiàn)在分詞、過去分詞等,例如將“apples”轉(zhuǎn)換為“apple”,將“l(fā)ooked”轉(zhuǎn)換為“l(fā)ook”;第二步,根據(jù)前文描述的優(yōu)化工作對y→i的規(guī)則進行重編碼,例如將“try”轉(zhuǎn)換為“tri”;第三步,對整合多個詞綴的復(fù)合詞綴進行處理,將這類詞綴轉(zhuǎn)化為非復(fù)合后綴,例如將“generalization”轉(zhuǎn)換為“generalize”。本算法對復(fù)合詞綴到非復(fù)合后綴的映射規(guī)則進行了重編碼;第四步,刪除簡單的非復(fù)合后綴,通過定義的編碼規(guī)則對現(xiàn)存詞干進行歸一化,例如將上一步得到的“generalize”轉(zhuǎn)換為“general”。這兩步主要對單詞的派生形態(tài)進行處理。第五步,處理不滿足以上編碼規(guī)則的不規(guī)則詞,通過與補充的規(guī)則轉(zhuǎn)化表單詞進行遍歷匹配來完成對不規(guī)則詞的詞干提取;最后,在處理完不規(guī)則詞的基礎(chǔ)上,根據(jù)重編碼后的新規(guī)則去除單詞末尾的-e或-l,最終得到詞干。

圖1 APS算法流程

3 基于SAAT策略的隨時排序算法SAR

搜索引擎在海量數(shù)據(jù)中檢索到滿足用戶查詢要求的文檔是一項非常耗時的任務(wù)。研究表明[36],在谷歌搜索中人為對查詢時間延長100～400 ms,用戶每天的搜索次數(shù)減少0.2%～0.6%?，F(xiàn)有的處理查詢延遲的方法往往是將文檔劃分到多個服務(wù)器,每個服務(wù)器分擔(dān)部分時間延遲,但查詢的延遲時間仍不可忽視?；趯μ嵘脩趔w驗的考慮,分析發(fā)現(xiàn),通過犧牲可接受范圍的搜索質(zhì)量能夠在任意給定時間限制的情況下,向用戶查詢返回較為準(zhǔn)確的文檔排名,并且隨著計算時間的延長,結(jié)果質(zhì)量成正比增長。在此基礎(chǔ)上,基于SAAT 查詢處理策略設(shè)計了隨時排序算法SAR。該算法能夠在處理完指定數(shù)量的倒排項后或給定時間內(nèi)提前終止查詢過程,大大減少查詢評估延遲時間。

在SAR算法實現(xiàn)的基于影響力排序索引中,文檔標(biāo)識符按照每個詞對于文檔的實際貢獻得分分段,每段以文檔標(biāo)識符升序排列,而段按照影響力分?jǐn)?shù)降序進行排列,最終將影響力分?jǐn)?shù)的top-k結(jié)果返回。

3.1 影響力分?jǐn)?shù)與詞項權(quán)重量化

其中:ω(d,t)為詞項t對于文檔d的權(quán)重,在索引建立過程中被量化到b字節(jié)中,在SAR算法中設(shè)置為8;ω(q,t)為詞項t對于查詢詞q的權(quán)重。

對于詞項的量化標(biāo)準(zhǔn),SAR 算法采用了由Anh等[37]提出的量化方法:

3.2 索引的組織方式

索引的組織方式如下,單詞字典中的每個查詢詞項指向倒排列表,倒排列表中的倒排項由類似{score,start,end,num}的四元組組成,稱之為段(segment)。其中段的第一項score代表影響力分?jǐn)?shù),第二項start代表指向段數(shù)據(jù)首部的指針,第三項end代表指向段數(shù)據(jù)尾部的指針,包含在段數(shù)據(jù)中的文檔數(shù)量則由變量num 存儲。每個詞項的段都按照以段中存儲的score值降序、文檔標(biāo)識符升序排列。

3.3 SAAT評估策略

基于以上影響力分?jǐn)?shù)計算以及索引組織方式,應(yīng)用查詢評估策略SAAT。在SAAT查詢處理機制的剪枝方法中,定義了4種查詢處理模式:

定義9 OR模式。在該模式下,所有文檔都將分配分?jǐn)?shù)累加器,且都會進行得分統(tǒng)計。

定義10 AND模式。若轉(zhuǎn)換為該模式,則出現(xiàn)的新文檔不再被分配分?jǐn)?shù)累加器,只針對已被分配累加器的文檔進行分?jǐn)?shù)累計操作。

定義11 REFINE 模式。該模式應(yīng)用的前提是,top-k的文檔已經(jīng)確定,但最終順序還未確定。此時,得分累加只針對top-k的文檔。

定義12 IGNORE模式。在該模式下,停止對所有文檔的得分進行遞加,查詢處理過程終止。

首先獲取與查詢詞項相關(guān)的倒排列表段,然后根據(jù)段中存儲的score值進行降序排列,并按照此順序?qū)Χ芜M行處理。對于段中的每個文檔標(biāo)識符,其影響力分?jǐn)?shù)值由文檔對應(yīng)的累加器存儲,而在處理過程中累加器中的值通過維護一個堆來實時獲取top-k的結(jié)果。每當(dāng)將當(dāng)前影響力分?jǐn)?shù)值添加到累加器時,通過與堆頂值進行判斷可決定是否將指向累加器的指針添加到堆中。

由于實時地維護了影響力值最大的top-k個文檔結(jié)果,因此能夠在任意給定時間或給定處理倒排列表項的數(shù)量終止算法,返回給用戶檢索結(jié)果。另外,段會按照優(yōu)先度依次遞減的順序處理,優(yōu)先度由詞項的分?jǐn)?shù)貢獻值決定,因此排名情況會隨著查詢進展逐步細化。若查詢時間預(yù)算增加,則輸出結(jié)果的質(zhì)量也成正比提升。

3.4 提前終止閾值參數(shù)η

在處理段的過程中,SAR 算法維護已處理文檔影響力得分的累加值。在下一個段處理之前,首先與η進行比較,若大于η值,則跳出循環(huán),然后從堆中獲取top-k的結(jié)果;若小于η值,則流程繼續(xù)。

基于以上原理介紹,SAR 算法的核心代碼如算法1所示。

SAR算法核心代碼如算法1所示。步驟1使用OR模式對各個查詢詞項對應(yīng)倒排表中分?jǐn)?shù)高的段進行處理;步驟2～11,計算每個詞項t對應(yīng)倒排表中未處理塊的最大分?jǐn)?shù),即npbt。當(dāng)文檔得分大于npbt時,將OR 模式改用AND 模式;步驟12～13,若文檔得分大于所有文檔的最大得分,即滿足條件Score≥max{MAXd|d∈AC,D?R}時,將模式改用REFINE模型進行處理。其中,AC為現(xiàn)有累加器集合,保存文檔號及文檔的部分得分,Md為文檔d的最大得分,由AC保存的分?jǐn)?shù)累加得到,即MAXd=ACd+∑{npbd|t∈q,t?Td};步驟14～15,若滿足現(xiàn)有累加器集合中的累加分?jǐn)?shù)大于文檔d的最大分?jǐn)?shù),則此時查詢可以提前終止,采用IGNORE模式。最終得到累加器中得分最高的top-k個文檔。

4 實驗評估

對APS算法和SAR算法分別進行評估。

針對APS算法,使用誤差計數(shù)法對APS算法以及優(yōu)化前的波特詞干算法進行評估,利用該方法通過計算詞干提取不足指數(shù)(understemming index,簡稱UI)、詞干提取過度指數(shù)(overstemming index, 簡稱OI)以及相對截斷錯誤率(error rate relative to truncation,簡稱ERRT)3個指標(biāo)對APS算法的詞干提取準(zhǔn)確率進行評價,最后在2個數(shù)據(jù)樣本上進行實驗驗證,并與現(xiàn)有詞干算法進行對比。

針對SAR算法,在2個真實的大型TREC標(biāo)準(zhǔn)數(shù)據(jù)集上進行實驗驗證,通過檢索質(zhì)量評價指標(biāo)nDCG@10對SAR 算法進行評估,并說明了在給定時間預(yù)算下的查詢延遲、減少的倒排段處理數(shù)量等。

4.1 實驗環(huán)境及數(shù)據(jù)集

實驗的硬件環(huán)境為Intel?Xeon?CPU E3-1226 v3@3.30 GHz和256 GiB 內(nèi)存;軟件環(huán)境為Red Hat Enterprise Linux 6。

針對APS算法的評估,實驗在2個真實數(shù)據(jù)集上開展,數(shù)據(jù)集基本信息如下:

1)Word List A:來自于Paice官方網(wǎng)站,最初用于Paice評估,包含約10 000個詞。詞匯樣本取自于圖書情報學(xué)相關(guān)的CISI測試集。

2)Word List B:由Scrabble單詞檢查器中使用的單詞列表編譯而成,該樣本包含約20 000個單詞。

針對SAR算法的評估,實驗在2個標(biāo)準(zhǔn)TREC測試集ClueWeb09、數(shù)據(jù)集ClueWeb12-B13 進行。通過檢索質(zhì)量評價指標(biāo)nDCG@10對SAR 算法進行評估。數(shù)據(jù)集的文檔數(shù)量和實驗所用到的TREC主題如表7所示。

表7 TREC數(shù)據(jù)集及主題

另外,本實驗對數(shù)據(jù)集中的每個文檔進行了如下處理:將所有無效UTF-8字符轉(zhuǎn)換成了空格,同時對字母字符與數(shù)字字符進行分離,并剔除了標(biāo)記標(biāo)簽。

4.2 APS算法評價

在2個數(shù)據(jù)集樣本上對APS算法進行實驗。首先,為了形成對照,將改進后的APS算法與改進前的Porter Stemmer算法進行評估對比;之后,在數(shù)據(jù)集上對現(xiàn)有的詞干分析算法Paice/Husk及Lovins也進行了對比測試,作為數(shù)據(jù)參考。通過實驗驗證得知,與現(xiàn)有詞干分析算法相比,APS算法提高了對查詢詞詞干提取的準(zhǔn)確率,實驗結(jié)果如圖2所示。

以Word List A數(shù)據(jù)樣本為觀察對象,圖2(b)、(c)中,APS算法與改進前的波特詞干算法相比,詞干不足指數(shù)UI降低了約48.4%,相對截斷錯誤率ERRT降低了約28%。UI值的改善說明APS算法能對更多相關(guān)詞合并成同一詞干,例如對于單詞“ability”和“able”的處理,改進前的波特詞干算法并不會將其歸為同一詞干群。圖2(a)中OI值之所以相對改進前有所提升,是因為APS算法調(diào)整規(guī)則函數(shù)后刪除了許多重要詞綴,這對OI值造成了影響。實際上UI值的改善會在一定程度上影響OI值,導(dǎo)致詞干提取過度,但影響的單詞數(shù)較少。因此,根據(jù)ERRT值對總體相對準(zhǔn)確性的評估來看,APS算法對于詞干提取的效果要優(yōu)于波特詞干算法。

以Word List B數(shù)據(jù)樣本作為觀察對象。由圖2(e)、(f)可知,APS算法較改進前,詞干不足指數(shù)UI降低了約54.6%,相對階段錯誤率ERRT降低了約30.2%。可以發(fā)現(xiàn),在Word List B 數(shù)據(jù)樣本中,APS算法對于詞干提取的準(zhǔn)確率具有較大的提升,能夠?qū)⒏嗟南嚓P(guān)詞統(tǒng)一成同一詞干。

圖2 APS算法詞干提取準(zhǔn)確率評價

除此之外,通過和Lovins、Paice/Husk算法對比可知,APS算法表現(xiàn)更佳,其中相對截斷錯誤率的數(shù)據(jù)表明,APS算法相對于其他的詞干提取算法,有效提升了詞干提取準(zhǔn)確率。

4.3 SAR算法評價

對于2個評價數(shù)據(jù)集,將前十個主題用于訓(xùn)練線性模型,其余主題用于測試。評價效率的指標(biāo)只包括引擎框架生成top-k結(jié)果花費的時間,即查詢延遲時間,不包括將單詞字典、倒排列表加載到主存儲器的啟動成本以及寫入輸出文件的時間。查詢延遲時間通過chrono庫進行測量,檢索質(zhì)量選用nDCG@10作為度量指標(biāo)。

通過將倒排項數(shù)量η分別設(shè)置為104、105、106、107以及108觀察nDCG@10的變化,從而確定倒排項數(shù)量η的最佳取值。圖3為在給定處理倒排項數(shù)量η變化時,nDCG@10指標(biāo)的變化情況。由圖3可知,在不顯著影響檢索質(zhì)量的情況下,SAR算法有效減少了需要處理的倒排段數(shù)量。通過分析折線趨勢可以發(fā)現(xiàn),將η設(shè)置為數(shù)據(jù)集大小的10%最為合理,因為在η=107與η=108時,指標(biāo)nDCG@10數(shù)據(jù)表現(xiàn)效果不相上下。由上一步分析得到η最佳取值范圍后,在此基礎(chǔ)上用2個測試集合ClueWeb09b和ClueWeb12-B13的前10個主題訓(xùn)練模型,記錄在給定時間預(yù)算的情況下,查詢的延遲時間和處理的倒排段數(shù)量。由此模型來預(yù)測在給定時間預(yù)算下η的最佳取值。數(shù)據(jù)集ClueWeb09b和數(shù)據(jù)集ClueWeb12-B13符合線性回歸的特點,其線性模型包括恒定的開銷和每個倒排段的處理成本。通過最終的線性模型,確定η適當(dāng)?shù)娜≈岛?將時間預(yù)算分別設(shè)置為25、50、100、150、200 ms。在此條件下進行3次測試取平均值,最終SAR算法在2個數(shù)據(jù)集上的檢索質(zhì)量如圖4和圖5所示。

圖3 給定倒排項數(shù)量η時的nDCG@10指數(shù)

圖4 ClueWeb12-B13上的nDCG@10指數(shù)

圖5 ClueWeb1209b上的nDCG@10指數(shù)

圖4和圖5中max取值由雙側(cè)配對隨機化測驗得到,并作為標(biāo)準(zhǔn)值來體現(xiàn)相對有效性差異。由圖4和圖5可看出,在給定時間預(yù)算下,SAR算法檢索質(zhì)量有一定程度的下降,但在可接受范圍內(nèi);由圖中折線的總體趨勢可以發(fā)現(xiàn),隨著給定預(yù)算時間的延遲,檢索質(zhì)量也相應(yīng)提升。另外,由2個圖的數(shù)據(jù)對比可知,在數(shù)據(jù)集ClueWeb12-B13上處理所有倒排項所花費的時間要比數(shù)據(jù)集ClueWeb09b要長,這說明在相同的時間預(yù)算下,數(shù)據(jù)集越大,有效性折損也越大,因此,ClueWeb12-B13的nDCG@10指標(biāo)折損更多。

圖6和圖7為在2個數(shù)據(jù)集上的平均延遲時間,圖8和圖9為在2個數(shù)據(jù)集上的提前終止倒排段的數(shù)量與倒排段總數(shù)量。由圖6～9可知,SAR算法通過在給定查詢時間內(nèi)提前終止查詢過程,大大減少了倒排項的處理數(shù)量,從而有效減少了查詢延遲時間。

圖6 ClueWeb12-B13上的平均查詢延遲時間

圖7 ClueWeb09b上的平均查詢延遲時間

圖8 ClueWeb12-B13上的提前終止數(shù)量與總數(shù)量

圖9 ClueWeb09b上的提前終止數(shù)量與總數(shù)量

表8和表9為2個數(shù)據(jù)集上未處理的主題數(shù)與給定查詢時間下的超時時間。

表8 ClueWeb09b數(shù)據(jù)集上未處理主題數(shù)與超時時間

表9 ClueWeb12-B13數(shù)據(jù)集上未處理主題數(shù)與超時時間

由上述實驗結(jié)果分析可知,SAR 算法在特殊情況下存在略微的延遲,總體來看影響并不大,但在控制查詢延遲時間方面效果顯著。另外,隨著預(yù)算時間的增加,檢索質(zhì)量也相應(yīng)成正比提升,雖然存在一定程度的檢索質(zhì)量下降,但在可接受的范圍內(nèi)。實驗結(jié)果也驗證了SAR算法對控制尾部延遲的有效性,能夠減少計算資源的消耗,且對于用戶體驗的提升也有一定幫助。

5 未來展望

基于APS算法對文本預(yù)處理進行了優(yōu)化,并基于SAAT策略設(shè)計了隨時排序算法SAR,在數(shù)據(jù)集上的實驗結(jié)果達到了預(yù)期的效果,但考慮到時代環(huán)境的需求變化以及對各種場景的適用情況,該檢索系統(tǒng)的擴展未來還有一定的優(yōu)化空間,需要相關(guān)的研究和工作支持。為此,從幾個方面提出了需要進一步研究與探討的工作點:

首先,針對倒排索引,可以考慮利用數(shù)據(jù)壓縮算法對其進行壓縮,以減少索引占用的磁盤空間,進而降低磁盤讀寫數(shù)據(jù)的時間開銷。在之后的工作中可以在該檢索系統(tǒng)中添加一個簡單有效的解編碼器,例如基于單指令多數(shù)據(jù)流(single instruction multiple data,簡稱SIMD)的解編碼器[38-39],將壓縮和解壓的過程并行化,以實現(xiàn)存儲空間的減少和訪問速度的提升。

其次,由于文檔長度存在不確定性,詞頻存在隨機性,為提高對文檔中稀有詞項的建模能力,實現(xiàn)帶有Dirichlet平滑(dirichlet smoothing,簡稱DiS)方法或JM 平滑方法(jelinek-mercer smoothing,簡稱JMS)的語言模型[40]也是可行的優(yōu)化點之一。對文檔和查詢項進行語言建模后,不僅能夠提高估計文檔語言模型的準(zhǔn)確性,而且也能適應(yīng)查詢中非常用詞的生成。

最后,可以針對用戶接口設(shè)計更利于用戶體驗的界面。目前本文檢索系統(tǒng)的接口尚且基于文本,后期可以通過HTML界面來實現(xiàn)用戶交互接口。用戶在界面展示的文本框中輸入查詢詞后,搜索的結(jié)果能夠通過該界面進行展示以供閱讀、分析和判斷。對交互接口進行優(yōu)化能夠豐富表現(xiàn)信息的形式,便于用戶多方式高效接收信息,從而進一步提升用戶體驗。

6 結(jié)束語

針對文本預(yù)處理階段,設(shè)計了優(yōu)化的詞干分析算法APS,基于派生形態(tài)學(xué)調(diào)整了規(guī)則函數(shù)的定義,改善了波特詞干算法存在的詞干提取不足以及準(zhǔn)確率不理想的問題,并通過實驗驗證了APS算法在提升詞干提取準(zhǔn)確率的有效性。另外,針對相關(guān)排序階段,基于SAAT查詢策略設(shè)計了隨時排序算法SAR,能夠在給定時間預(yù)算或給定處理的倒排段數(shù)量的情況下,提前終止檢索過程,減少不必要的時間消耗,有效控制查詢延遲,返回較為準(zhǔn)確的檢索結(jié)果。在2個大規(guī)模TREC數(shù)據(jù)集上的實驗結(jié)果驗證了SAR 算法對于控制尾部延遲時間的有效性。最后,本文提出了若干可行的研究點,為未來的工作指明了方向。