（计算机应用技术专业论文）大规模中文文本检索中的高性能索引研究.pdf

太蕊攫孛丈鬟盎控素中鼹商牲鼗霞l 麟戆= 摘要 摘要 涟罄笠联酾土绱息瞧举断增长枯跨蘸登龉，缝豢累缝，特澍是母文文零黢紫系缝， 楚枢蹙裂a 卷j 越泉越多豹关注。 索g l 跫检索系绫必幂鼙争熬缀或部势，照捡囊系筑搓供抉逮囊谗服务麓美毽。蜒撵 支替照丈勰摸稳索惹统最嚣趣的索g l 影式。然豫，通常撼酝_ f ，索；f 鹩鞫建，鞠侧撵文 件豹生成，是一个 # 常耗时麴避程，为了逡墩大规模的文采检索往务。豁必要研究女n 恢 鞫建襄g 魏手段。 通过辩索g i 迸攫静骞个除陂进行努辑，零文措怒，道鬻熬豢； 算法效犁攀搿的奎蘩 原因霄二：1 ) c 甲u _ 搦i o 部棒捆豆等待，使穆系统资源的利用率不裹；2 ) 文戡分橱阶 戳蹙整个索 i 过程中韵瓶颈，特别的，辩中文文本丽言，静词是主要的开销。 铃霹第一个睡遂，辜文霞串孬静豢；l 流稳中剐a 渔瘩缝瑟拇，援商了蠹源蘸终热并 行程艘，进而缩短侧捧文律的生成时闻；在此纂礁t ，文中还比较了流水绒结构在幂耐 参数下的性能差摊。 嚣霹嚣：令簿蘧，嚣叛鬻月 愆纯鼢爵薅结构，虢鞠终母文静分 霹遽发，烈蕊达蚕g 减 少分析阶段靖辅聒销前霹弱：程拢较了a 种常凳静诵冀绪约之嚣，文中攒出，鏊予竣数 缀辫的褥典结梅燕麓捷索 i 遴度静有效荦段。 实验袭甥，综台使罔致上醒释方法，哥馘健索 l 的漶澄怒商签。鼹律盼，我稻对 串支t x t 支静静最侠索；l 蘧寝霹遮豁馘字斟黪， 芙穗褥：鼹臻文捧f 紫 & 流水统；努诃 黢数蕴骶酶褥 疆 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 声明 我声明本论文是我本人在导师指导下进行的研究工作及取得的研究成 果。尽我所知，除了文中特别加以标注和致谢的地方外，本论文中不包含 其他人已经发表或撰写过的研究成果。与我一同工作的同志对本研究所做 的任何贡献均已在论文中作了明确的说明并表示了谢意。 作者签名：桨嘉日期：2 0 。蹈竹骨二f 8 论文版权使用授权书 本人授权中国科学院计算技术研究所可以保留并向国家有关部门或机 构送交本论文的复印件和电子文档，允许本论文被查阅和借阅，可以将本 论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编本论文。 ( 保密论文在解密后适用本授权书。) 作者签名：米喜 导师签名：弓斌 日期：力珂中j 引言 随着互联网应用的普及，人们町以获得的数字信息也是越柬越多。根据中国互联网 络信息中心( a q n i c ) 在今年1 月份发白的第卜五次中国互联网络发展状况报告1 显 示：我国境内注册的网站数目已多达6 6 万，国际出口的带宽总量高达7 4 g ；3 9 1 的用 户的主要上网目的足获取信息，6 5 o 的用户经常使用搜索引擎。町以预见，随着时问 的推移，将有更多的信息出现在网络上，而用户对信息的需求也会不断的增加。 面对大量的数据，要从中找出所需的信息，就要借助于检索技术。对检索用户而言， 就耍把自己的检索需求表达出来( 例如若1 二个关键词) 并提交给检索系统。检索系统要 提供枪索服务，首先要有待检索的数据源，通常足大量文档的集合。一种很直观的检索 方案是，对集合中的每个文档，检查每个关键字是否出现，并按其问的逻辑关系进一步 判断是否返回。但足，尽管存在线性的扫描算法( 关键字匹配) ，由于文档空问实在是太 大了，用户不得不忍受超长的响应时问。既然在线扫描行不通，检索系统就需要借助于 某种机制，把在线的时间上的负担转移到离线的空日j 上去。这种机制就是索引。 1 1 索引的结构 概念上讲，索引可以看成是一个巨大的二维矩阵( 位图) ：行代表所有的关键字，列 对应所有的文档，每个元素则表示关键字是否在文档中出现。矩阵的列向量可看做文档 的向量化表示，即文档中出现了哪些关键字；行向量则反映了关键字在文档集合中的分 布这正是在线扫描所期望的结果。所以，如果事先( 离线) 收集到这些信息，在线 检索就能在合理的时间内响应用户的请求。典型的情况足：对请求中每个关键字，从索 引中得到相应的文档列表( 即行向量) ；再根据关键字之问的逻辑关系进行向量的合并； 然后根据一定的准则进行相似度排序，将最相关的若干文档及其信息返回给检索用户。 然而，这种位图的表示方法需要巨大的存储空间。特别的，对于自然文本而言，关 键字的分布是极其不均衡的：占词汇表很小一部分的高频词几乎在所有的文档中出现， 而相当一部分的词是仅出现在极少数的文档中的低频词。这意味着，在索引矩阵中，只 有少数的行向量比较饱满，而大多数的行向量则比较稀疏。列向量也存在类似的主题相 关的稀疏问题。因此，位图矩阵需要压缩。于是，就产生了另外一种索引结构：倒排文 件( 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 的实现机制庙包括后缀数组( 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 由于丈多数捡 囊系统的索引都采用倒排文件实现( 特剐靠人规模致姑童的情况下) ，闪此。为，叙述卜的方便，奉支将把索引和倒捧 文件等w 起束 1 中陶f i 学院碘 学位论丈人舰模中空支奉柃采中的岛性能索引研兜 足矩阵行向晕的，b 缩表示：它实际上足一个文档列表( p o s t i n g l i s t ) ，在该列衷的每个节 点文档( p o s t i n g ) 中，该关键字至少出现( 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 协 ，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 倒排文什的结构 倒排文件的大小通常和原始文档集合在同一数量级。本质上，每个倒排表足一个变 长的记录，整个倒排文件是一个变长记录的集合。如何组织这些变长记录? 不同的组织 方式意味着不同的文件大小，不同的空间利用率，更重要的是不同的访问效：蕃和更新代 价。 除了存储开销外，倒排文件的生成代价也足较大的。为了尽可能的加快在线检索的 响应速度，倒排文件需要事先采集好关键字和文档的统计信息( 统计对象的选取和粒度 跟检索时用的检索模型密切相关) ，即至少要对整个文档集合进行一遍扫描。整个过程可 以看作是先逐文档构造倒排矩阵的列向璧，然后再依次将行向黾写入倒排文件，如同作 了一次“转置”运算4 。由于倒排文件通常是离线生成的，它的时自j 丌销常常被检索系统 忽略。 倒排文件的建立过程会生成一个全局词典( v o c a b u l a r y ) ，其中记录了扫描的过程中 遇到的关键字。由于倒排文件很大，通常无法一次载入内存；只能等到检索时处理某关 键字时，再从磁盘上读入相应倒排表。由于倒排文件足变长记录的集合，要随机访问任 意倒排表，必须事先知道每一个的偏移位置。这个定位信息一般作为词典中每个词条的 一部分。词典的规模一般较小，能够次装入内存并常驻，供检索时使用。 1 2 本文的主题 倒排文件是检索系统必不可少的组成部分，它在很大程度上也限定了检索系统所能 够达到的最大性能。囡此，对倒排文件的研究一直是检索领域的热点5 。随着网络应用的 3 摘白【1 3 】 “倒捧文件”的名4 ，由柬。 5 有关例捧文件的研f 究，土萱分为索0 l 和拎索两大类前苦吉垂考虑倒捧文件自身的性质，石肯关注例排文件耐古洵 r 能的影响只体的i 兑前省讨 究的f u j 题包括：如何减少倒持文件的人小( 索0 l 环缩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 一圆一 一一 第一帝相关研究介绍 普及，对舱索系统( 特别足搜索引擎) 的要求也与f 1 俱增：既要索引越束越多且不断变 化的信息，又耍保证良好的并发性和响应速度。冈此如何优化倒排文件组织，改莳检索 算法、提高枪索系统效率成为一个畦要的研究课题1 4 1 。 时也必须看到，随着文档集合的规模不断扩大，倒排文件的生成丌销问题也越柬 越突出。根据t r e c 2 0 0 4 6t e r a b y t et r a c k 的报告，对4 2 6 g 的数掘进行索引，十几家参赛 单位的耗时从1 7 个小时到几百个小时不等。7 此外，索引的生成速度也直接影响了索引的更新速度。大多数情况下，柃索系统采 用最简荦但也足非常实用的重建索引的策略。即使采用更快捷的合并更新的策略，由于 合并过程足构建过程的自然延续，因此更新的效率都受限丁= 生成速度。 通常的枪索系统至少包括采集系统、索引系统和查询系统三个部分。采集系统用来 获得待处理的文档，它跟索引系统之间是典型的“生产者一消费者”关系。在b r 用带宽 不断增加、采集技术不断改进的情况下，如何使得索引系统跟得上采集器的步伐，也足 检索系统亟需面对的一个现实问题：更新速度跟不上，用户只能检索到过时的信息。 鉴于以上原因，本文将着重讨论如何加快倒排文件的生成。 在下面的章节里，本文将指出： 普通的串行索引算法对资源的利用并不充分；通过引入流水线结构，可以提高 资源的利用率，进而缩短索引的构建时日j 。 文档分析是生成过程中最慢的环节；通过采用基于双数组t r i e 树的词典结构， 可以加快分析，进而加快索引的生成速度。 1 3 内容的安排 论文的组织如下：第二章介绍索引构建的一般流程；第三章将对各个步骤的丌销进 行详细的分析；第四章将专门讨论并行索引，特别是流水线结构对索引性能的改善；第 五章则从分词的角度来讨论如何加速索引；第六章简要的介绍使用倒排文件的检索系统； 最后给出总结和展望。 速度( 索引压缩，索引结构优化【1 】【4 】) ，如何利用多节点分布j 捡索( 索引分布1 6 1 1 1 ) 等这些研究点都不足孤立的， 例如：索引压缩的目的即是为了减少倒捧文件的大小，也同时减少r 检索时i o 的开销；分布式p - , c a t 即可以用于检索， 也町以用于索引的创建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 索引算法简介 可以想象，如果有足够大的内存，便可把整个倒排文件( 甚至是索引矩阵) 装入， 那么构建的代价基本上就只由分析步骤决定( 统计文档内训汇的分布) 。然而内存总是有 限的，如果完全依赖于操作系统的虚拟存储系统，而不是有意识的管理磁盘i 0 。频繁 的缺页将会大大的降低系统的性能【1 】。 【1 1 中介绍了多种倒排文件的生成算法：基于内存的，基于排序的( 基于磁盘的) ； 对临时文件进行压缩的，对内存中的倒排表进行压缩的；对全部文档仅扫描一遍的，需 要预先扫描一遍的9 ；普通多路归并的，就地( i n p l a c e ) 多路归并的等等。这些算法， 对内存空间、临时磁盘空间的需求是各不相同，效率也f 差万别。它们大多数足对基于 排序的算法的某种改进，或是针对特定资源约束的折中。事实上，基于排序的算法已经 成为了构建索引的标准算法，稍后我们将详细介绍。 【1 3 j 哩也对现存的构建倒排文件的算法进行了总结，并大体上可以基于内存的、基 于磁盘和和基于排序的三类。 简单的基于内存的方法实际上就是引言中提到的索引矩阵法，它需要对文档集合进 行两遍扫描。第一遍用来确定关键字和文档的数目，以便分配一个空的二维矩阵( 关键 字数文档数) ；第二遍扫描的时候，才真正进行先列后行的填充和输出( 可按行为单 位进行压缩) 。显然这种方式需要庞大的内存，因而足不合适的。该方法的一个变种是把 每行用链表的形式表示( 因而只需要一遍扫描) 。然而链表上的存储空间不是连续的，对 链表的随机访问会造成大量的缺页。 另外一种基于内存的算法利用索引压缩束减少对内存空间的需求。它也是一个需要 扫描两遍的算法：在第一遍扫描中，形成词典以及粗粒度的统计信息( 例如词频) ；在第 二遍扫描之静，先分配一块内存区域，并按关键字进行分割( 倒排表长度已知) ，扫描时 直接填充到相应的内存位置。由于连续存储，节省了指针的存储开销。当然，内存空间 毫无疑问，使用分布式的策略町以加快索引的构娃过程。即使自收集伞局信息的额外负担( 这个负担足文档集合大 小的次线性函数，相对于索0 l 生成代价( 线性对数) 来说璺小1 1 0 1 ) 。小过，奉文只讨论单个节点上的加速f 段 为，获得统计信息以利于优化组织内存 5 中国 学院坝1 学位论支人埘模中文史奉柃采中的扇廿能索0j 研究 的大小还是相当町观的，b r 以盘第一遍中先确定每个倒排袭在压缩方式下的最大长度1 0 。 填充时直接采用爪缩表示。该算法的主要缺点足扩展性不强，只适合中锋规模的文档集 合。一种改进是把预分配的空i h j 转移到磁盘上，并根据可用内存划分文档集合，分批处 理；当内存饱和时，合并到磁盘上( 也就是说，磁盘上每个倒排衷足逐批填充的) 。很明 显，这种改进需要在第一遍扫描中搜集更多的信息。 基于磁盘的基本思想足把倒排表放在磁盘上而不足内存中。属于同一个倒排表的节 点在临时文件中通过指针链接起来；当所有文档扫描完毕后，以词典的顺序遍历所有的 链表，并进行压缩，保存在新的文件中。该方法的劣势在于需委额外的磁盘空间束保存 临时文件，并且在生成索引时，需要大麓的磁盘定位操作。 至于基于排序的算法，我们将在下一节进行介绍。 2 2 基于排序的算法 在基于排序的索引构建算法中，假设可用内存要比最终的索引小，即无法一次处理 完所有的文档，只能分批进行。因此，算法上要生成临时索引以及合并临时索引两部分 组成。自口者又涉及到以下操作：在内存允许的自f 提下，读入若于文档，调用分析算法统 计文档内的信息1 1 并暂存在缓冲区中；等到缓冲区满的时候，再按关键字排序输出到临 时文件。 今 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 ”表现为一系列的形如关键宁，立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 ) 的数据结构【1 2 1 ”。 分析所要完成的工作就是识别文档内的关键字并进行统计。【1 2 】考察了各种常用的 数掘结构在该任务上的表现：树、t i l e 树、h a s h 表以及各种改进。文档的属性，特别是 词汇分白的不均衡，将大大影响各种结构的性能：如果能够为高频词汇提供快捷的访问， 那么即便影响其它词的效率也是值得的；另一方面，如果词汇分布的比较均匀，就没有 必要来对结构进行动态调整。 二分查找树( b s t ) 足一种常用的树结构，其性能依赖于关键字的插入顺序。可以 假定，大多数文档并非足按照关键字排列的，因此平均的查找代价是对数一级的，而非 最坏情况下的线性。另外，常用词很有可能在文档中较早出现，因此它们会被存储在树 的较高的层次上，因此访问代价很小；同时它们又在文档中大量出现，且本身长度通常 又较短，进一步降低了整体的代价。 b s t 还有一些变种，如a 。树、红黑树，用束在插入后调节树的平衡。虽然可以 将最坏情况下的查找代价提升到对数时间，但是由f 树结构的重新组织，常用词未必就 保存在树的高层。但另一方面，由于大部分足常用词，上要的操作足访问而不是插入， 因此平衡树结构调整的丌销可以限定在一个合理的范围。 s p l a y 树是b s t 的另外一个适应性变种，它在每次访问的时候修改树结构，以便使 被访问的节点向根结点靠近一些( 通过一次旋转) ，其结果就是常用诃聚集在根结点周围， 这对普通文本来说是很好的性质但是过多的旋转将损害其带来的好处，一种改进是每 隔k 次访问才旋转一次。 f a b ( f r e q u e n c y - a d a p t i v eb s t ) 树赋予每个节点一个计数器，每次访问加1 ，并通 过旋转来使得计数器满足堆( h e a p ) 的性质为了避免计数器溢出以及非常用词的局部 集中分布，可以在根结点的计数器超过某个门限值时，对树中的高频节点进行一次遍历 并减小其计数器，来降低这些节点的“热门程度” 与b s t 及其变种相比，t r i e 树虽然可以获得比较快的访问速度，但是其对空问的需 求较大，为此【1 2 】提出了一种改进的结构：b u i s ft r i e 树。这种结构包含一个标准的瓢e 树结构，只不过叶子节点不再仅对应一个关键字，而是一个可以存储多个关键字的容器 ( 例如二分查找树) 。这样，查找一个关键字的时候，从根结点出发，采用通常的t i l e 树检索算法到达容器，这意味着关键字的前缀将与检索路径相匹配；然后在容器内，再 ”相对的，适台于天数据集的结构( 特别足适应性结构) 如果戍用到小集合上，很有町能拒结构达到r 衡点之前输入 就结束r 此外。纂屿大集合下町以忽略代价的操作。例如初始化时的卒问分配，以及结束前的越历等，在小集合上 尢疑会显著的影响整体性能 7 中【日f 学院硕卜学位论之人l 嫩模中上支奉柃裹中的高能索0 【l 小亢 利用容器本身的检索方法去查找后缀。u r 以看出，容器内的父键字共9 f i i y 缀，因此也就 箝省了存储空阃。当容器中的关键字达到一定数目的时候，叶节点分裂( 即所谓的b u r s t ) ， 在新节点内藿新分配关键字。 除了各种树结构之外，h a s h 表足最常用的一种结构。借助j 二好的h a s h 函数，h a s h 表一般可以获得最好的性能。为了进一步提高性能，口r 以把最近访问的符点移到所在 h a s h 链的头部，这样常用词就聚集在各h a s h 链的头部，仅需要进行少数几次字符串比 较。h a s h 表的不足在于并非按有序的顺序来组织数据。 f 1 2 】比较了各种结构，其结论足：b u r s tt n e 树是最合适的。 2 2 2 全局词典 分析阶段的另一项任务是在备文档之日j 维护一个全局词典1 4 ，每篇文档处理完毕， 文档内的关键字信息就要并入全局词典。词典和分析过程实际上是竞争内存的：词典占 用的内存越多，则每轮处理的文档数就越少，临时索引就越多，归并时甘j 也就越长。虽 然经常假设珂典可以一次性载入内存，还需看到，由于总会有新的关键字出现，因此词 典的规模还会扩大。另一方面，很多关键字仅在某一轮中相对集中的出现少数几次，在 后继的轮次中就没有必要继续保留。 为了尽可能的减少词典占用的空问对构造倒排文件的影响，【1 3 】采用了不在轮次之 问共享词典的策略：在每一轮结束后，将本轮的词表写入临时倒排文件中( 为了能够进 行最后的归并) ，然后清空当自口词典，在下一轮中重新利用这部分空日j 巧。 无论是对索引生成还是在线检索，词典的结构至关藿要。不同的结构有不同的存储 丌销，更重要的足，有不同的查询代价。处理过程中有相当一部分时间是用来定位关键 字的。定位方式的大体可分为两类：基于比较的和基于计算的。比较也足一种操作，只 不过太常用而已。 典型的使用字符串比较的结构就是各种线性表以及树结构。为了加快定位，通常在 结构内部维持一种有序关系或者自适应性，以期减少待比较节点的数目。树结构的性能 通常不理想，很大原因在于关键字要被比较多次。与此相对，t i l e 树的比较粒度降为单 个字符，次数仅由关键字自身长度限定但足t r i e 树的优势是用空问换来的，每个节点 都要维护字母表规模的指针，过度发散会导致空f 可浪费以及多次i o ，因此需要借助辅 助的结构( 如h a s h 表) ，仅包含字母表的某个子集。 基于计算( 非比较) 的方法本质上是寻求一种从词典空问到整数空问的映射。h a s h 文档分析”小节中用到的数据结构也町以著作足一个训典，只不过该词典足局部十每个史挡的特别的，在文 档之问，需要对该数据结构进行荤冒或者清空操作 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 到临时文件以用于最后的归并该方案下关键字并未事九转化为整数删此 棚邻的倒排表对廊相邻的关键字，从由支持关键7 区问a 咖 8 第二营索引赢程简介 函数就是一种映射，只不过存在映射冲突，需要进一步的比较束解决冲突。借助于良好 设计的h a s h 函数，对关键字空问进行一次划分，冲突的概率i r 限定在一个合理的范围， 再辅以某些优化策略( 例如常用词置于链首) ，町何效的减少严均比较次数。 理想的情况下，映射应该是单射，即无冲突的完荚h a s h 1 。完荚h a s h 的构造一般 很耗时问，通常足根掘一个固定的纠表事先计算好；当训表发生变化的时候，需要重新 计算。可以专门针对常用的关键字构建一个完美h a s h ，对其它的关键字采用基f 比较的 结构，从而能够适应词表的扩展( 假设新词都不是常用诃，因此已构造的完荚h a s h 不 需要变化) 。 双数组t i l e 树也是一种基于计算的结构，它实质上足t r i e 树的扁平化表示1 1 8 1 1 1 9 1 ， 逐字符的计算( 即改变下标) 对应着t i l e 树指针的移动。由于仅保留有效的指针，数组 占用的空间要比t h e 树小。与完荚h a s h 类似，双数组t i l e 树也是一种静态结构，适合 于词表固定的场合；当词表变化时，其调整的代价通常比较大。 除了数据结构，词典本身的规模1 6 以及覆盖率等属性也足影响分析效率、效果的一 个重要方面。 新的文档总是会出现新的关键字的，那么词典本身是动态的还是静态的? 动态词典 可以保证文档中出现的关键字都被检索到，但是其规模会不断的增加，可用性会越来越 差。静态词典查找和维护的开销小，却很容易会产生查询失败( 例如字母组合) 。 此外，关键字对应哪种语法单元，足字是词或是短语? 度小时，词典规模会降下 来，但是每个倒排表会太长，检索时比较合并的开销就大；粒度大了，组合空间就会过 于庞大，而每条链又会过于稀疏。对中文文档而占，通常采用词为基本单元。 为了解决覆盖率问题，【1 4 】构建了一组适用于检索系统的词典，包括中文词典、英 文词典、以及一部特殊词典，其中包括2 6 个英文字母、部分常用的字母组合、1 0 个阿 拉伯数字，部分可能代表年份的4 位阿拉伯数字等，这样所有可能在文档中出现的组合 都可以分解为词典中的元素1 1 7 。 对输入的每篇文档，处理之自f 通常需要经过一系列的预处理，包括编码转换、字符 集转换、去掉h t m l 标签等；特别的，对中文文档来说，还要进行分词。关于分词的问 题，我们将在第五章咀做进一步的讨论。 2 3 3 索引合并 基于排序的索引算法的最后一个过程是临时索引的合并。由于每个临时索引都是有 序的，因此可以采用多路归并的技术，例如堆排序。l s v p 对多个中间排序结果的合并 就是一个典型的例子( 在具体实现上，【1 5 j 斫t j 用并行的读写以提高资源利用率) 。 怕据统计，文档集合中关键宁的数1 ：1 跟文档集合的大小线性相关 1 ，中文分诃胄一个特点：讧1 典町以足同定的如果诃典中包括了所自学宁词，则收采的例汇自然町以破切分，未出现 的词则被切分为多个单字诫一虽然这是( 语言学t ) 错误的分训结震，但不影响榆索的结果( 假设索弓l 系统和检索 系统使用n j 样的词典，赃q 未收录的词刨捧表町以通过合并每个学，侧的倒持表柬掰到) 9 中固l 学院硕 学位论支大规模中支文本柃蠡中的盘性能索引研究 i 门并时所需要的取最小值的操作i t 以利用最小堆柬实现，取出后需要( 代价为 0 0 0 n ) ) ，以满足最小堆的性质。 【1 】中描述了一种i n - p l a c e 的多路归并方法，以避免普通归并需耍两倍临时磁盘空间 的缺点( 临时文件+ 倒排文件) 。其基本思想是，把倒排表写到临时文件中：由f 内存缓 冲区的存在，总是可以在临时文件中找到放置输出的位置。为了产生最终的输出，还需 进行一次轮换，以保证逻辑顺序与物理顺序的一致。 2 3 本章小结 本章简要介绍了各种常见的索引生成算法，并着重介绍了罄丁二排序的算法。在下一 章咀，我们将分析索引流程中备个阶段的时间丌销，以揭示索引构建的瓶颈所在，并提 出相应的解决方案。 1 0 第三章索引开销分析 很多文献【4 1 【1 4 j 都提到了，在生成索引的各个阶段，分折足最耗时的，对中文尤甚。 分析阶段究竟占整个流程的多大比重? 它又在哪些操作上耗时呢? 3 1 索引流程的实现 我们实现了一个简单的索引系统”，有两个参数：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 排序以统计词频” 2 把天键字的文档内信息( 词频、位置列表) 连同文档信息暂存到缓冲区中2 1 b )对缓冲区按照戈键字i d 和文档编号进行排序 3 流水线第三级 a ) 把缓冲区写到临时的索引文件中去2 4 转到1 5 。对所有的临时文件，执行多路归并 可以看到，如果不考虑第5 步的合并操作的话，整个索引流程由1 3 的 b u f s i z e d o c s i z e 次循环组成，分别完成读文档、分析文档、写( 临时) 索引的操作。进 一步观察可以发现，这三个步骤使用不同的资源部件，读写操作主要涉及磁盘i o ，而 分析是主要依赖c p u ，因此它们存在重叠的可能性( 采用流水线的“并行方式”2 3 ) 。有 珥实际上足一个完整的检索系统的一个子模块 如果足h t m l 页面首先要去标签 统计训频也叮以在分析阶段完成不过这就需安扩充词典结构以便进行计数，还需提供j l ；l 历功能以便在处理新的文 h 之前清空计致器我们使用的足仅提供关键宁和i d 双向映射功能的最简单的词典结构 2 1 缓冲区由一系列= o l 组构成( 关键宁i d 、文档编弓，文档内信息 ) 由于文档内信息中的位冒伫息足变长的，通 筇保存旮另外的缓冲区中，兰几组中仅包含一个指针 盘为，简化实现，内存中的缓冲随以及写到磁盘上的f 临时索引都没有进行b 缩，因此缓冲区要比b u t s i z e 丈 嚣j 此相对照，我们把奉章的流程称为。串行方式 1 1 中圃f 学院硕士学位论文大规模中支史奉榆采中的高竹能磊l 研究 关流水线性能的分折，我们将在下一革i f 细阐述。 针对中英文的不刚特点，系统中使用了中英文两部典。对英文词典，我们又把词 汇分成了两部分：对最常用的3 0 0 0 个英文词汇构造一个核心渊典，具体束说足利用l i n u x 下的g p e f f 工具，预先构造了一个完荚h a s h 函数，它能够实现从( 核心) 谢汇到整数i d 的无冲突的映射( 即单射) ；对非核心浏汇，构造一个普通词典，采用的数掘结构是( 仃 冲突的) h a s h 表，对冲突的h a s h 值则进行进一步的二分折半查找。对中文词典，我们 又有不同的实现方案( h a s h 表、t i l e 树、双数组t f i c 树) ，在第五章咀会有更详细的描 述。 在分析文档之前，通过预扫描固定大小的文档片断( 例如1 k 字节) ，统计各类字符 出现的百分比，来简单的判定文档采用的字符集( 主要关心u sa s c i i 和g b2 3 1 2 ) ， 从而决定足调用英文分析部件还是中文分析部件“。 3 2 索引的性能测试 实验环境中包含两台机器： 表3 1 实验平台 c p u 内存操作系统 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 个词条。分词过程中不更改词典，即采用固定词 典的策略。词典结构使用分词效果最好的双数组t i l e 树。有关诃典的具体特性将在第五 章描述。 3 2 1 资源的利用率 我们首先来看一下在索引的构建过程中系统资源的利用情况。测量的方法是：首先 在一个终端启动索引程序，然后在另外一个终端利用l i n u x 下的s a r 命令来收集系统信 息2 6 。 下面是机器a 的资源利用图( b u f s i z c = 2 5 m ) ： m 在中文分析器中遇到英文年词( 1 f 双字节7 符序列) 还足壁盘找英文词典的 罄该语料由1 9 6 3 7 个1 x r 文件组成，最小的文件仅肯7 8 个7 节，最大的文件5 3 m r 均大小为1 5 k ，菇占用磁盘宅 问3 3 3 m t 实硒也含的字节效为1 9 6 m 当d o e s i z * 丈 语料棠合的大小的时候，荤新从第一个文件开始读起 拍钮f 命自两个参数一个足每次采样的周期，一个采样的次数；该命令将记录d 每个周期内系统资源的利用情况( 这 单上篮关注c p u ( u ) 和i o ( - b ) 的活动) 1 2 第二节索0 i 流程简介 图3 1 机器a 的资源利用翠 左边一列( a 、c ) 是以1 秒钟为间隔，连续采样1 0 0 次( 1 0 0 秒) 的结果，右边一 列( b 、d ) 是以5 秒钟为间隔连续采样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 处 于用户态、核心念以及空日j 状态的百分比) ，下图( c 、d ) 为i ，0 的读写速度( 每秒钟 读写的字节数) 。每个图中横轴表示采样周期的序号，纵轴为相应利用率的指标。 通过纵向的比较可以看出，c p u 的波谷2 - 波峰正好对应f o 的波峰波谷，二者存在 互补的关系。这正好反映了在串行方式下，各个资源部件存在周期性的间歇，彼此相互 等待( 在u s e r 的两个波峰之间，c p u 绝大部分处于i d l e 状态) 。另一方面，应该看到， 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 秒左右，由于每个循环 的写操作的后面是下一个循环读操作，因此，在c 图里，读写的峰值都是相邻的；而d u s e r 的波谷之所以没有完全降为0 ，足因为读，丐也利用c p u 的操作：前者测试文档编码，后名找j i ；昂小三几纽( 实现有关) 荔n 提到读、写、分析的。周期”时，我们指的足每个阶段的持续时| 可( 即仅考虑波峰) ，l 劬小是通常虑义上的两个波 峰之间的时间( 波峰+ 波谷) 1 3 中国 i 学院琐 学位论炙人规模中支支奉榆泰中的岛性能索引研究 图的采样周期大f 这个值，所以看到的图像足重合的。比较读写区域的面积，可以发现， 写的字节数要丈f 读的字节数，这跟我们的临时索引没有压缩有关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 都呈现明显的周期状态。不同 的是，在机器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 ) 。另外一个明显 的区别是，在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 相对应。 ”这或许罪磁盘参数自关；另外，由j _ 我们反复的读取h j 一批史档，系统的缓存也起到r 很人的作用。 记这罩的读写周期井小完伞对府读阶段的时间( 凼为每个阶段除r1 1 0 活功之外硅自c p u 的操作) ，根据调试输出 ；j l 示。读阶段耗时1 秒山q 阶段耗时8 秒( 该小一敛的现象仅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 ，纵轴是累积时间 站缓冲步骤中迁包含一个| 非序的过程( 用束统计训颏) ，r 耍验中的记时信息显示，该过程占整个缓冲步骤