（計(jì)算機(jī)應(yīng)用技術(shù)專業(yè)論文）大規(guī)模中文文本檢索中的高性能索引研究.pdf

太蕊攫孛丈鬟盎控素中鼴商牲鼗霞l 麟戇= 摘要 摘要 漣罄笠聯(lián)釃土绱息瞧舉斷增長(zhǎng)枯跨蘸登齬，縫豢累縫，特澍是母文文零黢紫系縫， 楚樞蹙裂a(bǔ) 卷j 越泉越多豹關(guān)注。 索g l 跫檢索系綾必冪鼙爭(zhēng)熬綴或部勢(shì)，照撿囊系筑搓供抉逮囊讒服務(wù)麓美毽。蜒攆 支替照丈勰摸穩(wěn)索惹統(tǒng)最囂趣的索g l 影式。然豫，通常撼醞_ f ，索；f 鷯鞫建，鞠側(cè)攆文 件豹生成，是一個(gè) # 常耗時(shí)麴避程，為了逡墩大規(guī)模的文采檢索往務(wù)?；肀匾芯颗畁 恢 鞫建襄g 魏手段。 通過(guò)辯索g i 迸攫靜騫個(gè)除陂進(jìn)行努輯，零文措怒，道鬻熬豢； 算法效犁攀搿的奎蘩 原因霄二：1 ) c 甲u(yù) _ 搦i o 部棒捆豆等待，使穆系統(tǒng)資源的利用率不裹；2 ) 文戡分櫥階 戳蹙整個(gè)索 i 過(guò)程中韻瓶頸，特別的，辯中文文本麗言，靜詞是主要的開(kāi)銷。 鈴霹第一個(gè)睡遂，辜文霞串孬靜豢；l 流穩(wěn)中剮a 漁瘩縫瑟拇，援商了蠹源蘸終熱并 行程艘，進(jìn)而縮短側(cè)捧文律的生成時(shí)聞；在此纂礁t ，文中還比較了流水絨結(jié)構(gòu)在冪耐 參數(shù)下的性能差攤。 囂霹囂：令簿蘧，囂叛鬻月 愆純鼢爵薅結(jié)構(gòu)，虢鞠終母文靜分 霹遽發(fā)，烈蕊達(dá)蠶g 減 少分析階段靖輔聒銷前霹弱：程攏較了a 種常凳靜誦冀緒約之囂，文中攢出，鏊予竣數(shù) 綴辮的褥典結(jié)梅燕麓捷索 i 遴度靜有效犖段。 實(shí)驗(yàn)襲甥，綜臺(tái)使罔致上醒釋方法，哥馘健索 l 的漶澄怒商簽。鼴律盼，我稻對(duì) 串支t x t 支靜靜最俠索；l 蘧寢霹遮豁馘字斟黲， 芙穗褥：鼴臻文捧f 紫 & 流水統(tǒng)；努訶 黢數(shù)蘊(yùn)骶酶褥 疆 s t u d yo ne f f i c i e n ti n d e x i n gf o rl a r g e s c a l ec h i n e s et e x tr e t r i e v a ls y s t e m s m ij i a ( c o m p u t e r a p p l i e dt e c h n o l o g y ) d i r e c t e db y w a n g b i n i n v e f i e df i l e sa r go fg r e a ti m p o r t a n c ef o ri rs y s t e m s ，y e ti ti sat i m e c o n s u m i n gp r o c e s st o c o n s t r u c to n e w ew i l lf o c u sh e r eo nh o wt os p e e d u pt h ep r o c e s so fi n d e xb u i l d i n g i n t h i st h e s i s ，w ew i l lp o i n to u tt h a tt h e r ea r et w of a c t o r st h a ts l o wd o w nt h es p e e do f i n d e x i n g o n e i st h ei n e f f e c t i v eu s eo f s y s t e mr e s o u r c e s ，d u et ot h ep a u s e sc a u s e db yc p u a n d i ow h e nt h e yh a v et ow a i tf o re a c ho t h e r t h eo t h e ro n ei sb a s e do nt h ef a c tt h a td o c u m e n t p a r s i n g , e s p e c i a l l yc h i n e s ew o r ds e g m e n t a t i o n ，i so n eo ft h es l o w e s ts t e p sw h e nb u i l d i n ga n i n v e r t e df i l e ，i e ，i ti st h eb o t t l e n e c k t os o l v et h ef i r s tp r o b l e m ，w ei n t r o d u c et h ec o n c e p to f p i p e l i n et oo u ri n d e x i n gs y s t e m w i t h t h eh e l po fp i p e l i n e ，w ec a ni m p r o v et h ep a r a l l e l i s mo fo u r i n d e x i n gs y s t e m ，a n dm a k eb e t t e r u s eo fs y s t e mr e s o u r c e ss oa st os h o r t e nt h ei n d e x i n gt i m e a sf o rt h es e c o n do n e ，w ee x p e r i m e n to nd i f f e r e n tl e x i c o ns t r u c t u r e st oe v a l u a t et h e i r p e r f o r m a n c eo nw o r ds e g m e n t a t i o na n dp a r s i n g o u rr e s u l t sc o n f i r mu st h a td o u b l e a r r a yt r i ei s a ne x c e l l e n tc a n d i d a t ef o rc h i n e s ew o r ds e g m e n t a t i o n , a n di tc a na l s os p e e du pi n d e x i n g s i g n i f i c a n t l y k e y w o r d s ：i n v e r t e df i l e s , i n d e x i n g , p i p e l i n e ，w o r ds e g m e n t a t i o n ，d o u b l e - a r r a yt r i e 1 1 1 聲明 我聲明本論文是我本人在導(dǎo)師指導(dǎo)下進(jìn)行的研究工作及取得的研究成 果。盡我所知，除了文中特別加以標(biāo)注和致謝的地方外，本論文中不包含 其他人已經(jīng)發(fā)表或撰寫過(guò)的研究成果。與我一同工作的同志對(duì)本研究所做 的任何貢獻(xiàn)均已在論文中作了明確的說(shuō)明并表示了謝意。 作者簽名：槳嘉日期：2 0 。蹈竹骨二f 8 論文版權(quán)使用授權(quán)書 本人授權(quán)中國(guó)科學(xué)院計(jì)算技術(shù)研究所可以保留并向國(guó)家有關(guān)部門或機(jī) 構(gòu)送交本論文的復(fù)印件和電子文檔，允許本論文被查閱和借閱，可以將本 論文的全部或部分內(nèi)容編入有關(guān)數(shù)據(jù)庫(kù)進(jìn)行檢索，可以采用影印、縮印或 掃描等復(fù)制手段保存、匯編本論文。 ( 保密論文在解密后適用本授權(quán)書。) 作者簽名：米喜 導(dǎo)師簽名：弓斌 日期：力珂中j 引言 隨著互聯(lián)網(wǎng)應(yīng)用的普及，人們町以獲得的數(shù)字信息也是越柬越多。根據(jù)中國(guó)互聯(lián)網(wǎng) 絡(luò)信息中心( a q n i c ) 在今年1 月份發(fā)白的第卜五次中國(guó)互聯(lián)網(wǎng)絡(luò)發(fā)展?fàn)顩r報(bào)告1 顯 示：我國(guó)境內(nèi)注冊(cè)的網(wǎng)站數(shù)目已多達(dá)6 6 萬(wàn)，國(guó)際出口的帶寬總量高達(dá)7 4 g ；3 9 1 的用 戶的主要上網(wǎng)目的足獲取信息，6 5 o 的用戶經(jīng)常使用搜索引擎。町以預(yù)見(jiàn)，隨著時(shí)問(wèn) 的推移，將有更多的信息出現(xiàn)在網(wǎng)絡(luò)上，而用戶對(duì)信息的需求也會(huì)不斷的增加。 面對(duì)大量的數(shù)據(jù)，要從中找出所需的信息，就要借助于檢索技術(shù)。對(duì)檢索用戶而言， 就耍把自己的檢索需求表達(dá)出來(lái)( 例如若1 二個(gè)關(guān)鍵詞) 并提交給檢索系統(tǒng)。檢索系統(tǒng)要 提供槍索服務(wù)，首先要有待檢索的數(shù)據(jù)源，通常足大量文檔的集合。一種很直觀的檢索 方案是，對(duì)集合中的每個(gè)文檔，檢查每個(gè)關(guān)鍵字是否出現(xiàn)，并按其問(wèn)的邏輯關(guān)系進(jìn)一步 判斷是否返回。但足，盡管存在線性的掃描算法( 關(guān)鍵字匹配) ，由于文檔空問(wèn)實(shí)在是太 大了，用戶不得不忍受超長(zhǎng)的響應(yīng)時(shí)問(wèn)。既然在線掃描行不通，檢索系統(tǒng)就需要借助于 某種機(jī)制，把在線的時(shí)間上的負(fù)擔(dān)轉(zhuǎn)移到離線的空日j 上去。這種機(jī)制就是索引。 1 1 索引的結(jié)構(gòu) 概念上講，索引可以看成是一個(gè)巨大的二維矩陣( 位圖) ：行代表所有的關(guān)鍵字，列 對(duì)應(yīng)所有的文檔，每個(gè)元素則表示關(guān)鍵字是否在文檔中出現(xiàn)。矩陣的列向量可看做文檔 的向量化表示，即文檔中出現(xiàn)了哪些關(guān)鍵字；行向量則反映了關(guān)鍵字在文檔集合中的分 布這正是在線掃描所期望的結(jié)果。所以，如果事先( 離線) 收集到這些信息，在線 檢索就能在合理的時(shí)間內(nèi)響應(yīng)用戶的請(qǐng)求。典型的情況足：對(duì)請(qǐng)求中每個(gè)關(guān)鍵字，從索 引中得到相應(yīng)的文檔列表( 即行向量) ；再根據(jù)關(guān)鍵字之問(wèn)的邏輯關(guān)系進(jìn)行向量的合并； 然后根據(jù)一定的準(zhǔn)則進(jìn)行相似度排序，將最相關(guān)的若干文檔及其信息返回給檢索用戶。 然而，這種位圖的表示方法需要巨大的存儲(chǔ)空間。特別的，對(duì)于自然文本而言，關(guān) 鍵字的分布是極其不均衡的：占詞匯表很小一部分的高頻詞幾乎在所有的文檔中出現(xiàn)， 而相當(dāng)一部分的詞是僅出現(xiàn)在極少數(shù)的文檔中的低頻詞。這意味著，在索引矩陣中，只 有少數(shù)的行向量比較飽滿，而大多數(shù)的行向量則比較稀疏。列向量也存在類似的主題相 關(guān)的稀疏問(wèn)題。因此，位圖矩陣需要壓縮。于是，就產(chǎn)生了另外一種索引結(jié)構(gòu)：倒排文 件( 1 n v e n e df n e ) 2 倒排文件由多個(gè)倒排表( i n v e r t e dl i s t ) 組成，每個(gè)關(guān)鍵字對(duì)應(yīng)一個(gè)。倒排表可看作 1 參見(jiàn)；h _ t l p ：w w w c n n i c 垂e 1 c n d o w n l o a d 2 0 0 5 2 0 0 5 0 1 1 8 0 1 1 x 1 f 2 除r 倒捧文件之外，索哼i 的實(shí)現(xiàn)機(jī)制廟包括后綴數(shù)組( s u w a x a r r a y ) 、簽名史件( s i g n a t u r ef i l e ) 【2 2 1 由于丈多數(shù)撿 囊系統(tǒng)的索引都采用倒排文件實(shí)現(xiàn)( 特剮靠人規(guī)模致姑童的情況下) ，閃此。為，敘述卜的方便，奉支將把索引和倒捧 文件等w 起束 1 中陶f(shuō) i 學(xué)院碘 學(xué)位論丈人艦?zāi)Ｖ锌罩Х铊诓芍械膷u性能索引研兜 足矩陣行向暈的，b 縮表示：它實(shí)際上足一個(gè)文檔列表( p o s t i n g l i s t ) ，在該列衷的每個(gè)節(jié) 點(diǎn)文檔( p o s t i n g ) 中，該關(guān)鍵字至少出現(xiàn)( o c c u r r e n c e ) 一次。 l j 壯出- 出 一 i 對(duì)d * 。h 2 一 l 曲l ；s 一 ： ：l l f v m 口。 ， 一 l f ， 一 i 協(xié) ，l 五 i ，“i c ：l o n n g l m c r r c d l = t ac 。i r a , n i n g 蝣口 w d 6 萱 缸b d 砌刪辨盯m 胂6 孵 圖1 1 倒排文什的結(jié)構(gòu) 倒排文件的大小通常和原始文檔集合在同一數(shù)量級(jí)。本質(zhì)上，每個(gè)倒排表足一個(gè)變 長(zhǎng)的記錄，整個(gè)倒排文件是一個(gè)變長(zhǎng)記錄的集合。如何組織這些變長(zhǎng)記錄? 不同的組織 方式意味著不同的文件大小，不同的空間利用率，更重要的是不同的訪問(wèn)效：蕃和更新代 價(jià)。 除了存儲(chǔ)開(kāi)銷外，倒排文件的生成代價(jià)也足較大的。為了盡可能的加快在線檢索的 響應(yīng)速度，倒排文件需要事先采集好關(guān)鍵字和文檔的統(tǒng)計(jì)信息( 統(tǒng)計(jì)對(duì)象的選取和粒度 跟檢索時(shí)用的檢索模型密切相關(guān)) ，即至少要對(duì)整個(gè)文檔集合進(jìn)行一遍掃描。整個(gè)過(guò)程可 以看作是先逐文檔構(gòu)造倒排矩陣的列向璧，然后再依次將行向黽寫入倒排文件，如同作 了一次“轉(zhuǎn)置”運(yùn)算4 。由于倒排文件通常是離線生成的，它的時(shí)自j 丌銷常常被檢索系統(tǒng) 忽略。 倒排文件的建立過(guò)程會(huì)生成一個(gè)全局詞典( v o c a b u l a r y ) ，其中記錄了掃描的過(guò)程中 遇到的關(guān)鍵字。由于倒排文件很大，通常無(wú)法一次載入內(nèi)存；只能等到檢索時(shí)處理某關(guān) 鍵字時(shí)，再?gòu)拇疟P上讀入相應(yīng)倒排表。由于倒排文件足變長(zhǎng)記錄的集合，要隨機(jī)訪問(wèn)任 意倒排表，必須事先知道每一個(gè)的偏移位置。這個(gè)定位信息一般作為詞典中每個(gè)詞條的 一部分。詞典的規(guī)模一般較小，能夠次裝入內(nèi)存并常駐，供檢索時(shí)使用。 1 2 本文的主題 倒排文件是檢索系統(tǒng)必不可少的組成部分，它在很大程度上也限定了檢索系統(tǒng)所能 夠達(dá)到的最大性能。囡此，對(duì)倒排文件的研究一直是檢索領(lǐng)域的熱點(diǎn)5 。隨著網(wǎng)絡(luò)應(yīng)用的 3 摘白【1 3 】 “倒捧文件”的名4 ，由柬。 5 有關(guān)例捧文件的研f 究，土萱分為索0 l 和拎索兩大類前苦吉垂考慮倒捧文件自身的性質(zhì)，石肯關(guān)注例排文件耐古洵 r 能的影響只體的i 兌前省討 究的f u j 題包括：如何減少倒持文件的人小( 索0 l 環(huán)縮1 1 】【2 1 ) 、如何加快索引的流程( 索 j i 算法【1 】1 1 3 1 ) 、如何減少倒手 f 叟件的維護(hù)代價(jià)( 索弓i 螂i 1 1 5 1 1 6 1 1 7 1 【8 】) ；后占甜f 究的f u 】題包括：如何加伙a 詢的響應(yīng) 2 一圓一 一一 第一帝相關(guān)研究介紹 普及，對(duì)艙索系統(tǒng)( 特別足搜索引擎) 的要求也與f 1 俱增：既要索引越束越多且不斷變 化的信息，又耍保證良好的并發(fā)性和響應(yīng)速度。岡此如何優(yōu)化倒排文件組織，改蒔檢索 算法、提高槍索系統(tǒng)效率成為一個(gè)畦要的研究課題1 4 1 。 時(shí)也必須看到，隨著文檔集合的規(guī)模不斷擴(kuò)大，倒排文件的生成丌銷問(wèn)題也越柬 越突出。根據(jù)t r e c 2 0 0 4 6t e r a b y t et r a c k 的報(bào)告，對(duì)4 2 6 g 的數(shù)掘進(jìn)行索引，十幾家參賽 單位的耗時(shí)從1 7 個(gè)小時(shí)到幾百個(gè)小時(shí)不等。7 此外，索引的生成速度也直接影響了索引的更新速度。大多數(shù)情況下，柃索系統(tǒng)采 用最簡(jiǎn)犖但也足非常實(shí)用的重建索引的策略。即使采用更快捷的合并更新的策略，由于 合并過(guò)程足構(gòu)建過(guò)程的自然延續(xù)，因此更新的效率都受限丁= 生成速度。 通常的槍索系統(tǒng)至少包括采集系統(tǒng)、索引系統(tǒng)和查詢系統(tǒng)三個(gè)部分。采集系統(tǒng)用來(lái) 獲得待處理的文檔，它跟索引系統(tǒng)之間是典型的“生產(chǎn)者一消費(fèi)者”關(guān)系。在b r 用帶寬 不斷增加、采集技術(shù)不斷改進(jìn)的情況下，如何使得索引系統(tǒng)跟得上采集器的步伐，也足 檢索系統(tǒng)亟需面對(duì)的一個(gè)現(xiàn)實(shí)問(wèn)題：更新速度跟不上，用戶只能檢索到過(guò)時(shí)的信息。 鑒于以上原因，本文將著重討論如何加快倒排文件的生成。 在下面的章節(jié)里，本文將指出： 普通的串行索引算法對(duì)資源的利用并不充分；通過(guò)引入流水線結(jié)構(gòu)，可以提高 資源的利用率，進(jìn)而縮短索引的構(gòu)建時(shí)日j 。 文檔分析是生成過(guò)程中最慢的環(huán)節(jié)；通過(guò)采用基于雙數(shù)組t r i e 樹(shù)的詞典結(jié)構(gòu)， 可以加快分析，進(jìn)而加快索引的生成速度。 1 3 內(nèi)容的安排 論文的組織如下：第二章介紹索引構(gòu)建的一般流程；第三章將對(duì)各個(gè)步驟的丌銷進(jìn) 行詳細(xì)的分析；第四章將專門討論并行索引，特別是流水線結(jié)構(gòu)對(duì)索引性能的改善；第 五章則從分詞的角度來(lái)討論如何加速索引；第六章簡(jiǎn)要的介紹使用倒排文件的檢索系統(tǒng)； 最后給出總結(jié)和展望。 速度( 索引壓縮，索引結(jié)構(gòu)優(yōu)化【1 】【4 】) ，如何利用多節(jié)點(diǎn)分布j 撿索( 索引分布1 6 1 1 1 ) 等這些研究點(diǎn)都不足孤立的， 例如：索引壓縮的目的即是為了減少倒捧文件的大小，也同時(shí)減少r 檢索時(shí)i o 的開(kāi)銷；分布式p - , c a t 即可以用于檢索， 也町以用于索引的創(chuàng)建1 9 1 0 1 從另一個(gè)角度來(lái)講，索引的性能跟檢索的性能存在著某種程度的。對(duì) z ”，即需愛(ài)在索 引中存儲(chǔ)的信息越 富。則檢索的性能越好，i f 百索引本身的維護(hù)開(kāi)銷則越大 。參見(jiàn)：一httd：trecnist20v 7h 中微軟利用6 臺(tái)盎配置的服務(wù)器( 硬c p u + 4 g 內(nèi)存+ 4 個(gè)2 0 0 g 的i d e 鹼盤) ，索引時(shí)間為1 1 6 小時(shí)。 3 第二章索引流程簡(jiǎn)介 要想找出索引構(gòu)建耗時(shí)的原因，首先需要了解生成索引的流程，并仔細(xì)分析各個(gè)階 段的丌銷8 。本拳將對(duì)該流程進(jìn)行簡(jiǎn)要介紹；詳細(xì)的開(kāi)銷分折將在下一章展開(kāi)。 本章組織如下：首先介紹各種類型的索引構(gòu)建算法；然后以s o r t b a s e d 算法為例， 詳細(xì)介紹涉及到的主要步驟。 2 1 索引算法簡(jiǎn)介 可以想象，如果有足夠大的內(nèi)存，便可把整個(gè)倒排文件( 甚至是索引矩陣) 裝入， 那么構(gòu)建的代價(jià)基本上就只由分析步驟決定( 統(tǒng)計(jì)文檔內(nèi)訓(xùn)匯的分布) 。然而內(nèi)存總是有 限的，如果完全依賴于操作系統(tǒng)的虛擬存儲(chǔ)系統(tǒng)，而不是有意識(shí)的管理磁盤i 0 。頻繁 的缺頁(yè)將會(huì)大大的降低系統(tǒng)的性能【1 】。 【1 1 中介紹了多種倒排文件的生成算法：基于內(nèi)存的，基于排序的( 基于磁盤的) ； 對(duì)臨時(shí)文件進(jìn)行壓縮的，對(duì)內(nèi)存中的倒排表進(jìn)行壓縮的；對(duì)全部文檔僅掃描一遍的，需 要預(yù)先掃描一遍的9 ；普通多路歸并的，就地( i n p l a c e ) 多路歸并的等等。這些算法， 對(duì)內(nèi)存空間、臨時(shí)磁盤空間的需求是各不相同，效率也f 差萬(wàn)別。它們大多數(shù)足對(duì)基于 排序的算法的某種改進(jìn)，或是針對(duì)特定資源約束的折中。事實(shí)上，基于排序的算法已經(jīng) 成為了構(gòu)建索引的標(biāo)準(zhǔn)算法，稍后我們將詳細(xì)介紹。 【1 3 j 哩也對(duì)現(xiàn)存的構(gòu)建倒排文件的算法進(jìn)行了總結(jié)，并大體上可以基于內(nèi)存的、基 于磁盤和和基于排序的三類。 簡(jiǎn)單的基于內(nèi)存的方法實(shí)際上就是引言中提到的索引矩陣法，它需要對(duì)文檔集合進(jìn) 行兩遍掃描。第一遍用來(lái)確定關(guān)鍵字和文檔的數(shù)目，以便分配一個(gè)空的二維矩陣( 關(guān)鍵 字?jǐn)?shù)文檔數(shù)) ；第二遍掃描的時(shí)候，才真正進(jìn)行先列后行的填充和輸出( 可按行為單 位進(jìn)行壓縮) 。顯然這種方式需要龐大的內(nèi)存，因而足不合適的。該方法的一個(gè)變種是把 每行用鏈表的形式表示( 因而只需要一遍掃描) 。然而鏈表上的存儲(chǔ)空間不是連續(xù)的，對(duì) 鏈表的隨機(jī)訪問(wèn)會(huì)造成大量的缺頁(yè)。 另外一種基于內(nèi)存的算法利用索引壓縮束減少對(duì)內(nèi)存空間的需求。它也是一個(gè)需要 掃描兩遍的算法：在第一遍掃描中，形成詞典以及粗粒度的統(tǒng)計(jì)信息( 例如詞頻) ；在第 二遍掃描之靜，先分配一塊內(nèi)存區(qū)域，并按關(guān)鍵字進(jìn)行分割( 倒排表長(zhǎng)度已知) ，掃描時(shí) 直接填充到相應(yīng)的內(nèi)存位置。由于連續(xù)存儲(chǔ)，節(jié)省了指針的存儲(chǔ)開(kāi)銷。當(dāng)然，內(nèi)存空間 毫無(wú)疑問(wèn)，使用分布式的策略町以加快索引的構(gòu)娃過(guò)程。即使自收集傘局信息的額外負(fù)擔(dān)( 這個(gè)負(fù)擔(dān)足文檔集合大 小的次線性函數(shù)，相對(duì)于索0 l 生成代價(jià)( 線性對(duì)數(shù)) 來(lái)說(shuō)璺小1 1 0 1 ) 。小過(guò)，奉文只討論單個(gè)節(jié)點(diǎn)上的加速f 段 為，獲得統(tǒng)計(jì)信息以利于優(yōu)化組織內(nèi)存 5 中國(guó) 學(xué)院壩1 學(xué)位論支人塒模中文史奉柃采中的扇廿能索0j 研究 的大小還是相當(dāng)町觀的，b r 以盤第一遍中先確定每個(gè)倒排襲在壓縮方式下的最大長(zhǎng)度1 0 。 填充時(shí)直接采用爪縮表示。該算法的主要缺點(diǎn)足擴(kuò)展性不強(qiáng)，只適合中鋒規(guī)模的文檔集 合。一種改進(jìn)是把預(yù)分配的空i h j 轉(zhuǎn)移到磁盤上，并根據(jù)可用內(nèi)存劃分文檔集合，分批處 理；當(dāng)內(nèi)存飽和時(shí)，合并到磁盤上( 也就是說(shuō)，磁盤上每個(gè)倒排衷足逐批填充的) 。很明 顯，這種改進(jìn)需要在第一遍掃描中搜集更多的信息。 基于磁盤的基本思想足把倒排表放在磁盤上而不足內(nèi)存中。屬于同一個(gè)倒排表的節(jié) 點(diǎn)在臨時(shí)文件中通過(guò)指針鏈接起來(lái)；當(dāng)所有文檔掃描完畢后，以詞典的順序遍歷所有的 鏈表，并進(jìn)行壓縮，保存在新的文件中。該方法的劣勢(shì)在于需委額外的磁盤空間束保存 臨時(shí)文件，并且在生成索引時(shí)，需要大麓的磁盤定位操作。 至于基于排序的算法，我們將在下一節(jié)進(jìn)行介紹。 2 2 基于排序的算法 在基于排序的索引構(gòu)建算法中，假設(shè)可用內(nèi)存要比最終的索引小，即無(wú)法一次處理 完所有的文檔，只能分批進(jìn)行。因此，算法上要生成臨時(shí)索引以及合并臨時(shí)索引兩部分 組成。自口者又涉及到以下操作：在內(nèi)存允許的自f 提下，讀入若于文檔，調(diào)用分析算法統(tǒng) 計(jì)文檔內(nèi)的信息1 1 并暫存在緩沖區(qū)中；等到緩沖區(qū)滿的時(shí)候，再按關(guān)鍵字排序輸出到臨 時(shí)文件。 今 t 屯 l e x i c o n ) 兩一m 。qa r r ；2 o m p o m r ) f | e d e xt e 。御 m 6 口 l 2 j ， ， e 站h t o l i n 1 3 鬻：o n 腳一m 一“m n a 啤o c s 姆t 。r m d a f #潞勰。黼氍蛔n m oc 餅n p r s hn m 圖2 1 基于排序的索引算法” 帕實(shí)際的b 縮k 度依賴十倒排表中的支竹編q ，i 向這扛第一遍f i 描中足無(wú) 上收集到的；如果為某個(gè)關(guān)鍵字保留的存儲(chǔ) 守問(wèn)過(guò)小對(duì)j # 進(jìn)行擴(kuò)鹱的代價(jià)足比較高的，閃此必須計(jì)算其i 限：n 使用強(qiáng)大值的情況下，一般會(huì)導(dǎo)毀5 的內(nèi)存 浪贊 1 3 1 ”表現(xiàn)為一系列的形如關(guān)鍵寧，立h 編l j ，史檔內(nèi)信息 的三幾組，其中文檔內(nèi)信息包拓文檔內(nèi)頻率位置信息等 1 2 摘f j 1 3 1 6 ； 網(wǎng)引俐引 考 網(wǎng)引俐喇 尋 第一二黿索0 i 贏程簡(jiǎn)介 2 2 1 文檔分析 可以看出，分析步驟是索引構(gòu)建算法的基本元素，其輸入足集合中的每篇文檔，輸 出足由 三元組構(gòu)成的流。相對(duì)f 整個(gè)文檔集合而占， 單個(gè)文檔是非常小的，因此分折算法有必要采用最適合于“小串集合”( s m a l ls e t so f s t r i n g ) 的數(shù)據(jù)結(jié)構(gòu)【1 2 1 ”。 分析所要完成的工作就是識(shí)別文檔內(nèi)的關(guān)鍵字并進(jìn)行統(tǒng)計(jì)?！? 2 】考察了各種常用的 數(shù)掘結(jié)構(gòu)在該任務(wù)上的表現(xiàn)：樹(shù)、t i l e 樹(shù)、h a s h 表以及各種改進(jìn)。文檔的屬性，特別是 詞匯分白的不均衡，將大大影響各種結(jié)構(gòu)的性能：如果能夠?yàn)楦哳l詞匯提供快捷的訪問(wèn)， 那么即便影響其它詞的效率也是值得的；另一方面，如果詞匯分布的比較均勻，就沒(méi)有 必要來(lái)對(duì)結(jié)構(gòu)進(jìn)行動(dòng)態(tài)調(diào)整。 二分查找樹(shù)( b s t ) 足一種常用的樹(shù)結(jié)構(gòu)，其性能依賴于關(guān)鍵字的插入順序。可以 假定，大多數(shù)文檔并非足按照關(guān)鍵字排列的，因此平均的查找代價(jià)是對(duì)數(shù)一級(jí)的，而非 最壞情況下的線性。另外，常用詞很有可能在文檔中較早出現(xiàn)，因此它們會(huì)被存儲(chǔ)在樹(shù) 的較高的層次上，因此訪問(wèn)代價(jià)很??；同時(shí)它們又在文檔中大量出現(xiàn)，且本身長(zhǎng)度通常 又較短，進(jìn)一步降低了整體的代價(jià)。 b s t 還有一些變種，如a 。樹(shù)、紅黑樹(shù)，用束在插入后調(diào)節(jié)樹(shù)的平衡。雖然可以 將最壞情況下的查找代價(jià)提升到對(duì)數(shù)時(shí)間，但是由f 樹(shù)結(jié)構(gòu)的重新組織，常用詞未必就 保存在樹(shù)的高層。但另一方面，由于大部分足常用詞，上要的操作足訪問(wèn)而不是插入， 因此平衡樹(shù)結(jié)構(gòu)調(diào)整的丌銷可以限定在一個(gè)合理的范圍。 s p l a y 樹(shù)是b s t 的另外一個(gè)適應(yīng)性變種，它在每次訪問(wèn)的時(shí)候修改樹(shù)結(jié)構(gòu)，以便使 被訪問(wèn)的節(jié)點(diǎn)向根結(jié)點(diǎn)靠近一些( 通過(guò)一次旋轉(zhuǎn)) ，其結(jié)果就是常用訶聚集在根結(jié)點(diǎn)周圍， 這對(duì)普通文本來(lái)說(shuō)是很好的性質(zhì)但是過(guò)多的旋轉(zhuǎn)將損害其帶來(lái)的好處，一種改進(jìn)是每 隔k 次訪問(wèn)才旋轉(zhuǎn)一次。 f a b ( f r e q u e n c y - a d a p t i v eb s t ) 樹(shù)賦予每個(gè)節(jié)點(diǎn)一個(gè)計(jì)數(shù)器，每次訪問(wèn)加1 ，并通 過(guò)旋轉(zhuǎn)來(lái)使得計(jì)數(shù)器滿足堆( h e a p ) 的性質(zhì)為了避免計(jì)數(shù)器溢出以及非常用詞的局部 集中分布，可以在根結(jié)點(diǎn)的計(jì)數(shù)器超過(guò)某個(gè)門限值時(shí)，對(duì)樹(shù)中的高頻節(jié)點(diǎn)進(jìn)行一次遍歷 并減小其計(jì)數(shù)器，來(lái)降低這些節(jié)點(diǎn)的“熱門程度” 與b s t 及其變種相比，t r i e 樹(shù)雖然可以獲得比較快的訪問(wèn)速度，但是其對(duì)空問(wèn)的需 求較大，為此【1 2 】提出了一種改進(jìn)的結(jié)構(gòu)：b u i s ft r i e 樹(shù)。這種結(jié)構(gòu)包含一個(gè)標(biāo)準(zhǔn)的瓢e 樹(shù)結(jié)構(gòu)，只不過(guò)葉子節(jié)點(diǎn)不再僅對(duì)應(yīng)一個(gè)關(guān)鍵字，而是一個(gè)可以存儲(chǔ)多個(gè)關(guān)鍵字的容器 ( 例如二分查找樹(shù)) 。這樣，查找一個(gè)關(guān)鍵字的時(shí)候，從根結(jié)點(diǎn)出發(fā)，采用通常的t i l e 樹(shù)檢索算法到達(dá)容器，這意味著關(guān)鍵字的前綴將與檢索路徑相匹配；然后在容器內(nèi)，再 ”相對(duì)的，適臺(tái)于天數(shù)據(jù)集的結(jié)構(gòu)( 特別足適應(yīng)性結(jié)構(gòu)) 如果戍用到小集合上，很有町能拒結(jié)構(gòu)達(dá)到r 衡點(diǎn)之前輸入 就結(jié)束r 此外。纂嶼大集合下町以忽略代價(jià)的操作。例如初始化時(shí)的卒問(wèn)分配，以及結(jié)束前的越歷等，在小集合上 尢疑會(huì)顯著的影響整體性能 7 中【日f(shuō) 學(xué)院碩卜學(xué)位論之人l 嫩模中上支奉柃裹中的高能索0 【l 小亢 利用容器本身的檢索方法去查找后綴。u r 以看出，容器內(nèi)的父鍵字共9 f i i y 綴，因此也就 箝省了存儲(chǔ)空閫。當(dāng)容器中的關(guān)鍵字達(dá)到一定數(shù)目的時(shí)候，葉節(jié)點(diǎn)分裂( 即所謂的b u r s t ) ， 在新節(jié)點(diǎn)內(nèi)藿新分配關(guān)鍵字。 除了各種樹(shù)結(jié)構(gòu)之外，h a s h 表足最常用的一種結(jié)構(gòu)。借助j 二好的h a s h 函數(shù)，h a s h 表一般可以獲得最好的性能。為了進(jìn)一步提高性能，口r 以把最近訪問(wèn)的符點(diǎn)移到所在 h a s h 鏈的頭部，這樣常用詞就聚集在各h a s h 鏈的頭部，僅需要進(jìn)行少數(shù)幾次字符串比 較。h a s h 表的不足在于并非按有序的順序來(lái)組織數(shù)據(jù)。 f 1 2 】比較了各種結(jié)構(gòu)，其結(jié)論足：b u r s tt n e 樹(shù)是最合適的。 2 2 2 全局詞典 分析階段的另一項(xiàng)任務(wù)是在備文檔之日j 維護(hù)一個(gè)全局詞典1 4 ，每篇文檔處理完畢， 文檔內(nèi)的關(guān)鍵字信息就要并入全局詞典。詞典和分析過(guò)程實(shí)際上是競(jìng)爭(zhēng)內(nèi)存的：詞典占 用的內(nèi)存越多，則每輪處理的文檔數(shù)就越少，臨時(shí)索引就越多，歸并時(shí)甘j 也就越長(zhǎng)。雖 然經(jīng)常假設(shè)珂典可以一次性載入內(nèi)存，還需看到，由于總會(huì)有新的關(guān)鍵字出現(xiàn)，因此詞 典的規(guī)模還會(huì)擴(kuò)大。另一方面，很多關(guān)鍵字僅在某一輪中相對(duì)集中的出現(xiàn)少數(shù)幾次，在 后繼的輪次中就沒(méi)有必要繼續(xù)保留。 為了盡可能的減少詞典占用的空問(wèn)對(duì)構(gòu)造倒排文件的影響，【1 3 】采用了不在輪次之 問(wèn)共享詞典的策略：在每一輪結(jié)束后，將本輪的詞表寫入臨時(shí)倒排文件中( 為了能夠進(jìn) 行最后的歸并) ，然后清空當(dāng)自口詞典，在下一輪中重新利用這部分空日j 巧。 無(wú)論是對(duì)索引生成還是在線檢索，詞典的結(jié)構(gòu)至關(guān)藿要。不同的結(jié)構(gòu)有不同的存儲(chǔ) 丌銷，更重要的足，有不同的查詢代價(jià)。處理過(guò)程中有相當(dāng)一部分時(shí)間是用來(lái)定位關(guān)鍵 字的。定位方式的大體可分為兩類：基于比較的和基于計(jì)算的。比較也足一種操作，只 不過(guò)太常用而已。 典型的使用字符串比較的結(jié)構(gòu)就是各種線性表以及樹(shù)結(jié)構(gòu)。為了加快定位，通常在 結(jié)構(gòu)內(nèi)部維持一種有序關(guān)系或者自適應(yīng)性，以期減少待比較節(jié)點(diǎn)的數(shù)目。樹(shù)結(jié)構(gòu)的性能 通常不理想，很大原因在于關(guān)鍵字要被比較多次。與此相對(duì)，t i l e 樹(shù)的比較粒度降為單 個(gè)字符，次數(shù)僅由關(guān)鍵字自身長(zhǎng)度限定但足t r i e 樹(shù)的優(yōu)勢(shì)是用空問(wèn)換來(lái)的，每個(gè)節(jié)點(diǎn) 都要維護(hù)字母表規(guī)模的指針，過(guò)度發(fā)散會(huì)導(dǎo)致空f(shuō) 可浪費(fèi)以及多次i o ，因此需要借助輔 助的結(jié)構(gòu)( 如h a s h 表) ，僅包含字母表的某個(gè)子集。 基于計(jì)算( 非比較) 的方法本質(zhì)上是尋求一種從詞典空問(wèn)到整數(shù)空問(wèn)的映射。h a s h 文檔分析”小節(jié)中用到的數(shù)據(jù)結(jié)構(gòu)也町以著作足一個(gè)訓(xùn)典，只不過(guò)該詞典足局部十每個(gè)史擋的特別的，在文 檔之問(wèn)，需要對(duì)該數(shù)據(jù)結(jié)構(gòu)進(jìn)行葷冒或者清空操作 o 實(shí)際上，【1 3 】中采用的構(gòu)建倒排文件的策略也稍自小n j j 序后的臨時(shí)索0 l 相t t ：，內(nèi)存中的- j l f l t 序列存d 一關(guān)鍵 ，的冗余( 由f 無(wú)序) ，【1 3 1 , 就i 式1 t 1 用磁盤上的格式束表示三幾組并且邊處理邊居縮由卜卜共享媳，每輪還需受 把詞典( 采用前綴編碼f r o n t c o d i n g ) 輸 i j 到臨時(shí)文件以用于最后的歸并該方案下關(guān)鍵字并未事九轉(zhuǎn)化為整數(shù)刪此 棚鄰的倒排表對(duì)廊相鄰的關(guān)鍵字，從由支持關(guān)鍵7 區(qū)問(wèn)a 咖 8 第二營(yíng)索引贏程簡(jiǎn)介 函數(shù)就是一種映射，只不過(guò)存在映射沖突，需要進(jìn)一步的比較束解決沖突。借助于良好 設(shè)計(jì)的h a s h 函數(shù)，對(duì)關(guān)鍵字空問(wèn)進(jìn)行一次劃分，沖突的概率i r 限定在一個(gè)合理的范圍， 再輔以某些優(yōu)化策略( 例如常用詞置于鏈?zhǔn)? ，町何效的減少嚴(yán)均比較次數(shù)。 理想的情況下，映射應(yīng)該是單射，即無(wú)沖突的完莢h a s h 1 。完莢h a s h 的構(gòu)造一般 很耗時(shí)問(wèn)，通常足根掘一個(gè)固定的糾表事先計(jì)算好；當(dāng)訓(xùn)表發(fā)生變化的時(shí)候，需要重新 計(jì)算?？梢詫ｉT針對(duì)常用的關(guān)鍵字構(gòu)建一個(gè)完美h a s h ，對(duì)其它的關(guān)鍵字采用基f 比較的 結(jié)構(gòu)，從而能夠適應(yīng)詞表的擴(kuò)展( 假設(shè)新詞都不是常用訶，因此已構(gòu)造的完莢h a s h 不 需要變化) 。 雙數(shù)組t i l e 樹(shù)也是一種基于計(jì)算的結(jié)構(gòu)，它實(shí)質(zhì)上足t r i e 樹(shù)的扁平化表示1 1 8 1 1 1 9 1 ， 逐字符的計(jì)算( 即改變下標(biāo)) 對(duì)應(yīng)著t i l e 樹(shù)指針的移動(dòng)。由于僅保留有效的指針，數(shù)組 占用的空間要比t h e 樹(shù)小。與完莢h a s h 類似，雙數(shù)組t i l e 樹(shù)也是一種靜態(tài)結(jié)構(gòu)，適合 于詞表固定的場(chǎng)合；當(dāng)詞表變化時(shí)，其調(diào)整的代價(jià)通常比較大。 除了數(shù)據(jù)結(jié)構(gòu)，詞典本身的規(guī)模1 6 以及覆蓋率等屬性也足影響分析效率、效果的一 個(gè)重要方面。 新的文檔總是會(huì)出現(xiàn)新的關(guān)鍵字的，那么詞典本身是動(dòng)態(tài)的還是靜態(tài)的? 動(dòng)態(tài)詞典 可以保證文檔中出現(xiàn)的關(guān)鍵字都被檢索到，但是其規(guī)模會(huì)不斷的增加，可用性會(huì)越來(lái)越 差。靜態(tài)詞典查找和維護(hù)的開(kāi)銷小，卻很容易會(huì)產(chǎn)生查詢失敗( 例如字母組合) 。 此外，關(guān)鍵字對(duì)應(yīng)哪種語(yǔ)法單元，足字是詞或是短語(yǔ)? 度小時(shí)，詞典規(guī)模會(huì)降下 來(lái)，但是每個(gè)倒排表會(huì)太長(zhǎng)，檢索時(shí)比較合并的開(kāi)銷就大；粒度大了，組合空間就會(huì)過(guò) 于龐大，而每條鏈又會(huì)過(guò)于稀疏。對(duì)中文文檔而占，通常采用詞為基本單元。 為了解決覆蓋率問(wèn)題，【1 4 】構(gòu)建了一組適用于檢索系統(tǒng)的詞典，包括中文詞典、英 文詞典、以及一部特殊詞典，其中包括2 6 個(gè)英文字母、部分常用的字母組合、1 0 個(gè)阿 拉伯?dāng)?shù)字，部分可能代表年份的4 位阿拉伯?dāng)?shù)字等，這樣所有可能在文檔中出現(xiàn)的組合 都可以分解為詞典中的元素1 1 7 。 對(duì)輸入的每篇文檔，處理之自f 通常需要經(jīng)過(guò)一系列的預(yù)處理，包括編碼轉(zhuǎn)換、字符 集轉(zhuǎn)換、去掉h t m l 標(biāo)簽等；特別的，對(duì)中文文檔來(lái)說(shuō)，還要進(jìn)行分詞。關(guān)于分詞的問(wèn) 題，我們將在第五章咀做進(jìn)一步的討論。 2 3 3 索引合并 基于排序的索引算法的最后一個(gè)過(guò)程是臨時(shí)索引的合并。由于每個(gè)臨時(shí)索引都是有 序的，因此可以采用多路歸并的技術(shù)，例如堆排序。l s v p 對(duì)多個(gè)中間排序結(jié)果的合并 就是一個(gè)典型的例子( 在具體實(shí)現(xiàn)上，【1 5 j 斫t j 用并行的讀寫以提高資源利用率) 。 怕?lián)y(tǒng)計(jì)，文檔集合中關(guān)鍵寧的數(shù)1 ：1 跟文檔集合的大小線性相關(guān) 1 ，中文分訶胄一個(gè)特點(diǎn)：訌1 典町以足同定的如果訶典中包括了所自學(xué)寧詞，則收采的例匯自然町以破切分，未出現(xiàn) 的詞則被切分為多個(gè)單字誡一雖然這是( 語(yǔ)言學(xué)t ) 錯(cuò)誤的分訓(xùn)結(jié)震，但不影響榆索的結(jié)果( 假設(shè)索弓l 系統(tǒng)和檢索 系統(tǒng)使用n j 樣的詞典，贓q 未收錄的詞刨捧表町以通過(guò)合并每個(gè)學(xué)，側(cè)的倒持表柬掰到) 9 中固l 學(xué)院碩 學(xué)位論支大規(guī)模中支文本柃蠡中的盤性能索引研究 i 門并時(shí)所需要的取最小值的操作i t 以利用最小堆柬實(shí)現(xiàn)，取出后需要( 代價(jià)為 0 0 0 n ) ) ，以滿足最小堆的性質(zhì)。 【1 】中描述了一種i n - p l a c e 的多路歸并方法，以避免普通歸并需耍兩倍臨時(shí)磁盤空間 的缺點(diǎn)( 臨時(shí)文件+ 倒排文件) 。其基本思想是，把倒排表寫到臨時(shí)文件中：由f 內(nèi)存緩 沖區(qū)的存在，總是可以在臨時(shí)文件中找到放置輸出的位置。為了產(chǎn)生最終的輸出，還需 進(jìn)行一次輪換，以保證邏輯順序與物理順序的一致。 2 3 本章小結(jié) 本章簡(jiǎn)要介紹了各種常見(jiàn)的索引生成算法，并著重介紹了罄丁二排序的算法。在下一 章咀，我們將分析索引流程中備個(gè)階段的時(shí)間丌銷，以揭示索引構(gòu)建的瓶頸所在，并提 出相應(yīng)的解決方案。 1 0 第三章索引開(kāi)銷分析 很多文獻(xiàn)【4 1 【1 4 j 都提到了，在生成索引的各個(gè)階段，分折足最耗時(shí)的，對(duì)中文尤甚。 分析階段究竟占整個(gè)流程的多大比重? 它又在哪些操作上耗時(shí)呢? 3 1 索引流程的實(shí)現(xiàn) 我們實(shí)現(xiàn)了一個(gè)簡(jiǎn)單的索引系統(tǒng)”，有兩個(gè)參數(shù)：d o c s i z e ( 待索引文檔集合的大小) 和b u t s i z e ( 每一次處理的文檔大小) 。流程如下： 0 初始化：a l l s i z e = 0 1 流水線第一級(jí) a )如果a l l s i z e = d o c s i z e 索引過(guò)程結(jié)束 b 1讀入b u f s i z e 人小的文檔，a l l s i z e + = b u f s i z e 2 流水線第二級(jí) a )對(duì)剛讀入的每篇文檔 l 分析文檔”：分詞查詞典、記錄笑鍵字j d 以及位置信息 n 對(duì)剛分析過(guò)的文檔 1 按芙鍵字i d 排序以統(tǒng)計(jì)詞頻” 2 把天鍵字的文檔內(nèi)信息( 詞頻、位置列表) 連同文檔信息暫存到緩沖區(qū)中2 1 b )對(duì)緩沖區(qū)按照戈鍵字i d 和文檔編號(hào)進(jìn)行排序 3 流水線第三級(jí) a ) 把緩沖區(qū)寫到臨時(shí)的索引文件中去2 4 轉(zhuǎn)到1 5 。對(duì)所有的臨時(shí)文件，執(zhí)行多路歸并 可以看到，如果不考慮第5 步的合并操作的話，整個(gè)索引流程由1 3 的 b u f s i z e d o c s i z e 次循環(huán)組成，分別完成讀文檔、分析文檔、寫( 臨時(shí)) 索引的操作。進(jìn) 一步觀察可以發(fā)現(xiàn)，這三個(gè)步驟使用不同的資源部件，讀寫操作主要涉及磁盤i o ，而 分析是主要依賴c p u ，因此它們存在重疊的可能性( 采用流水線的“并行方式”2 3 ) 。有 珥實(shí)際上足一個(gè)完整的檢索系統(tǒng)的一個(gè)子模塊 如果足h t m l 頁(yè)面首先要去標(biāo)簽 統(tǒng)計(jì)訓(xùn)頻也叮以在分析階段完成不過(guò)這就需安擴(kuò)充詞典結(jié)構(gòu)以便進(jìn)行計(jì)數(shù)，還需提供j l ；l 歷功能以便在處理新的文 h 之前清空計(jì)致器我們使用的足僅提供關(guān)鍵寧和i d 雙向映射功能的最簡(jiǎn)單的詞典結(jié)構(gòu) 2 1 緩沖區(qū)由一系列= o l 組構(gòu)成( 關(guān)鍵寧i d 、文檔編弓，文檔內(nèi)信息 ) 由于文檔內(nèi)信息中的位冒佇息足變長(zhǎng)的，通 筇保存旮另外的緩沖區(qū)中，蘭幾組中僅包含一個(gè)指針 盤為，簡(jiǎn)化實(shí)現(xiàn)，內(nèi)存中的緩沖隨以及寫到磁盤上的f 臨時(shí)索引都沒(méi)有進(jìn)行b 縮，因此緩沖區(qū)要比b u t s i z e 丈 囂j 此相對(duì)照，我們把奉章的流程稱為。串行方式 1 1 中圃f 學(xué)院碩士學(xué)位論文大規(guī)模中支史奉榆采中的高竹能磊l 研究 關(guān)流水線性能的分折，我們將在下一革i f 細(xì)闡述。 針對(duì)中英文的不剛特點(diǎn)，系統(tǒng)中使用了中英文兩部典。對(duì)英文詞典，我們又把詞 匯分成了兩部分：對(duì)最常用的3 0 0 0 個(gè)英文詞匯構(gòu)造一個(gè)核心淵典，具體束說(shuō)足利用l i n u x 下的g p e f f 工具，預(yù)先構(gòu)造了一個(gè)完莢h a s h 函數(shù)，它能夠?qū)崿F(xiàn)從( 核心) 謝匯到整數(shù)i d 的無(wú)沖突的映射( 即單射) ；對(duì)非核心瀏匯，構(gòu)造一個(gè)普通詞典，采用的數(shù)掘結(jié)構(gòu)是( 仃 沖突的) h a s h 表，對(duì)沖突的h a s h 值則進(jìn)行進(jìn)一步的二分折半查找。對(duì)中文詞典，我們 又有不同的實(shí)現(xiàn)方案( h a s h 表、t i l e 樹(shù)、雙數(shù)組t f i c 樹(shù)) ，在第五章咀會(huì)有更詳細(xì)的描 述。 在分析文檔之前，通過(guò)預(yù)掃描固定大小的文檔片斷( 例如1 k 字節(jié)) ，統(tǒng)計(jì)各類字符 出現(xiàn)的百分比，來(lái)簡(jiǎn)單的判定文檔采用的字符集( 主要關(guān)心u sa s c i i 和g b2 3 1 2 ) ， 從而決定足調(diào)用英文分析部件還是中文分析部件“。 3 2 索引的性能測(cè)試 實(shí)驗(yàn)環(huán)境中包含兩臺(tái)機(jī)器： 表3 1 實(shí)驗(yàn)平臺(tái) c p u 內(nèi)存操作系統(tǒng) l 機(jī)器a 1 g 1 2 5 6 ml i n u x 2 4 9 【機(jī)器b 2 g 4 4 gl i n u x 2 4 9s m p 用來(lái)建索引的中文文檔采用復(fù)旦大學(xué)的語(yǔ)料，該語(yǔ)料本來(lái)是用于二分類聚類的，包含 1 1 4 m 的訓(xùn)練文本和1 1 6 m 的測(cè)試文本2 5 。 本章測(cè)試用的中文詞典包含7 5 7 8 4 個(gè)詞條。分詞過(guò)程中不更改詞典，即采用固定詞 典的策略。詞典結(jié)構(gòu)使用分詞效果最好的雙數(shù)組t i l e 樹(shù)。有關(guān)訶典的具體特性將在第五 章描述。 3 2 1 資源的利用率 我們首先來(lái)看一下在索引的構(gòu)建過(guò)程中系統(tǒng)資源的利用情況。測(cè)量的方法是：首先 在一個(gè)終端啟動(dòng)索引程序，然后在另外一個(gè)終端利用l i n u x 下的s a r 命令來(lái)收集系統(tǒng)信 息2 6 。 下面是機(jī)器a 的資源利用圖( b u f s i z c = 2 5 m ) ： m 在中文分析器中遇到英文年詞( 1 f 雙字節(jié)7 符序列) 還足壁盤找英文詞典的 罄該語(yǔ)料由1 9 6 3 7 個(gè)1 x r 文件組成，最小的文件僅肯7 8 個(gè)7 節(jié)，最大的文件5 3 m r 均大小為1 5 k ，菇占用磁盤宅 問(wèn)3 3 3 m t 實(shí)硒也含的字節(jié)效為1 9 6 m 當(dāng)d o e s i z * 丈 語(yǔ)料棠合的大小的時(shí)候，葷新從第一個(gè)文件開(kāi)始讀起 拍鈕f 命自兩個(gè)參數(shù)一個(gè)足每次采樣的周期，一個(gè)采樣的次數(shù)；該命令將記錄d 每個(gè)周期內(nèi)系統(tǒng)資源的利用情況( 這 單上籃關(guān)注c p u ( u ) 和i o ( - b ) 的活動(dòng)) 1 2 第二節(jié)索0 i 流程簡(jiǎn)介 圖3 1 機(jī)器a 的資源利用翠 左邊一列( a 、c ) 是以1 秒鐘為間隔，連續(xù)采樣1 0 0 次( 1 0 0 秒) 的結(jié)果，右邊一 列( b 、d ) 是以5 秒鐘為間隔連續(xù)采樣3 0 次( 1 5 0 秒) 的結(jié)果。每一列又分為上下兩 個(gè)圖，上圖( a ，b ) 為c p u 的利用率( u s e r 、s y s t e m 以及i d l e 分別表示c p u 處 于用戶態(tài)、核心念以及空日j 狀態(tài)的百分比) ，下圖( c 、d ) 為i ，0 的讀寫速度( 每秒鐘 讀寫的字節(jié)數(shù)) 。每個(gè)圖中橫軸表示采樣周期的序號(hào)，縱軸為相應(yīng)利用率的指標(biāo)。 通過(guò)縱向的比較可以看出，c p u 的波谷2 - 波峰正好對(duì)應(yīng)f o 的波峰波谷，二者存在 互補(bǔ)的關(guān)系。這正好反映了在串行方式下，各個(gè)資源部件存在周期性的間歇，彼此相互 等待( 在u s e r 的兩個(gè)波峰之間，c p u 絕大部分處于i d l e 狀態(tài)) 。另一方面，應(yīng)該看到， c p u 在相當(dāng)一部分時(shí)間里( 至少占1 2 ) 都是接近滿負(fù)荷運(yùn)行的( u s e r 接近1 0 0 ) ， 這說(shuō)明流水線的第二級(jí)( 即分析階段) 為整個(gè)索引過(guò)程的重點(diǎn)。 橫向來(lái)看，右邊的圖( b 、d ) 相當(dāng)于將左邊的每五個(gè)點(diǎn)合并為一個(gè)點(diǎn)，因此圖像不 如左邊( a 、c ) 的平滑。從a 圖來(lái)看，分析的周期2 8 大約在1 0 秒附近，對(duì)應(yīng)b 圖的2 個(gè)采樣點(diǎn)，即每個(gè)波峰頂端最尖銳的部分。i o 的周期大約在3 秒左右，由于每個(gè)循環(huán) 的寫操作的后面是下一個(gè)循環(huán)讀操作，因此，在c 圖里，讀寫的峰值都是相鄰的；而d u s e r 的波谷之所以沒(méi)有完全降為0 ，足因?yàn)樽x，丐也利用c p u 的操作：前者測(cè)試文檔編碼，后名找j i ；昂小三幾紐( 實(shí)現(xiàn)有關(guān)) 荔n 提到讀、寫、分析的。周期”時(shí)，我們指的足每個(gè)階段的持續(xù)時(shí)| 可( 即僅考慮波峰) ，l 劬小是通常慮義上的兩個(gè)波 峰之間的時(shí)間( 波峰+ 波谷) 1 3 中國(guó) i 學(xué)院瑣 學(xué)位論炙人規(guī)模中支支奉榆泰中的島性能索引研究 圖的采樣周期大f 這個(gè)值，所以看到的圖像足重合的。比較讀寫區(qū)域的面積，可以發(fā)現(xiàn)， 寫的字節(jié)數(shù)要丈f 讀的字節(jié)數(shù)，這跟我們的臨時(shí)索引沒(méi)有壓縮有關(guān)2 9 。 接下束看一下b 機(jī)器上的資源利用圖( b u t s i z e = 3 2 m ) ： 圖3 2 機(jī)器b 的資源利用率 a 、c 對(duì)應(yīng)以1 秒鐘為周期采樣1 0 0 次( 1 0 0 秒) ，b 、d 則為以5 秒鐘為周期采樣 6 0 次( 3 0 0 秒) 。與單c p u 的機(jī)器a 上類似，c p u 和加l 都呈現(xiàn)明顯的周期狀態(tài)。不同 的是，在機(jī)器b 上，由于存在多個(gè)c p u ，可以使單個(gè)c p u 的利用率比較飽滿3 0 ，i d l e 從來(lái)沒(méi)有超過(guò)7 5 ( 在某些點(diǎn)上，u s e r + s y s t e m 甚至超過(guò)了2 5 ) 。另外一個(gè)明顯 的區(qū)別是，在f o 的利用圖( c 、d ) 哩，大部分的磁盤活動(dòng)為寫操作，讀操作基本上沒(méi) 有在圖中反映出來(lái)兒。與a 機(jī)器上類似，分析3 2 m 文檔需要1 0 秒左右；不同的是，寫 周期大概在1 秒左右( 僅考慮峰值) ，讀周期小于1 秒3 2 3 2 2 階段開(kāi)銷分析 我們已經(jīng)通過(guò)資源利用圖對(duì)索引的開(kāi)銷有了大致的認(rèn)識(shí)，接下來(lái)就需要進(jìn)行量化的 分析了。我們采用的手段是給每個(gè)階段記時(shí)( 使用l i n u x 下的毫秒時(shí)鐘) ，考察其在整個(gè) 囂對(duì)2 5 0 m 的文檔進(jìn)行索引( b u 6 i 辨= 2 5 m ) ，朱脈縮的包含位胃信息的1 3 個(gè)臨時(shí)索引共占開(kāi)i5 1 5 m 的空同 m 我們把4 個(gè)c p u 下的2 5 卜j 單c i u 下的1 0 0 相對(duì)應(yīng)。 ”這或許罪磁盤參數(shù)自關(guān)；另外，由j _ 我們反復(fù)的讀取h j 一批史檔，系統(tǒng)的緩存也起到r 很人的作用。 記這罩的讀寫周期井小完傘對(duì)府讀階段的時(shí)間( 凼為每個(gè)階段除r1 1 0 活功之外硅自c p u 的操作) ，根據(jù)調(diào)試輸出 ；j l 示。讀階段耗時(shí)1 秒山q 階段耗時(shí)8 秒( 該小一斂的現(xiàn)象僅n 機(jī)器bl 舭祭到) 。 1 4 第一二爭(zhēng)索0 l 流程簡(jiǎn)介 過(guò)程中所占用的百分比。 在大的尺度上，我們針對(duì)讀階段、分折階段和寫階段進(jìn)行了記時(shí)( 對(duì)應(yīng)算法的步驟 l 3 ) ，此外在分析階段的內(nèi)部，還記求分詞階段、緩沖階段3 3 和排序階段的開(kāi)銷( 對(duì)應(yīng) 算法步驟2 的a l 、a 2 和b ) 。 奪先來(lái)看機(jī)器a 上的結(jié)果： 圖3 3 機(jī)器a 的階段對(duì)比 a e 五個(gè)圖分別反映了當(dāng)d o c s i z e 為1 0 m 、5 0 m 、l o o m 、1 5 0 m 和2 5 0 m 3 4 的時(shí)候， 讀、分析、寫三個(gè)階段累積時(shí)間的對(duì)比。其中每個(gè)圖的橫軸是b u f s i z e ，縱軸是累積時(shí)間 站緩沖步驟中遷包含一個(gè)| 非序的過(guò)程( 用束統(tǒng)計(jì)訓(xùn)頦) ，r 耍驗(yàn)中的記時(shí)信息顯示，該過(guò)程占整個(gè)緩沖步驟