（计算机应用技术专业论文）化工专业搜索引擎索引技术的研究与实现.pdf

摘要 化工专业搜索引擎索引技术的研究与实现 摘要 随着互联网技术的迅速发展，网络上的资源日益丰富，各类搜索引 擎应运而生，并迅速发展壮大。以百度，g o o g l e 为代表的综合性搜索引 擎搜索范围几乎涵盖了各个领域。但是，这些综合性搜索引擎在检索某一 特定领域的信息时，无论是检索效率还是检索精度都无法满足人们的需 要。为了进一步挖掘某一专业领域的网络信息，发展出了具有领域特点的 专业搜索引擎。 化工专业搜索引擎主要用于检索网络上化工领域相关信息。本文在 深入了解搜索引擎相关索引技术的基础上，对l u c e n e 开源源代码进行研 究与实践，分析了l u c e n e 的系统组织结构、基本数据类型、索引内存结 构、索引数据库的文件结构。深刻理解其索引过程以及索引方式，掌握了 索引权重的控制、索引优化的方法。在此基础上，对源代码进行了创新性 的改进，设计了用多索引器对文档进行索引的机制，有效地缩短了索引时 间，改进了索引库词典文件中词条默认的排序方式，有效地减少了检索的 响应时间，为待索引化工专业文档设置权值，有效地提高了检索化工信息 的精度，创建了有利于化工专业信息检索的索引库。 本文实现的索引器可以快速地为化工文档库建立高性能的倒排索引 库，不仅适用于化工专业搜索引擎，而且适用于化工专业文献检索系统， 对其他专业搜索引擎索引库的建立也有一定的参考作用。 北京化1 ：人学硕十学位论文 关键词：l u c e n e ，索引库，多索引器，排序算法，权值 摘要 t h el 啦s e a r c ha n dr e a i 。i z 棚o n o fi n d e xt e c h n o l o g y i nc h e m i c a ls e a r c he n g i n e a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fi n t e m e ta n dw w w ；t h cr e s o u r c ei l l i n t e m e tb e c o m em o r e 锄di n o r e ，t h e r e f b r e ，m a n yk i n d so fs e a r c l le n g i n eb a s e d o ni n t e m e td e v e l o pq u i c k l y t h eg e n e r a ls e a r c he n g i n e ss u c h 弱( 沁o g l e ， b a i d ua r ev e 巧e x c e l l e n ta tt h e i rs e a r c hf u n c t i o n s ，y o uc a ns e a r c ha l m o s ta l l i n f o m a t i o ni ne v e 巧f i e l d b u tt h e ya r eu n f i t a b l ei nac e r t a i np r o f e s s i o n a lf i e l d i t i sn e c e s s a 巧t od e v e l o pp r o f e s s i o n a ls e a r c he n g i n ei ns p e c i f i c a l l yf i e l di n o r d e rt os e a r c h i n gi n f o m a t i o ne 如c t i v e l y c h e m i c a ls e a r c he n g i n ei so n et y p eo fp r o f e s s i o n a ls e a r c he n g i n ef 研 s e a r c l l i n gi n f o r m a t i o ni i lc h e m i c a lf i e l d i nt h i sp a p e f ，b a s e0 nc o m p r e h e n d i n g r e l a t i v e 1 【i l o w l e d g e a b o u ti n d e xt e c h n o l o g yi l ls e a r c he n g i i l ed e 印l y ，w e a n a l y z ea n dr e s e a r c ht h es o u r c ec o d eo fl u c e n ei na p a c h ef u l l t e x ts e a r c h s y s t e m ，a n dm a s t e rt h es y s t e ms t m c t u r e ，t h eb a s i cd a t at y p e ，t h ei n d e x s t r u c t u r ei i l m e m o r y ，t h es t m c t u r eo fi n d e x f i l ei nl u c e n es y s t e m w | e u n d e r s t a n dt h ep r o c e s so fi i l d e x i n ga n dt h em e a s u r eo fi n d e x i n g ，a n dm a s t e r t h em e a s u r eo fc o n t r o l l i n gi n d e xw e i g h ta n do p t i m i z i n gi n d e x b a s e do nt h e m 北京化j ：人! 学硕十学位论文 r e s e a r c h ，t h ep r o j e c to fi n u l t i - i n d e x e ri s d e s i g n e dt od e c r e a s et h et i m eo f e s t a b l i s h i n gi n d e xe 虢c t i v e l y ，t h ee f i c i e n c yo fs e a r c h i n gc h e m i c a l t e m sc 觚 b ei m p r o v e db yo p t i m i z i n gs o n i l l gp r o c e s so ft e m o fi n d e xl e x i c o nf i l e ，t h e i n d e x e dd o c u m e n t sa r ea d d e dd i 雠r e n tt y p e so fp a r a m e t e r sv a l u e st oi m p r o v e a c c u r a c yo fs e a r c h i n gc h e m i c a l t e r m s ，t h i si n d e xd a t a b a s ei sm o r es u i t a b l ef o r s e a r c h i n gc h e m i c a l i m o r m a t i o n t h i si n d e x e rw h i c hc a ne a t a b l i s hi n v e r t e di n d e xd a t a b a s ef o rc h e m i c a l d o c u m e n td a t a b a s ef i t sn o to l l l yc h e m i c a ls e a r c he n g i n es y s t e m ，b u ta l s ot h e c h e 血c a ld o c u m e n ts e a r c hs y s t e mb a s e do nf u l l t e x ts e a r c h t e c h n o l o g y 7 n l e r c a r ei i n p o r t a i l tr e f e r e n c e sf o ro t h e rp r o f e s s i o n a ls e a r c h e n g i n e t oe s t a b l i s h i n d e xd a t a b a s e k e yw o r d s ：l u c e n e ，i n d e xd a t a b a s e ，m u l t i i n d e x e r ，s o r t i l l g a l g o r i t h m ， b o o s tv a l u e s 北京化工大学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究工作所取得的成果。除文中已经注明引用的内容外，本 论文不含任何其他个人或集体已经发表或撰写过的作品成果。对本文 的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本 人完全意识到本声明的法律结果由本人承担。 作者签名：盗墅 日期：兰丝星：，2 关于论文使用授权的说明 学位论文作者完全了解北京化工大学有关保留和使用学位论 文的规定，即：研究生在校攻读学位期间论文工作的知识产权单 位属北京化工大学。学校有权保留并向国家有关部门或机构送交 论文的复印件和磁盘，允许学位论文被查阅和借阅；学校可以公 布学位论文的全部或部分内容，可以允许采用影印、缩印或其它 复制手段保存、汇编学位论文。 保密论文注释：本学位论文属于保密范围，在土年解密后适用 本授权书。非保密论文注释：本学位论文不属于保密范围，适用本授 权书。 作者签名： 导师签名： 潭芝 日期：兰竺壁：! 日期：垒竺查：亟：2 第一章绪论 1 1 课题相关领域的发展情况 1 1 1 搜索引擎的历史 第一章绪论 早在w - c b 出现之前，互联网上就已经存在许多旨在让人们共享的信息资源，当 时主要存在于各种允许匿名访问的兀甲站点。1 9 9 3 年m a t t h e w 触y 开发了w r o r l dw i d e w 曲w 抽d e r e r ，它是世界上第一个利用耵m l 网页之间的链接关系来监测w | e b 发展 规模的“机器人 ( r o b o t ) 程序。由于专门用于检索信息的r o b o t 程序像蜘蛛( s p i d e r ) 一样在网络间沿超链接“爬行”，因此，搜索引擎的r o b o t 程序有时也称为s p i d e r 程 序。刚开始时它只用来统计互联网上的服务器数量，后来则发展为能够捕获网址 ( u r l ) ，通过它可以检索网站域名l 心。 现代搜索引擎的思路正是源于w | 蛐d e r e f 。随着互联网的迅速发展，使得检索所有 新出现的网页变得越来越困难，因此，在w 抽d e r e r 基础上，一些编程者将传统的s p i d c r 蜘蛛程序工作原理作了些改进。其设想是，既然所有网页都可能有连向其他网站的链 接，那么从一个网站开始，跟踪所有网页上的所有链接，就有可能检索整个互联网。 1 9 9 4 年m i c h a e lm 卸l d i n 将改进的s p i d e r 程序接入到其索引程序中，创建了大家熟知 的l y c o s ，成为第一个现代意义的搜索引擎。除了相关性排序外，l y c o s 还提供了前 缀匹配和字符相近限制，l v c o s 第一个在搜索结果中使用了网页自动摘要，而最大的 优势还是它远胜过其它搜索引擎的数据量。在那之后，随着w 曲上信息的爆炸性增 长，搜索引擎的应用价值也越来越高，不断有更新、更强的搜索引擎系统推出。g o o 酉e 成立于1 9 9 8 年，创始人为美国斯坦福大学的两位博士研究生h 玎yp a g e 和s e r g e y b 咖。g o o 皿e 一词由英文单词”g d 0 9 0 l ”变化而来，表示1 0 的1 0 0 次方的巨大数字，使 用这个词显示了g 0 0 西e 欲整合网上海量信息的远大目标l 引。 1 1 2 搜索引擎的现状 根据中国互联网络发展状况统计报告( 2 0 0 5 p 1 ) 【4 5 】用户在互联网上获取信息最 常用的方法是通过搜索引擎：占7 0 7 。远远高于位于第二位的直接访问已知的网 北京化i ：人学硕十学位论文 站：占2 4 6 。搜索引擎的后起之秀g o o 西e 每天处理的搜索请求已达2 亿次。由此 可见搜索引擎不愧为网络门户。 搜索引擎的发展速度越来越快，在众多的搜索引擎中有一些是比较著名的搜索引 擎，从中文搜索引擎方面，共有十个著名的搜索引擎：百度、中文g 0 0 西e 、新浪、搜 狐、中文雅虎、3 7 2 1 、网易，悠游，天网，北极星。这1 0 种搜索引擎类型多样，各 具特色，检索者在使用时要依据各自不同的特点，选择合适的搜索引擎1 6 j 。 随着搜索引擎的蓬勃发展，现阶段搜索引擎的问题也逐渐的暴露出来。主要的问 题是：( 1 ) 查准率低。多数搜索引擎的检索功能单一，信息加工的深度不够，这导致 信息查询的准确率不高。( 2 ) 检索效率不高。主要问题是数据更新速度慢，查询响应 时间长。( 3 ) 对多媒体信息资源的处理技术不够成熟。目前多数搜索引擎的搜索对象 主要是文本格式，主要原因是搜索引擎的自动排序软件，只能接受这种格式的网页。 能够搜索多媒体信息资源的搜索引擎较少。( 4 ) 专业性搜索引擎较少。专业性搜索引 擎是为专门收录某一行业、主题等的信息而建立的，能够提供专题信息查询服务的搜 索引擎。目前的搜索引擎大多是综合性的，收录各方面、各学科和各行业的信息，在 反映专题或专业信息方面很难做到全、快、精、准网。 1 1 3 搜索引擎的发展趋势 针对目前的搜索引擎提供给用户的不相关信息太多的现状，专业垂直引擎的诞生 解决了这一问题。垂直搜索引擎对特定专业领域或行业的信息进行专业化、深入的分 析挖掘和精细分类，信息定位更精准，可保证专业领域信息的收录齐全和及时更新， 因此得到更多用户的认可，成为搜索引擎的发展方向【8 l 。 垂直搜索引擎是指应用于搜索某一学科领域或某一类信息( 如图像、影像) 的专 业搜索引擎，又称专题搜索引擎、专门搜索引擎，是搜索引擎的细分和延伸。对网页 库中的某类专门的信息进行一次整合，定向分字段地抽取出需要的数据，经过处理后 再以某种形式返回给用户。垂直搜索引擎在提供专业信息方面有着综合搜索引擎无法 比拟的优势【9 ，埘。 4 因此，基于专业领域的垂直搜索引擎开始成为搜索引擎发展的一个新趋势。垂直 搜索引擎采用的基本技术和综合性搜索引擎相似。主要区别是垂直搜索引擎将网页的 非结构化数据抽取成特定的结构化信息数据，然后将这些数据存储到数据库，进行进 一步的加工处理，如去重、分类等，最后分词、索引，再以搜索的方式满足用户的需 求。综合搜索引擎主要是利用蜘蛛程序到网络上爬行，一般按某一特定的周期网页。 垂直搜索引擎同样有一个蜘蛛程序，但该程序只在一些特定的网络上爬行，并不会对 2 第一章绪论 每一个链接都感兴趣。相对来说，垂直搜索引擎的收录范围大大的缩小了，但专业内 容并没有减少。目前，垂直搜索引擎的发展非常的迅速，如比价购物搜索引擎、供求 信息搜索引擎、工作搜索引擎、博客搜索引擎等等【1 1 ，1 2 1 。 1 2 搜索引擎的关键技术和性能评估 1 2 1 信息收集和存储技术 网上信息收集和存储一般分为人工和自动两种方式【1 3 】。人工方式采用传统信息收 集、分类、存储、组织和检索的方法。研究人员对网站进行调查筛选、分类、存储。 由专业人员手工建立关键字索引，再将索引信息存入计算机相应的数据库中。自动方 式通常是由搜索程序来完成的，流行的搜索程序有：r o b o t 、s p i d e r 、h a r v e s t 、p u r s u i t 、 h e r i t r i x 。搜索程序的主要功能是搜索h t e m e t 上的网站或网页。这种软件定期在互联 网上漫游，通过网页间链接顺序地搜索新的地址，当遇到新的网页时，会将页面抓取 到本地磁盘中，对页面内容做索引后存入搜索引擎的索引库中，由此，搜索引擎的索 引库得以定期的更新。一般来说，人工方式收集信息的准确性要远优于搜索程序，但 其收集信息的效率及其全面性低于搜索程序。信息的存储则是根据不同的分析结果和 要求，针对提取的索引和查询目的而进行的。可以采用专用的，也可以采用通用的数 据库。 1 2 2 信息预处理技术 信息的预处理包括信息的格式支持与转换以及信息过滤【1 4 l 。目前，h l t e m e t 上的 信息发布格式多种多样，这就要求搜索引擎支持多种文件格式。从实际的情况看，所 有的搜索引擎都支持h t m l 格式，而对于其他文件格式的支持则不同的搜索引擎有 不同的规定，最多的能支持2 0 0 多种文件格式。一般地说，一个企业级的公用w 曲 站点起码支持4 0 6 0 中文件格式。同时搜索引擎还应具备信息格式转换功能，以保证 不同的格式的数据均能在网络流通。信息过滤也是搜索引擎的一项重要技术。在 l l l l e m e t 上，存在有大量的无用信息，一个好的搜索引擎应当尽量减少垃圾站点的数 量，这是信息过滤要着重解决的问题。 3 北京化l ：人学硕十学位论文 1 2 3 信息索引和检索技术 搜索引擎索引技术主要包括以下几个方面： ( 1 ) 信息语词切分和语词词法分析。语词是信息表达的最小单位，由于语词切 分中存在切分歧义，切分需要利用各种上下文知识。语词词法分析是指识别出各个语 词的词干，以便根据词干建立信息索引。 ( 2 ) 进行词性标注及相关的自然语言处理。词性标注是指利用基于规则和统计 ( 马尔可夫链) 的数学方法对语词进行标注。基于马尔可夫链随机过程的n 元语法统 计分析在词性标注中能达到较高的精度。可利用多种语法规则识别出重要的短语结 构。自然语言处理是指自然语言识别在信息检索中应用，可以提高信息检索的精度和 相关性。 ( 3 ) 建立检索项索引。使用倒排文件的方式建立检索项索引，一般包括“检索 项 、“检索项所在文件位置信息 以及“检索项权重”。 ( 4 ) 检索结果预处理技术。搜索引擎的检索结果通常包含大量的文件，用户不 可能一一浏览。搜索引擎一般应按与查询的相关程度对检索结果进行排列，搜索引擎 确定相关性的方法有概率方法、位置方法、摘要方法、分类或聚类方法等。概率方法 根据关键词在文中出现的频率来判断文件的相关性。这种方法对关键词出现的次数进 行统计，关键词出现的次数越多，该文件与查询的相关程度越高。位置方法根据关键 词在文中出现的位置判定文件的相关性。关键词在文中出现的越早，文件的相关程度 越高。摘要方法是指搜索引擎自动的为每个文件生成一份摘要，让用户自己判断结果 的相关性，以便用户进行选择。分类或聚类方法是指搜索引擎采用分类或聚类技术， 自动把查询结果归入到不同的类别中。 1 2 4 搜索引擎的性能评估 衡量搜索引擎性能【1 5 l 的两个重要参数是：召回率( r e c a l l ) 和精度( p r e c i s i o n ) 。 召回率是检索出的相关文档数与文档集中所有的相关文档数的比率，衡量的是搜索引 擎的查全率；精度是检索出的相关文档数与检索出的文档总数的比率，衡量的是搜索 引擎的查准率。对于搜索引擎系统来讲，因为对于一个查询总能返回很多信息，所以 召回率一般不成问题；加之，没有一个搜索引擎系统能够搜集到所有的w ，e b 网页， 召回率很难比较，所以衡量搜索引擎的性能时，召回率很少使用。目前的搜索引擎系 统都非常关心精度，即是否为用户提供了相关度很高的、高质量的导航信息。 4 第一章绪论 搜索引擎系统的其它衡量指标还有响应时间、支持峰值查询的能力、易用性、返 回结果的有效性( 是否为死链、过时信息) 等等。 影响一个搜索引擎系统的性能有很多因素，最主要的是信息搜集策略和检索模 型，包括索引库的更新频率和策略、文档和查询的表示方法、评价文档和用户查询相 关性的匹配策略、查询结果的排序方法和用户进行相关度反馈的机制。 1 3 课题研究的内容 “网络搜索技术的研究及化工专业搜索引擎的建立是2 1 1 项目的子项目，该课 题研究的内容主要是研究并建立一个化工专业搜索引擎系统，主要包括系统架构的搭 建、网络蜘蛛模块的开发、文件处理器模块的开发、索引器模块的开发、中文分词模 块的开发、检索器模块的开发以及信息过滤模块的开发。本文主要设计适合化工专业 搜索引擎的索引系统，建立高效率、高性能的索引器。主要内容包括设计多索引器对 文档进行批量和增量索引，以内存作为索引文件缓冲区，有效地减少l o 操作；对索 引库的词典文件进行分类排序，使之更符合化工专业搜索引擎检索的需要；对待索引 的网页文档按其类型和权重加入权值，提高检索时查找化工文档的精度。 5 第二章搜索引擎中索引的体系结构 第二章搜索引擎中索引的体系结构 2 1 搜索引擎索引的体系结构 2 1 1 概述 索引结构1 1 6 】是搜索引擎的核心，直接影响着搜索引擎的检索性能。当提到索引时， 使人首先联想到的是数据库系统。但是数据库的索引结构并不能满足搜索引擎的特殊 要求。首先，搜索引擎面对的是海量数据，大型的商业搜索引擎一般都要索引几千万 个网页，有些甚至到几亿，几十亿个。如此大型的数据量，使得数据库系统很难有效 的管理。其次，搜索引擎使用的数据操作简单，一般而言，只需要增、删、改、查几 个功能，而且数据都有特定的格式，可以针对这些应用设计出简单高效的应用程序。 而一般的数据库系统则支持大而全的功能，但损失了速度和空间。对搜索引擎来讲， 最重要的是如何有效地响应大量的用户检索需求，这必然要求搜索引擎在检索程序的 设计上要分秒必争，尽可能地将大运算量的工作在索引建立时完成，使检索运算尽量 少。针对搜索引擎的特点，全文检索技术是搜索引擎有效地提高检索时间和检索精度 的一个较好的选择。 全文检索技术是一种重要的关键词检索方法。所谓全文检索，就是给定一个字 符串或字符串逻辑表达式，对文档库进行相应的检索，查找出与指定表达式相匹配的 文档，并将包含这些文字信息的文档作为检索结果返回给用户。全文检索技术分为两 种：一种是根据检索表达式直接在原文档中匹配查找，这种方式适合于对小型文档库 的检索；另一种是对文档预先建立索引，检索时对索引进行检索，这种方式适合于对 大容量的文档库的检索，如i n t e m e t 网络上的文档检索。全文检索技术包含两方面的 核心问题：一个是如何建立和维护索引库；另一个是如何提供快速有效的检索机制。 由于搜索引擎引擎所处理的对象是大规模的海量数据，所以需要对文档建立高效 的索引库。搜索引擎的查询效率取决于索引的组织情况，也直接决定了整个搜索引擎 能否实现快速响应。因此，必须对索引进行高效组织，以实现整个搜索引擎的高效率。 2 1 2 全文检索中索引的组织形式 7 北京化1 ：人! 学硕十学位论文 常用的文本索引的组织方式有很多种，如正排文件、倒排文件( i l l v e nf i l e ) 【1 7 】、署 名文件( s i 舯a t u r ef i l e ) 、后缀数组等等。 正排表结构如图2 1 所示。这种组织方法在建立索引的时候结构比较简单，建立 比较方便且易于维护；但是在查询的时候需对所有的文档进行扫描以确保没有遗漏， 这样就使得检索时间大大延长，检索效率低下。 倒排表结构如图2 2 所示。倒排表以字或词为关键字进行索引，表中关键字对应 的记录表项记录出现这个字或词的所有文档，一个表项就是一个字表段，记录该文档 的i d 和字符在该文档中出现的位置情况。由于每个字或词对应的文档数量在动态变 化，所以倒排表的建立和维护都较为复杂，但是在查询的时候由于可以一次得到查询 关键字所对应的所有文档，所以效率高于正排表。 而署名文件和后缀数组无论在性能还是存储空间方面都不如倒排文件。所以搜索 引擎一般采用类似倒排表的结构作为其索引组织形式。 在全文检索中，检索的快速响应是一个最为关键的性能，而索引建立由于在后台 进行，效率相对低一些，不会影响整个搜索引擎的效率。 图2 1 正排表的结构 n g 2 1s t m c t u r eo ff o 刑a r dn s t s 图2 - 2 倒排表的结构 2 - 2s t m c t u r eo fi n v e n e dl i s t s 2 1 3 搜索引擎的倒排索引结构 搜索引擎的倒排索引结构主要包括基于字的倒排索引结构和基于词的倒排索引 8 第二章搜索引擎中索引的体系结构 结构。 ( 1 ) 基于字的倒排索引结构 基于字的倒排索引把源文档中的每一个字的出现位置信息记录到索引库中，索引 库对每个不同的字符都保存一个字表，记录同一个字在文档中的所有出现位置。建库 时只要扫描所有文档，将读到的每个字符的位置信息加到对应的字表中即可。与此相 对应，基于词的倒排索引以能表达一定意义的词为基本单位建立索引库。两种结构各 有优缺点。虽然基于字的倒排索引通用性强，实现和维护相对容易，但检索时有可能 断章取义，将完全不相干的文档也检索出来。 ( 2 ) 基于词的倒排索引结构【1 8 j 典型的基于词的倒排索引结构如图2 3 所示，包含两部分：( 一) 中文词组成向量 ( 称之为词汇表) ，它包含了词的基本信息和词索引在索引文件中的偏移量；( 二) 对 于词汇表中的每一个词，都有一个它出现过的文档列表，它包含了出现文档编号，在 此文档中该词的频率和出现的位置序列。 词索引指针指向词的索引在索引文件中的偏移量，区域最开始保存的这个词出现 过的文档数目( 文献频率) ，这是为了在检索过程中读取索引前能够合适地分配内存 空间，文献频率后面试出现文档的列表。在这个结构中，除了词频用单字节表示外， 其他都用四个字节表示，而且出现在列表中的文档编号是升序排列的。 图2 1 3 词条索引倒排文档结构 蛋i g 2 - 3s t n l c l l l r e0 fi n v e r t e dl i s t so ft e 咖si n d 懿 基于词的倒排索引需要使用切分词典，其优点是索引库可以组织得比较小，检索 的处理速度也比较快，而且还可能实现同义词、反义词的概念检索。虽然这种结构的 索引总体性能较好，但这种方法在处理中文时实现起来却十分困难。首先一个最基本 的问题就是要对源文档进行词的切分。目前这种处理都需要使用一个切分词典，按照 一定的策略对文档进行切分处理。但在实际中，中文词的切词工作存在许多难点，中 文词数量极多，词在不断地动态发展，使用灵活、构词方法复杂，切分时经常会遇到 歧义情况，容易发生切分错误，而对专有名词的切分也往往会发生错误切分。由于中 文词的切分存在这些困难，目前的切词技术的现状还不容乐观，还难以满足实际的应 9 北京化l ：人学硕十学位论文 用需求。但是对w e b 文档而言，一方面，由于其领域广泛，内容动态变化快，很难建 立足够大的词典以适应广泛领域的文档信息的处理需求；且很多领域中不断有新词汇 出现，加上大量的人名、地名及各种专有名词，几乎不可能有一个词典能覆盖这些词 汇：另外，考虑港台等地区用语习惯的不同也造成难以使用一个统一的词典；而对于 古文等特殊类型的文档，则几乎无法使用词典；另一方面，中文词使用灵活，切分时 经常会遇到歧义情况，容易造成切分错误。而在英文系统中，词与词之间在书写上用 空格隔开，计算机处理时可以非常容易地从文档中识别出一个一个的词，所以英文倒 排表可以采用词表法。 2 1 4 通用索引的创建流程 要建立基于词的索引，首先需要对文档进行自动分词。将文本中的中文词、西文 词和连续数字组合分析出来，然后对分词结果进行排序，合并相同词的信息，这样就 得到了一张文档中出现词的列表以及它们的出现位置序列。对于每个词，可以根据它 们的计算机编码( 中文g b 2 3 1 2 ，西文和数字a s c 码) 映射到词表中的位置，更新词 汇表及索引。下面是详细的创建流程【1 9 ，2 0 j ： ( 1 ) 对文档进行自动分词，对结果排序，合并相同词的信息。 ( 2 ) 定位词在词表中的位置，得到词索引区在临时文件中的偏移量，如果是以 前未出现过的词，就在临时文件中的末尾分配一个固定大小的基本空间，对于低频词 来说太大的基本空间会造成浪费，所以需要分配合适大小的基本空间。 ( 3 ) 如果这个词以前出现过，将文档的读写指针定位到这个词的索引区的末尾。 ( 4 ) 写入每个词的索引信息到临时文件。如果此时分配给该词的空间用完，则 在临时文件末尾给其分配新的溢出空间，出现次数越多的词分配的溢出空间也就越 大，索引写完后将上一索引区的向前指针更新为新分配空间在临时文档中的偏移量。 ( 5 ) 对于文档中的每个词，重复步骤( 2 ) 一( 4 ) ；对于每篇文档重复步骤( 1 ) 一( 5 ) 。 ( 6 ) 所有文档处理完后，对于每个词，我们将分散在临时文档中的索引信息合 并在一起，然后按照图2 3 的格式写入最终的倒排文档。 图2 4 是临时文件的结构。由图2 4 可以看出此创建索引过程中，对于每个词来说， 首先需要定位文档读写指针到词索引区的末尾，然后再写入新的索引信息。这两个过 程都涉及到大量外存储器上的随机读写操作，如果临时文档规模较大，这些操作将相 当耗时。由于可以释放临时保存分词结果的空间，因此内存占用量较低。 l o 第二章搜索引擎中索引的体系结构 一一一 2 1 5 常用的索引压缩技术 图2 4 临时文件结构 量毽2 - 4s 臼m c t l l 佗o ft c m pf i l e s 为了减少索引空间，需要对倒排文档进行压缩f 2 1 捌。由于索引完全是由整数值组 成，整数值越小，就能用更少的字节来表示它。为了提高索引压缩比，需要减小索引 中数值大小，因此在创建索引之前，需要对索引进行预处理。词出现列表中的文档编 号是升序排列的，因此可以采用增量编码的方法表示文档编号，文档编号只保存与上 一篇文档编号的增量。词在文档中的出现位置序列必然是升序排列的，因此也可以采 用同样的处理方法，同时出现位置可以用词编号来表示，而不用词相对于文件头的字 节偏移量来表示，这样可以减少出现位置的数值。 ( 1 ) 均匀变长编码 在未压缩的索引中，除了词频是单字节表示以外，其他都是用4 个字节来表示， 大部分的数值根本不需要4 个字节表示，造成了很大的浪费。设计一种整数变长编码 p 1 ，将双字的低字节的最低2 位作为数值字节长度标志位。o o 1 1 分别表示数值需要 1 _ 4 个字节表示。除了2 位作为标志位，字节其他位都用来保存数据，如图2 5 。由图2 5 可知字节长度和标志位是均匀映射，所以称之为均匀变长编码。 编码时，首先根据数值大小来判断字节长度标志位，然后将数值做左移2 位运算， 将标志位通过按位或运算写入数值的低2 位中。在解码时，首先在当前指针处读取一 个字节，和0 x 3 做按位与的运算获得此数值的标志位，然后按照标志位读入相应的字 节，最后将读入的数据整体做右移2 位操作就能得到源数据。比如数值1 2 0 ，用二进制 表不为1 1 1 1 0 0 1 0 0 ，通过大小比较后可知需要2 个字节来表示，均匀压缩编码后的二迸 制表示为0 0 0 0 0 0 1 11 1 0 0 0 0 0 l ，可以看出大部分的增量数值只需1 2 个字节表示，而无 需再用4 字节。 北京化l ：人学硕+ 学位论文 ll r a g = = 0 0l 1 厂j n a g = = 0 1 f 1 a g ( 2 b i l ) 一一口 一一 f 1 a g = = 1 0 。口一一 f 1 a g = = 1 1 图2 5 双字均匀编码 f i g 2 - 5d o u b l eb y t e ss y m m e t r i c a lc o d i n g ( 2 ) 非均匀变长编码 通过分析可以看出，大部分情况一篇文章包含的字词数在1 万以下，那么出现位 置数值的增量编码则会更小。对于数据量较大的高频词，其出现文档编码的相对增量 值也不大。针对全文数据的这一特点，提出一种标志位和字节长度非均匀的映射编码 方法刚。由于小数值出现的机会大，可以将小数值字节表示范围划分密集一些，而大 数值字节表示范围划分粗略一点。双字的编码方式如图2 6 所示。在前面的方法中。表 示词频的单字节不压缩，由分析可知，一个词在很大部分文章中出现频率会很低，针 对此加入了对词频单字节的压缩编码方法，单字节编码标志位为1 位，0 或1 分别表示 用半个或一个字节表示数值，如图2 7 。 均匀变长编码读写时，都是以字节为单位的，因此其压缩和解压缩的算法较简单； 非均匀变长编码由于会出现读写时字节不对齐的情况，因此算法较为复杂，解压缩的 时间也会更长。就索引的空间来说，原来大部分用2 字节表示的数值现在都能用1 5 倍 的字节表示，这部分空间减少了2 5 ，但是1 字节的表示长度没有变化，3 字节现在需 要4 字节来表示，字频大部分用半个字节就能表示，从整体来说比均匀编码方式的空 间缩减率在2 5 左右。由此可以看出非均匀编码相对于均匀编码来说，用一个标志位 状态表示1 5 个字节长度，3 ，4 个字节长度标志位合并为一个，使得在低数值字节表示 范围上划分更细了，与实际系统中小数据出现概率大的情况十分匹配，因此可以获得 更大的空间压缩率。 1 2 第二章搜索引擎中索引的体系结构 i ii n a g = = 0 0l f 1 a g g b i t ) 一f l a g = = 0 1 f 1 a 2 = = 1 0 一一一口一一 r a 窑= = 1 1 图2 6 双字非均匀编码 n g 2 - 6d o u b l cb y t e s 觞y m m e t 血a lc o d i l l g 1 b li ln 唱：。l y j n a g ( 2 b i t ) f l 垮1 图2 7 单字节变长编码 f i g 2 - 7s i n g l eb y t eu n f i 耻dc o d i n g 2 2g o o 翊e 索引技术的探究 2 2 1g o o 西e 索引入库模块 索引入库模块【2 5 捌由分类器和标引器组成。标引入库模块处理大量的文件和数 据，用来构建庞大的数据库，主要涉及数据资源库、词典库、链接库、桶等。桶的结 构与内容非常复杂，在此介绍分类器、标引器和有关桶的操作。 ( 1 ) 分类器( s o n e r ) 分类器从桶中取出数据，按d o c i d 进行一级分类，然后按照w o r d i d 进行二级分 类并产生倒排档索引。分类器产生w o r d i d 的列表并把其偏移量写到倒排档索引中。 一个称为d u m p k x i c 0 n 的程序把这个列表和由标引器产生的词典揉和在一起并为检 索器产生一个新的词典。 北京化i ：人学硕十学位论文 ( 2 ) 标引器( i n d e x e r ) 标引器有许多函数，它读数据库，解压缩文档然后进行分析。每个文档都被转成 一套单词出现频率，称之为采样数。采样数记录单词及在文档中出现的位置，字体的 大小以及大写信息。标引器把这些采样数分配到一套“桶”中，创建一个部分分类的 正排索引。对于中文，g o o 酉e 主要采用了二元切分法，也就是为什么输入长于两个汉 字的中文，如果不加双引号，g 0 0 西e 会自动给以切分的原因。 ( 3 ) 桶( b a r r e l s ) g 0 0 9 l e 共有6 4 个桶( b a 玎e l s ) ，每个桶都存着w o r d i d 的归类，包括顺排档与倒 排档。如果一个文档包含落在某个桶里的词，d o c i d 和w o r d i d 的列表以及相应的命 中列表就被记录到桶里。g 0 0 西e 存储每一个、釉r d i d 时，存储的是与所在桶的最小 w o r d i d 的相对差异，而不是存储实际的w o r d i d 。这样，在未排序的桶中用2 4 位存储 w o r d i d ，留下8 位用来存储命中列表的长度。 倒排档索引就像顺排档一样由系列的桶组成，唯一的不同是被分类器处理过。有 个重要的问题是d o c i d 应当在d o c l i s t 中如何排序。一个简单的解决办法是用d o c i d 进 行分类，这允许多词查询而带来的不同d o c l i s t 的合并。另外一个办法是按词在每个文 档中出现的频率等级进行分类存储，尽管这使得处理单个词的查询变得繁琐，但为多 词查询提供了可能。g 0 0 西e 在这两个方案中选择了折衷，使用两套倒排的桶，一套为 包括标题和锄c h o rl l i t s 的命中列表，称之为短桶，另一套为所有的命中列表，称之为 长桶。 在顺排档索引和倒排档索引中，命中列表占据了大量的空间。命中列表是指词在 一篇文档中的出现频率，包括位置、字体和大写信息。g 0 0 西e 为编码位置、字体和大 写考虑了多种编码方案简单编码、优化压缩编码和哈夫曼编码。由于优化压缩编 码对空间的要求比简单编码低，操作过程比哈夫曼编码简单，因此，g 0 0 西e 最终选择 了优化压缩编码。 g 0 0 酉e 用两个字节的压缩编码来记录每次命中，命中类型有两种：特殊命中与普 通命中。特殊命中包括u r l 的命中率、标题、链接文本和关键标记。普通命中含有 所有的信息，包括大写位、字体大小和1 2 位标记词在文档中出现的位置信息等。字 体大小用3 位来表达文档的其它内容的相对值( 仅有7 个值可用，因为1 1 1 是特殊命 中的标记) 。特殊标记由大写位，字体设成7 来表明是一个特殊命中，有4 位表示类 型，用8 位标记位置。为了节省空间，命中列表的长度由顺排档中的w o r d i d 和倒排 档中的d o c i d 决定。分别需要8 位与5 位。如果长度更长的话，在相应的位里就存着 一个溢出编码，接下来的两个字节存储命中列表的实际长度。 1 4 第二章搜索引擎中索引的体系结构 h n ： 普通 特殊 锚： 顺排 占2 个字节 c a d ：1i m d ：3d o s i t i o n ：1 2 c a p ：1h p _ 7t y p e ：4p o s i t i o n ：8 c a p ：j妇p = 3t y p e ：4h 弱h ：4 ip o s ：4 i d o c i w o r d i d ：2 4n h i t s ：8h i t h i t h i t h i t w o r d i d ：2 4n h i t s ：8h 证h j th i th i l n u w o r d i d i d o c i ew o r d i d ：2 4 n h i t s ：8h nh i t h i th 矗 w o r d i d ：2 4n h i t s ：8h i th i t h i t h i t w o r d i d ：2 4n h i t s ：8h j lh i th i t h j t n u w o r d i d 2 9 3 m 倒捧档桶：4 l g n d o c n d o c n d o c d o c i d ：2 7 l n h i t s ：5lh i t h i i h i th 矗 d o c i d ：2 7 in h i t s ：5lh i t h i t h i th i l d o c i d ：2 7 |n h i t s ：5 lh j t h i t h i th i l d o c i d ：2 7 ln h i t s ：5lh i i h i t h i t h i t 图2 8 顺排档索引、倒排档索引与词典 f i g 2 - 8f b r w a r dl i s t s 、l n v e n e dl i s t sa n dl e x i c o n ( 4 ) 词典1 f l e x i c o n ) 词典有几种不同的形式。对早期系统的一个重要改变是根据合理的代价分配内 存。该词典包含1 4 0 0 万个词条( 有些生僻词没加) ，由两部分实现，词表和指针的 哈希表。词表还有一些辅助信息用以实现其它功能。对于每个有效的w o r d i d ，词典 包含指向w o r d i d 所在桶的指针。它指向d o d d 和相应的命中列表的d o d i s t 。d 1 0 c l i s t 表明该词在所有文档中出现的所有情况。 2 2 2g 0 0 皿e 索引及其过程 ( 1 ) g 0 0 西e 索引方法 为了加快信息检索的速度，g o o 酉e 对信息库建立倒排索引。在建立倒排索引时， 着重考虑以下几个方面的问题： ( 一) 全文索引。g o o 百e 对信息库中的页面建立了全文索引，并且在建立索引时， 还同时考虑了超文本的不同标记所表示的不同含义，如粗体、大字体显示的内容往往 比较重要；放在锚链中的信息往往是它所指向页面信息的概括，所以用它来作为它所 指向的页面的重要信息。g 0 0 酉e 还在建立索引的过程中收集页面中的超链接，这些超 链接反映了收集到的信息之间的空间结构，利用这些信息可以提高页面相关度判别的 准确度。 ( 二) 过滤无用词汇。网页中存在着许多对信息检索没有什么实际意义的词汇， 如英文中的“a ”、“a n 、“t h e 等，以及中文中的“的”、“啊 等，它们不能 北京化i ：人学硕十学位论文 明确表达网页的主题信息，因此没有必要对它们进行索引。g 0 0 西e 在建立索引时，依 据事先保存的一张无用词汇表，对网页中的无用词汇进行过滤。 ( 三) 对图像标记的处理。网页中存在着大量的图像信息，而图像检索技术目前 还不是很成熟。网页中的图像标记往往存放着图像的替换信息，这些信息对相应的图 像有一个基本的描述。g 0 0 酉e 就专门针对这些图像的替换信息建立了索引，以支持 某种程度上的图像检索。 ( 2 ) g o o 西e 索引过程 g o o 酉e 具体建立索引的过程【2 刀，可分为以下三个阶段： ( 一) 分析过程。该过程主要处理文档中可能出现的错误。这些错误包括：错误 的h r r m l 标记、非a s c i i 码字符、标记嵌套层次过深等。