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

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