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

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

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

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

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

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

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

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

1 相關(guān)工作

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

1.1 詞干提取

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

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

1.2 相關(guān)排序

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

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

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

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

2 基于改進(jìn)Porter Stemmer的APS算法

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

為使算法描述更清晰,首先對(duì)以下定義進(jìn)行說(shuō)明:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖1 APS算法流程

3 基于SAAT策略的隨時(shí)排序算法SAR

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

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

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

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

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

3.2 索引的組織方式

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

3.3 SAAT評(píng)估策略

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

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

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

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

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

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

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

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

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

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

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

4 實(shí)驗(yàn)評(píng)估

對(duì)APS算法和SAR算法分別進(jìn)行評(píng)估。

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

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

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

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

針對(duì)APS算法的評(píng)估,實(shí)驗(yàn)在2個(gè)真實(shí)數(shù)據(jù)集上開(kāi)展,數(shù)據(jù)集基本信息如下:

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

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

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

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

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

4.2 APS算法評(píng)價(jià)

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

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

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

圖2 APS算法詞干提取準(zhǔn)確率評(píng)價(jià)

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

4.3 SAR算法評(píng)價(jià)

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

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

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

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

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

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

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

圖6 ClueWeb12-B13上的平均查詢延遲時(shí)間

圖7 ClueWeb09b上的平均查詢延遲時(shí)間

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

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

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

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

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

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

5 未來(lái)展望

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

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

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

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

6 結(jié)束語(yǔ)

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