（计算机系统结构专业论文）一种开放式高性能全文检索平台的研究与实现.pdf

摘要 信息的快速增长促使搜索引擎的迅速发展。通用搜索如g o o g l e 、 b a i d u 已取得很大成功，然而，一方面它们的技术严格保密，另一方 面，开发人员不可能将庞大的通用搜索引擎无缝地嵌入到自己的应用 程序中；此外，缺乏对中文支持良好的开源搜索引擎。为此，本文研 究并实现了一种新的中文全文检索平台。该平台具有高性能、架构灵 活等特点。它既可以很方便地应用于各种动态数据环境的实际领域， 也可以用来构建信息检索的实验系统。本文的主要研究工作如下： 1 针对传统最大正向匹配算法的效率较低和灵活性差的问题，提 出了一种改进算法。该算法采用了基于h a s h 和t r i e 树的词典结构， 使分词效率提高了约2 0 0 。同时，该算法摆脱了传统最大正向匹配 算法的固定最大词长度限制，具有更好的灵活性。 2 针对传统索引结构难以满足动态数据环境的不足，本文提出一 种新的索引创建方案。该方案主要包括：( 1 ) 分级的倒排索引组织结 构和链式存储方式，能够很好地解决索引动态增长要求；( 2 ) 基于动 态平衡树的索引合并策略；( 3 ) 可配置的限制性指数分配策略，提高 了索引内存利用率和分配效率；( 4 ) 基于d - g a p 的差量压缩算法，使 索引文件大小减少了7 5 ，从而减少i o 次数，提高系统性能。 3 基于前面提出的分词算法和索引创建方案，采用c + + 面向对象 设计思想以及工厂模式等设计模式，设计和实现一个架构灵活、扩充 性良好的全文检索平台，系统平台主要包括索引子系统，检索子系统， 存储子系统和插件管理子系统，以及内存管理组件。 4 利用该平台设计和实现一个实用的商用搜索引擎系统。该搜索 引擎提供用户对网络监控数据的搜索。为各种类型( 文本、h t m l 、 e m a i l 、o f f i c e 文档、p d f 文档等) 的监控数据创建大容量索引，提 供基于内容分类的高性能查询。该系统投入实际使用半年多所取得显 著的成效也很好地证明检索平台的高效性。 关键词全文检索，中文分词，倒排索引，索引维护，搜索引擎 a b s t r a c t t h e e x p l o s i v eg r o w t h o fi n f o r m a t i o n p r o m o t e s t h e e x p e d i t i o u s d e v e l o p m e n to fs e a r c he n g i n e g e n e r a ls e a r c he n g i n e ss u c ha sg o o g l e ， b a i d uh a v eb e e np r o v e dt ob es u c c e s s f u l h o w e v e r , o nt h eo n eh a n d ，t h e i r b u s i n e s st e c h n o l o g yi sc o n f i d e n t i a l ，o nt h eo t h e rh a n d ，d e v e l o p e r sc a n t s e a m l e s s l ye m b e dt h e s eg e n e r a ls e a r c he n g i n e si n t ot h e i ra p p l i c a t i o n s ； b e s i d e s ，i tl a c k so p e ns o u r c es e a r c he n g i n e sw h i c hs u p p o r tc h i n e s ew e l l t h e r e f o r e ，t h et h e s i sr e s e a r c h e sa n di m p l e m e n t san e wc h i n e s ef u l l t e x t r e t r i e v a lp l a t f o r m w i t hh i g h p e r f o r m a n c ea n df l e x i b i l i t y , i ta i m st oe i t h e r b ea p p l i e di n t op r a c t i c a lf i e l do fd y n a m i cd a t ae n v i r o n m e n t ，o rp r o v i d e f o raf e a s i b l eo fr e s e a r c ha n de x p e r i m e n t a t i o ni ni n f o r m a t i o nr e t r i e v a l t h e m a i nr e s e a r c hw o r k sa n di n n o v a t i o n si nt h et h e s i sa r ea sf o l l o w s 1 a n i m p r o v e d m e t h o di s p r e s e n t e da c c o u n t i n g f o rt h e l o w p e r f o r m a n c e a n d p o o rf l e x i b i l i t yp r o b l e m s o ft h et r a d i t i o n a l m m ( m a x i m u mm a t c h i n g ) s e g m e n t a t i o nm e t h o d i tu s e san e wd i c t i o n a r y s t r u c t u r eb a s e do nh a s ha n dt r i et r e es t r u c t u r e ，w h i c hg r e a t l yi n c r e a s e s t h es p e e do fw o r dc u t t i n gb y2 0 0 m o r e o v e r , f r e e i n gi t s e l ff r o mf i x e d m a x i m u m m a t c h i n gl e n g t h ，i th a sm o r ef l e x i b i l i t y 2 a i m i n ga tt h et r a d i t i o n a li n d e xs t r u c t u r eh a r dt oa d a p tt h ed y n a m i c d a t ae n v i r o n m e n t s ，an e wi n d e xc r e a t i n gs c h e m ei sp r e s e n t e d i ti n c l u d e s ： ( 1 ) i m p r o v e di n v e r t e di n d e x i n gs t r u c t u r ea n dc h a i ns t o r a g ep e r f e c t l y s o l v e st h ep r o b l e mo fd y n a m i ci n c r e a s i n gi n d e xd a t a ；( 2 ) an o v e li n d e x m e r g i n gs t r a t e g yb a s e d o nd y n a m i cb a l a n c et r e e ；( 3 ) c o n f i g u r a b l e m e m o r ya l l o c a t i n gs t r a t e g yb a s e do nl i m i t e de x p o n e n tm e t h o dg r e a t l y i m p r o v e s t h eu t i l i z a t i o nr a t ea n de f f i c i e n c yo fi n d e xm e m o r y ；( 4 ) d if f e r e n t i a lc o m p r e s s i n ga l g o r i t h mb a s e do nd - g a p ，w h i c hg r e a t l yr e d u c e s t h es i z eo fi n d e xf i l e sb y7 5 a n di n d i r e c t l yr e d u c e si ot i m e s 3 b a s e do nt h ew o r da u t o m a t i cs e g m e n t a t i o na l g o r i t h ma n di n d e x s t r u c t u r e s ，d e s c r i b e da b o v e ，u s i n go b j e c t - o r i e n t e dp r o g r a m m i n gw i t hc + + a n ds e v e r a ld e s i g np a r e r n ss u c ha sf a c t o r yp a t t e r n ，w ed e s i g na n d i m p l e m e n tah i 曲一p e r f o r m a n c ec h i n e s ei n d e xp l a t f o r mw i t h f l e x i b l e a r c h i t e c t u r ea n ds c a l a b i l i t y t h es u b s y s t e m sa n dm o d u l e si n c l u d e si n d e x s u b s y s t e m ，s e a r c h i n gs u b s y s t e m ，s t o r a g es u b s y s t e m ，p l u g - i nm a n a g i n g s u b s y s t e ma n dm e m o r ym a n a g i n gm o d u l e 4 a tl a s t ，b a s e do nt h ei n d e xp l a t f o r m ，w ed e v e l o pab u s i n e s s s e a r c h i n ge n g i n e i t c r e a t e s h i g h - c a p a c i t y i n d e xf o ra l lk i n d so f m o n i t o r i n gd a t aw h i c hr e c o r d su s e r s b e h a v i o r so fa c c e s s i n gi n t e m e t ，a n d p r o v i d e sr a p i d - r e s p o n s eq u e r ys e r v i c e s r e s u l t sf r o mp r a c t i c a lu s ef o r m o r et h a nh a l fay e a rp r o v e dt h ee f f i c i e n c yo ft h ef u ll t e x tr e t r i e v a l p l a t f o r m k e yw o r d s f u l l t e x t r e t r i e v a l ，c h i n e s es e g m e n t a t i o n ，r e v e r t e d i n d e x ，i n d e xm a i n t e n a n c e ，s e a r c he n g i n e n l 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不 包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我 共同工作的同志对本研究所作的贡献均己在论文中作了明确的说明。 作者虢丛盟一吼孕年月乒日 学位论文版权使用授权书 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文并根据国家或湖南省有关部门规定送交学位论文， 允许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内 容，可以采用复印、缩印或其它手段保存学位论文。同时授权中国科 学技术信息研究所将本学位论文收录到中国学位论文全文数据库， 并通过网络向社会公众提供信息服务。 作者签名：丝堕导师签黍篮 嗍毕年【月缪日 硕士学位论文第一章绪论 1 1 课题来源及研究背景 第一章绪论 随着计算机技术及网络技术的迅速发展，各种格式的电子文档数目急剧膨 胀。以世界上的各个行业几乎都在使用的m i c r o s o f tw o r d 文档为例，据有关调查 显示，如果将现有的w o r d 文档都打印出来，并将它们堆在一起，长度几乎就可 以到达太阳系里遥远的另一个星球【l 】。 很显然，如果没有一种新的计算机技术来帮助人们快速、全面、准确地查找 所需要的资料信息，人类也许会被这海量的信息所淹没而摸不着北。这种新的技 术就是检索技术，它成为了相关研究领域的一个热门课题。在这庞大而目标明确 的需求中，商业公司嗅出其中的商机，其中的佼佼者如g o o g l e 、b a i d u 、y a h o o 、 i n f o s e e k 。这些通用搜索引擎是集成信息检索技术的典型代表，它们为有效地定 位和查找w e b 文档信息起到了巨大的作用。然而，通用搜索引擎虽然功能十分 强大，但对于具有很多子网站的企业门户网站进行搜索时响应速度慢，索引结果 不全；并且，通过这些通用搜索引擎的站内搜索功能来实现的全文检索功能往往 不尽人意，经常会导致搜索结果不全和出现“坏链接”的情况f 2 j ；更重要的是， 作为商业化的信息检索工具，开发人员不可能将庞大的通用搜索引擎无缝地嵌入 自己开发的应用程序中以提供全文索引和检索功能。 另一方面，人们需要继续对全文检索技术进行研究，包括分词算法，索引算 法，检索算法，索引缓存，以期从效率和效果两个方面取得更大的进步。这些研 究都需要搭建大型的实验系统进行测试和验证。 为此，人们开发出一批优秀的开源搜索平台。目前广泛使用的有a p a c h e 软 件基金项目的l u e n c e 盼1 ，支持p 2 p 架构的h y p e r e s t r a i e rh 1 ，结构化文本索引和检 索z e b r a 船1 ，针对d o m a i n 和i n t r a n e t 的h t ：d i g 嗍，等等。这些平台性能各异，都 有特定的应用场景。有些具有良好的扩展性，提供了简洁的编程接口，但性能较 差，如l u e n c e 。有些具有很高的性能，但扩展性差，如h y p e re s t r a i e r 。此外， 这些平台对中文支持都不好。因此，需要对全文检索技术和平台进行继续研究， 研制和实现一个良好架构的、规模可扩展的，满足多种实验和应用要求的、高性 能的、能够很好支持中文的索引和检索平台。 1 2 国内外研究现状 1 中文分词的研究现状与水平 快速准确的汉语自动分词是高效中文搜索引擎的必要前提。众所周知，中文 l 硕士学位论文第一章绪论 文本没有类似英文空格之类的显式边界标志。中文自动分词的任务，通俗地说， 就是由机器在中文文本词与词之间自动地加上空格口1 。中文分词的关键在于切分 歧义的检测和消除。 歧义消解经历了一个由浅及深、由简单到复杂的语言知识利用的演变过程： ( 1 ) 一些系统( 尤其是早期系统) 主要利用词频以及语素( 自由抑或约束) 、 切分歧义表层结构等简单信息陋1 ( f a nc k a n dt s a iw h 1 9 8 8 ：李国臣、刘开瑛 等1 9 8 8 ；王永成、苏海菊等1 9 9 0 ；c h e nk j a n dl i us h 1 9 9 2 ；马晏1 9 9 6 ) 。 ( 2 ) 何克抗，徐辉等( 1 9 9 1 ) 断言，9 5 o 左右的切分歧义可以借重句法 以下的知识解决，只有5 0 必须诉诸语义和语用知识。基于规则的几个分词系 统( 黄祥喜1 9 8 9 ；梁南元1 9 9 0 ；姚天顺、张桂平等1 9 9 0 ；y e hc l a n dl e eh j 1 9 9 1 ； 韩世欣、王开铸1 9 9 2 ；徐辉、何克抗等1 9 9 1 ) 都自觉或不自觉地受到这个结论 的支配，切分歧义消解主要诉诸词法与句法规则。存在的缺陷是，规则集由人凭 主观编制而成，会受到系统性、有效性、一致性、可维护性等“天然 问题困扰。 ( 3 ) 为克服人工句法规则集的弊端，一些研究人员开始尝试另一种途径一 句法统计。l a ib ya n ds u nm s ，e ta 1 ( 1 9 9 2 ；1 9 9 7 ) 、c h a n gc h a n dc h e n c d ( 1 9 9 3 ) 、白拴虎( 1 9 9 5 ) 等将自动分词和基于m a r k o v 链的词性自动标注技 术结合起来，利用从人工标注语料库中提取出的词性二元统计规律来消解切分歧 义( 词性标注对分词有反馈作用，两者并行) 。初步实验( l a ib y a n ds u nm s ，e t a 1 1 9 9 7 ) 表明旧1 ，同“先做最大匹配分词，再作词性自动标注”( 词性标注对分 词无反馈作用，两者串行) 相比，这种做法的分词精度和词性标注精度分别提高 了1 3 和1 4 。 ( 4 ) w u a d a n dj i a n gz x ( 1 9 9 8 ) 走得更远。他们相信n 引，多数情况下，切 分歧义可以在输入句子的局部范围内得到妥善处理，但有些比较复杂的切分歧 义，必须在句中更大的范围内才能解决。当遇到这种情况时，他们的系统将对句 子做完整的句法分析，如果分析失败，则拒绝相应的切分。 现有的分词算法总结可分为三大类：基于字符串匹配的分词方法、基于理解 的分词方法和基于统计的分词方法。每种算法都有其优缺点，当都很难达到广泛 认可的满意程度。 2 索引和检索技术的研究现状和水平 在国际上，信息检索平台有很多，既有功能强大的商业平台，也有实验平台 和工业应用的开源项目。商业领域有g o o g l e ，b a i d u ，y a h o o 等，对先进检索技术的 拥有成为这些公司生存发展的法宝，因而这些技术也往往被严格保密起来。检索 实验平台的典型代表有：由麻州大学和卡内基梅隆大学合作开发的语言模型和信 息检索工具包l e m u r n ，皇家墨尔本理工大学( r m i t ) 的z e t t a i r n 引，滑铁卢大学的 2 硕士学位论文第一章绪论 w u m p u s n 3 1 等，其中最具有代表性的是l e m u r 。这些平台都有自己的特色和应用 场景，但大多数平台支持的实验有限，往往只关注某些方面的实验，系统架构不 够灵活。例如著名的l e m u r 实验平台仅仅关注检索模型等检索效果方面的实验， 而检索效率方面的实验不好扩展。此外，这些平台对中文的支持不好。 开源的搜索引擎也比较多，其中应用最广泛的要数本文前面提到的l u c e n e 。 作为一个开放源代码项目，l u c e n e 从问世之后，引发了开放源代码社群的巨大 反响，程序员们不仅使用它构建具体的全文检索应用，而且将之集成到各种系统 软件中去，以及构建w e b 应用，甚至某些商业软件也采用了l u c e n e 作为其内部 全文检索子系统的核心。a p a c h e 软件基金会的网站使用了l u c e n e 作为全文检索 的引擎，i b m 的开源软件e c l i p s e n 4 1 的2 1 版本中也采用了l u c e n e 作为帮助子系 统的全文索引引擎，相应的i b m 的商业软件w 曲s p h e r e n 5 3 中也采用了l u c e n e 。 l u c e n e 以其开放源代码的特性、优异的索引结构、良好的系统架构获得了越来 越多的应用。 l u c e n e 作为一个全文检索引擎，其具有如下突出的优点： ( 1 ) 索引文件格式独立于应用平台。l u c e n e 定义了一套以8 位字节为基础 的索引文件格式，使得兼容系统或者不同平台的应用能够共享建立的索引文件。 ( 2 ) 在传统全文检索引擎的倒排索引基础上，实现了分块索引，能够针对 新的文件建立小文件索引，提升索引速度。然后通过与原有索引的合并，达到优 化的目的。 ( 3 ) 优秀的面向对象的系统架构，使得对于l u c e n e 便于扩充新功能。 ( 4 ) 设计了独立于语言和文件格式的分析接口，索引器通过接受t o k e n 流 完成索引文件的创立，用户很容易扩展新的语言和文件格式。 ( 5 ) 已经默认实现了一套强大的查询引擎，用户无需自己编写代码即使系 统可获得强大的查询能力，l u c e n e 的查询实现中默认实现了布尔操作、模糊查 询( f u z z ys e a r c h n 剀) 、分组查询等等。 然而，l u c e n e 也有其与生俱来的缺陷：( 1 ) l u c e n e 的性能相当较差，难以 胜任海量数据的索引和检索。( 2 ) l u c e n e 对中文支持较差。 经过1 0 来年的发展，搜索引擎技术取得了长足的进步，但发展的空间仍然 很大。主要体现在以下几个方面n 7 1 ： ( 1 ) 自然语言理解技术。主要用来解决对用户检索提问的理解，克服当前 关键词检索和目录查询的盲目性，从而快速提高用户真正需要的检索结果。 ( 2 ) 垂直主题搜索引擎。垂直主题的搜索引擎以其高度的目标化和专业化 加强检索的针对性。 ( 3 ) 多媒体搜索引擎。未来的互联网是多媒体数据的时代，开发出可查寻 3 硕士学位论文第一章绪论 图像、声音、图片和电影的搜索引擎的本地化已经是势不可挡。 1 3 课题的研究内容及意义 一种架构灵活，扩展性良好，考虑多种需求的的高性能的中文全文索引和检 索平台显然具有广泛的应用前景。一方面，它良好的可编程接口使之很容易应用 在各种搜索应用中，如各种网站内部检索，企业信息检索系统，局域网信息检索 以及桌面检索等。另一方面，它可以作为一个实验平台，支持检索效果方面的研 究，例如面向信息检索的中文分词，检索模型，查询扩展与反馈等；同时还支持 检索效率方面的实验，例如倒排索引结构和算法研究，t o p - k 查询快速处理，实 时在线索引等。 本文主要研究索引相关的技术和检索平台的构建。包括： 1 分词算法的研究，主要研究中文分词技术； 2 索引文件格式，索引生成，索引合并等索引技术研究； 3 检索语法设计，结果文档打分、相关度计算等检索技术的研究； 4 可扩展的高性能的检索平台架构的研究。 1 4 本文的组织结构 论文分为五章。 第一章绪论。阐述课题背景与意义、国内外研究现状与发展方向、本文研 究的主要内容，说明了论文的章节安排。 第二章全文索引关键技术研究。首先介绍了全文检索系统的基础理论知识， 包括基本原理，功能，与数据库索引的比较，技术评价标准。然后重点研究中文 分词技术，索引结构和索引算法。详细描述了一种改进的分词算法和新的索引结 构及其相关索引算法，包括索引的创建、维护、压缩、索引内存管理。 第三章全文检索平台的设计。本章在第二章的研究基础上，从实用的角度 架构和设计一个全文检索平台的内核。 第四章全文检索平台的应用。本章在第三章的研究基础上，在一个具体的 环境下应用全文检索平台，设计和开发出一个实际检索系统，并对系统进行测试。 第五章总结与展望。总结本文所完成的工作，并指出了进一步研究方向和 研究问题。 4 硕士学位论文 第二章理论基础与关键技术研究 第二章理论基础与关键技术研究 2 1 全文检索系统 2 1 1 全文检索的功能与基本原理 索引技术诞生前，用户要查找包含某个或某些关键词的文档，只能采用传统 的查找方法，对于单机系统而言，各种操作系统都提供这样的自动查找程序，如 u n i x l i n u x 下的f i n d ，g r e p ，w i n d o w s 下的查找功能等。这种查找方法只是通过简 单的顺序扫描和匹配文本的方式来实现。当使用这样的方式来查找时，不需要对 文档资料库中的信息做任何预处理。相对而言，这种方法简单，易实现，且查全 率和查准率都很高。但它有一个致命的缺陷：效率低下，当要查找的文档数据量 很大时，这种方法变得几乎不可行。为此，人们又创造出各种新的查找方法，使 用索引便是其中最有效的一种。对于单一结构的整篇文档而言，则需要全文检索 技术。 全文检索是指计算机索引程序通过扫描文档，对文档按照一定策略分词，然 后对切分得到的有检索意义的单词创建索引，定位并记录该词在文档中出现的次 数和位置，当用户查询时，检索程序就根据事先建立的索引进行查找，并将查找 的结果按照特定顺序反馈给用户。这个过程类似于通过字典中的检索字表查字的 过程。 全文检索系统是按照全文检索理论建立起来的用于提供全文检索服务的软 件系统。一般来说，全文检索需要具备建立索引和提供查询的基本功能，此外现 图2 - 1 全文检索系统基本结构 5 硕士学位论文第二章理论基础与关键技术研究 代的全文检索系统还需要具有方便的用户接口、面向w w w 的开发接口、二次 应用开发接口等等。功能上，全文检索系统核心具有建立索引、处理查询返回结 果集、增加索引、优化索引结构等等功能，外围则由各种不同应用程序的功能组 成。结构上，全文检索系统核心具有索引引擎、查询引擎、文本分析引擎、对外 接口等等，加上各种外围应用系统等等共同构成了全文检索系统。图2 - 1 展示了 上述全文检索系统的结构与功能。 一个完整的全文检索系统架构组成应该包括： 1 解析器 负责提取各种类型文档内容。不同类型的文档需要不同的解析器，如网页文 档和m sw o r d 文档则分别需要网页文档解析器和m sw o r d 文档解析器。 2 查询语法解析器 负责查询语法的解析与优化。 3 分析器 负责分词处理。根据一定的分词词典和分词算法将解析器处理后的文本内容 切分成一个个词语。 图2 - 2 全文检索系统基本架构 6 硕士学位论文第二章理论基础与关键技术研究 4 索引子系统 创建和维护索引数据文件。 5 搜索子系统 提供对索引文件的查洵，文档打分，并将查询结果按一定规则排序。 6 存储组件 负责磁盘索引数据的读写。 7 插件管理器 为了利于扩展，考虑文档类型的多样性以及新的分词算法出现，提供对解析 器和分析器插件式管理。 各个组件或子系统的层次架构关系如图2 - 2 所示。 2 1 2 全文检索的核心与特点 全文索引和检索是全文检索系统的核心，也是全文检索系统的真正特色所 在，最能体现全文检索系统的优势。全文检索系统的结构不像关系数据库那样有 明确的定义，而是随全文检索软件的不同而有所区别。全文检索主要由两方面的 核心技术结合而实现：一是建立和维护索引库，二是提供快速有效的检索机制。 因而在设计时，要针对实际应用背景，确定索引库的数据结构和存储方式，以及 如何从原始文档中提取有用信息写入索引库中。 全文检索系统固然可以用已有的通用数据库管理系统来组织检索，如 s y b a s e 、o r a c l e 、d b 2 等，但是全文检索系统结构单一，操作单一，数据量大， 检索范围大，其主要操作是对数据进行插入和查找，而删除和修改很少使用，为 了提高检索速度，基本的检索过程应采用文件系统来实现。关系数据库管理系统 r d b m s 的瓶颈在于s o l 语句的执行速度，关系数据库屏蔽了底层系统，呈现给 用户的是它的高层接口。据统计，一条s q l 语句由于要进行编译和优化，转化 为底层语言再执行，其执行时间至少是1 0 m s ，而全文检索若从数据库中取数据 的话，往往需要与d b m s 交互多次，这比起直接使用文件系统基本语句的毫秒 级执行时间有着巨大的差别。再者，关系数据库系统还要维护整个系统的事务性 和表与表之间的数据依赖，执行效率再打折扣。无论关系数据库还是全文检索系 统最终数据都是以文件的形式存在的。所以一般情况下，基本的检索过程应采用 文件系统来实现，这样使得查询更直接、快速，可以有效提高执行速度n 。 全文检索系统突破了关系型数据库结构定义不易改变和数据定长的限制，支 持重复字段、子字段和变长字段，实现了对重复数据、变长数据的处理以及数据 项的变长存储管理。在处理连续信息( 包括全文信息) 和非结构信息( 包括重复数 据和变长数据) 时有着传统关系型数据库所无法比拟的优势。全文检索系统是一 7 硕士学位论文第二章理论基础与关键技术研究 种存储文档全文或其主要部分并能提供全文检索的源数据库，其体系结构介于文 件系统和关系数据库之间，它一般包含较少实体，实体之间的关联也比较少， 结构相对简单，其主要特点是n 7 ，： 1 数据的非结构化。全文检索系统中的数据与关系数据库中的记录不同，它 没有一个统一的数据结构，库中的文档往往是多种格式并存，而不仅仅局限于某 种或某几种文档格式。 2 包含信息的原始性。全文检索系统中的信息基本上是未经加工的原始文 本，具有客观性。 3 信息检索的彻底性。可对全文中的字、词、句( 没有检索意义的检索项除 外) 进行检索，还可以指定检索项之问复杂的位置关系。 4 所用检索语言的自然性。不作标引，借助截词、邻接等匹配方法，以自然 语言检索所需文档。这是与传统的主题词检索方法的根本区别。 5 数据的相对稳定性。全文检索系统中的数据基本上是封闭的，一般不需要 更新。 6 检索结果的准全性。利用后控制表等相关检索技术可以定制和改善检索效 果。 7 对事务性和并发性的要求不高。全文检索系统的操作主要是读数据，写操 作则主要是插入新数据，删除和修改都极少执行：此外，插入数据往往是间隔一 段时间，待积累了一定数量的新文档后才进行。即使有新数据插入，也不需要锁 住读操作，因为用户只是查询文档，即使暂时看不到新加入的文档，以往的数据 依然可用。所以，全文检索系统几乎不需要事务支持，而对事务的管理恰恰是很 消耗资源的，因此，全文检索系统在效率上比关系数据库得到了很大的提高。 2 1 。3 全文检索的技术评价标准 全文检索系统的技术评价标准主要包括查全率、查准率、索引更新效率、检 索结果排序、响应时间等n 引。 1 查全率 查全率是指全文检索系统检索出的与某查询关键字相关的信息的数量与全 文检索系统中实际与该查询关键字相关的信息总量之比率。但是如果全文检索系 统中的信息经常处于动态的变化过程中时，查全率指标比较难以测算。一种折中 的方案是可以通过全文检索相对查全率作为全文检索查全率的补充。相对查全率 可操作性较强，但受人为不确定因素的影响较大。全文检索的相对查全率的计算 方法为： 相对查全率= ( 专业人员检出的相关信息条数全文检索系统实际检出的信 8 硕士学位论文第二章理论基础与关键技术研究 息条数) * 1 0 0 2 查准率 查准率是指全文检索系统检索出的实际与某查询关键字相关的信息数量与 全文检索系统检索出的信息总量之比率。与查全率相似的是，查准率通常也比较 难以测算。一种折中的方案是计算全文检索系统的相对查准率，同样，相对查准 率也受人为不确定因素的影响较大，其计算方法为： 相对查准率= ( 专业人员辨别出的实际相关的信息条数全文检索系统实际 检出的信息条数) * 1 0 0 查全率与查准率是矛盾的双方，当它们的值达到一定时，查全率的提高通常 会导致查准率的降低，反之亦然。评价全文检索系统时，应该以该全文检索系统 所服务的主要用户群体的需求特点为标准。从目前信息检索工具用户的使用习惯 来看，用户往往更强调查准率的提高。值得注意的是，无论是强调查全率还是强 调查准率，全文检索都不能忽视索引库的更新。 3 索引更新效率 首先，新增的文档信息应能及时地在索引库中反映出来。由于文档资料库更 新的不确定性，全文检索系统索引库的更新情况比较复杂。其次，陈旧的和其信 息源己被移除的索引要及时删除，若不做及时删除，无疑将会增加用户查询的负 担，而且还会影响整个全文检索系统的查询性能。 索引的更新一般采用两种方法，一种是大批量的索引重建，另一种是小批量 的索引扩展，也叫增量式索引更新。对于一般的数据量小于1 0 g 的信息资料库来 说，定期对所有文档进行大批量的索引重建是可行的。但对于数据量庞大并且经 常处于动态更新的信息资料库而言，增量式索引更新则效率更高。 4 检索结果排序 检索结果的排序对于信息检索技术来说是十分重要的。根据i p r o s p e c t 在2 0 0 4 年4 月间发布的调查报告显示，8 1 7 的用户不会浏览第三页之后的检索结果， 而5 2 2 的用户只会关注第一页的检索结果。因此，如何将用户最关注的和最重 要的检索结果放在前面就成为影响全文检索系统检索质量的一个重要因素n 们。 5 响应时间 响应时间主要是指用户输入查询条件之后等待查询结果返回的时间。和大多 数应用系统一样，一个全文检索系统无论它的功能多么强大和完备，若响应时间 超出了用户可以忍受的程度，用户都会弃之不用。所以，响应时间对用户是否选 择某个全文检索系统产品将起着非常重要的作用，响应时间也因此成为评价全文 检索系统性能优劣的一个重要的技术指标。 9 硕士学位论文第二章理论基础与关键技术研究 2 2 中文自动分词技术 2 2 1 中文自动分词技术简介与难点 由于汉语不像英语有空格作为词与词之间的天然分隔符，需要某种技术将连 续的句子分割成词序列，这种技术就是中文自动分词技术。中文自动分词技术是 索引处理的基础，也是制约中文信息处理技术的发展瓶颈。由于自然语言的模糊 性和汉语一些本身特点，中文自动分词主要存在以下两个难点： 1 歧义的消除 歧义问题是分词过程中不可避免的难点。统计结果表明，在汉语文本中，歧 义现象出现的概率约为1 11 0 ，歧义字段的识别和处理严重影响着分词系统的分 词精度n9 j 。歧义的根源主要归结为以下三个方面： ( 1 ) 由自然语言的二义性引起的歧义。如句子“美国会采取措施制裁伊朗。 既可以切分成“美国会采取措施n 裁伊朗 ，也可以切分成“美国会采取 措施n 裁伊朗”，单看这个句子，人工也很难认定那个是正确的，只有在结合 上下文语境才能做出的正确的切分。 ( 2 ) 由人工分词不会但机器分词引起的歧义。如“当原子结合成分子时”， 机器会成“当原子结合成分子时”，人工很容易做出正确的切分“当原子 结合7 成f 食子? 时”o ( 3 ) 由分词词典的大小而引起的歧义，词典不可能包含所有的词。如句子 “李红军是一名教师。”，机器切分成“李红军是一名教师”，这里“李红军 是一个人名，应该被完整的切分出来。这种歧义无论分词词典多大都无法避免。 2 对未登录词的识别 在大规模文本处理中，有些词依靠分词词典无法识别出来的，这些词称为未 登录词，主要包括人民、地名、机构名。对未登录词的识别和处理也直接影响中 文文本处理的正确率。 有一个分词方法可以使检索系统达到极高的查全率，那就是将句子按单字切 分，然后建立单字索引。但是这种单字索引由于粒度太细，会导致索引文件比词 索引文件大几倍，另外，在查询的时候，一个词语要查询索引文件很多次，然后 求相邻位置交集，这样计算量大大增加，查询响应时间会变长很多。所以这种按 单字分词和索引的方式几乎没有多少实用价值。 2 2 2 中文自动分词算法介绍 经过2 0 多年的发展，人们研究出了几十种中文分词算法。这些分词算法可 以分为三类：机械分词法、语义分词法、人工智能法。后两类分词算法还不成熟， 1 0 硕士学位论文 第二章理论基础与关键技术研究 目前实用的自动分词系统基本上是以机械分词法为主，辅以少量的词法、语法和 语义信息。 1 机械分词法 机械分词算法按照一定的策略组织一个分词词典，扫描待切分的文本内容 时，按照一定的算法去匹配分词词典，其中不涉及到太多的词法、语法、语义等 关于语言自身的信息。词典中词条的数目与词典的组织结构都直接影响最后的分 词效果。机械分词法有正向最大匹配法( m m 法，m a x i m u mm a t c h i n gm e t h o d ) 、 逆向最大匹配法( r m m 法，r e v e r s em a x i m u mm a t c h i n gm e t h o d ) 、双向最大匹配 法、最佳匹配算法、逐词遍历法、二次扫描法、部件词典法、设立标志法等。下 面介绍一下前面三种最常用的算法。 正向最大匹配法，用m a x l e n g t h 表示最大词长，按照从左到右的顺序，首先 从汉字串中取长度为m a x l e n g t h 的子串在分词词典中查找匹配词条。若词典中存 在这个词，则切分出这一子串，指针后移m a x l e n g t h 个汉字后继续切分，否则， 子串长度减一，再与词典继续匹配。若长度为2 的子串还不能在词典中查到，则 取当前汉字为词，指针后移一个汉字继续匹配。根据每次匹配失败后是增加还是 减少子串长度，又可再分为正向增字最大匹配法和正向减字最大匹配法。该方法 按照从左到右，从长到短的顺序进行扫描匹配，原理简单，易于在计算机上实现， 时间复杂度也较低。但是对于分词过程中遇到的歧义问题，单纯依靠该分词法无 法识别。例如字符串“非常用词汇 ，用m m 法的切分结果是“非常用词汇 ， 而正确的切分结果应该是“- - ：l l z 常用词汇 。 c 主o d ! i t2 - 3 逆向最大匹配算法流程 硕士学位论文 第二章理论基础与关键技术研究 逆向最大匹配算法原理与m m 法相似，只是扫描方向不同，是由右向左扫 描。逆向最大匹配法的优点是提高了切分的准确率。逆向最大匹配法算法流程图 如图2 3 所示。一般说来，逆向匹配的切分精度略高于正向匹配，遇到的歧义现 象也较少。统计结果表明，单纯使用j 下向最大匹配法的错误率为1 1 6 9 ，单纯使 用逆向最大匹配法的错误率为1 2 4 5 ( 这可能是因为汉语的中心语靠后的特 点) 引。但这种精度还远远不能满足实际的需要。由于逆向分词需要将分词词典 中词条逆向，给词典的组织带来不便，所以通常也不推荐采用此方法。 无论正向最大匹配法还是逆向最大匹配法，其程序易于实现的优点是显而易 见的，但是最大词长m a x l e n g t h 难以确定，当m a x l e n g t h 较大时，该算法的时间 复杂度明显提高，m a x l e n g t h 较小时，则无法识别超过m a x l e n g t h 长度的词，导 致切分正确率降低，且两者都不能识别歧义字段。所以由此引入了双向最大匹配 法。即是在文本进行扫描时，同时使用正向和逆向最大匹配法。汉语文本中大多 数的句子，m m 和r m m 的切分完全重合且正确，而其余通过删和r m m 切分不同的 句子中，9 0 以上至少有一个是正确的，只有很少的句子，或者删和r m i 的切分 虽重合却是错的，或者删和r m m 切分不同但两个都不对，由此可以看出采用m m 和r m m 可以解决绝大多数的分词问题，这也正是双向最大匹配法在实用中文信息 处理系统中得以使用的原因所在。对于上一例中的字符串“非常用词汇 ，甩 m m 法的切分结果为“非常用词汇 ，而用r m m 法的切分结果为“非常用词 汇 ，由此可见，用r m m 法的识别结果是正确的。双向最大匹配法的优点是克服 了删法中“词中有词 的弊端，但是此方法算法复杂度较高，为了支持正向和 逆向两种扫描顺序，其分词词典的结构较一般词典复杂。 2 非机械分词法 机械分词法主要是以基于字符串匹配的原理进行的，即它以“足够大 的分 词词典为依据，采取一定的处理策略将中文文本中的字符串与词典中的词条逐一 匹配，达到切分目的。由于分词词典的不完备性和中文自身无法穷举的特点，人 们提出了不需要依靠分词词典进行分词的非机械分词法。基于规则的分词法、语 义语法分词法、人工智能法，都可以归结为非机械分词法，其中涉及到许多汉语 语言知识。由于汉语语言的笼统、复杂性，难以将各种语言信息组织成机器可直 接读取的形式，因此目前非机械分词法的研究还处于试验阶段。 2 2 3 基于h a s h 与t r i e 树的中英文混合分词算法 本文打算从效率上改进正向最大匹配算法。正向最大匹配算法中的 m a x l e n g t h 选择非常重要，一般选取词典中最长词的长度( 6 1 0 ) ，而根据文献 1 7 的统计，汉语平均使用词长2 2 9 ，也就是平均情况下要3 7 1 - 7 7 1 次尝试才能 1 2 硕士学位论文第二章理论基础与关键技术研究 完成一个词语的切分，每一次尝试都是一次查词典的过程，在一次查词典过程还 需要多次比较匹配( 比较次数与词典的组织有关) ，可见切分一个词语需要的比 较次数过多。此外，当新加入的词语比m a x l e n g t h 长，则该词是无法被正确切分。 为了减少匹配次数和能够正确切分新加入的长词，本文研究一种基于h a s h 和 t r i e 树的正向最大匹配算法。很多情况下，文本内容都是中英文混合，本文的 分词算法也将能切分中英文混合的文本内容。 整个分词器由分词词典、分词算法构成。 1 分词词典 分词词典的组织直接影响分词的效果和效率。本文采用种高效的基于 h a s h 和t r i e 树的分词词典结构。如图2 4 所示，词典的逻辑结构是一棵t r e 树，树的每层的每个节点是一个数组，数组的每个元素有三个记录：字的机内码 c o d ec o d ec o d e 中