（计算机应用技术专业论文）全文检索技术的研究与实现.pdf

摘要 摘要 随着网络信息资源的急剧增长，出现了越来越多的专业化网站，如何从这些 网站内海量的网络信息中，抽取出全面的、准确的信息，在用户解决问题的过程 中发挥作用，已变得越柬越重要。搜索引擎技术解决了用户检索网络信息的困难， 目f j i 全文检索技术正成为计算机科学界和信息产业界争相研究、开发的对象。 本文针对在北京工业大学技术转移中心网站的实际需要，对全文检索技术在 技术转移中心网站的应用进行了较为深入、系统的研究，通过全文检索系统为网 站的用户提供多方面、更准确的信息。 本文首先对全文检索技术进行了细致的研究，对全文检索的各项技术和基本 原理进行了深入的探讨，详细分析了全文检索系统的结构和索引的组织、库结构 和创建过程，提出了优化索引创建过程的方法，通过把临时文件映射到虚拟内存 中，大大加快对临时文件的访问速度，提高了索引的创建速度。另外对检索的四 种模型、排序算法和中文分词技术进行了重点研究和总结，并针对词典分词法的 不足，改进了最大匹配算法，充分实现了“长词优先”的原则。然后对常用的全 文检索工具包l u c e n e 进行了详细的分析，并与其它开源全文检索方法进行了比 较。 本文还对j 2 e e 平台上典型的m v c 模式和它的具体实现s t r u t s 框架进行了 分析和研究，分析了m v c 框架原理、s t r u t s 框架基本组件和s t r u t s 框架的运行 机制。 本文最后对技术转移中心网站的站内全文检索功能的设计目标进行详细的 论述，设计了全文检索系统的架构和各个功能模块，其中，功能模块设计包括静 态页面模块、动态页面模块的设计，分词方法的优化、l u c e n e 排序算法的改进 以及分词引擎中的字典和网站的索引的设计。通过对分词方法的优化，将单汉字 分词与词典分词两种方法结合起来使用，使检索结果兼具有相关度好和查全率高 的优点。通过对l u c e n e 排序算法的改进，增加了对网页链接的评分和对网站重 要信息的加分，提高了网站内搜索系统的准确度。最后本文根据整体设计和各个 模块的设计完成具体功能的实现，并部署在实际网站中测试运行。 关键词全文检索；垂直搜索引擎；站内检索；中文分词；s t r u t s 框架 a b s t r a c t a b s t r a c t w i t ht h er a p i di n c r e a s eo fn e t w o r ki n f o r m a t i o nr e s o u r c e s ，t h e r ea p p e a r sm o r e a n dm o r ep r o f e s s i o n a lw e b s i t e s i th a sb e c o m em o r ea n dm o r ei m p o r t a n tt h a th o wt o t a k ec o m p r e h e n s i v ea n da c c u r a t ei n f o r m a t i o nf r o mn u m e r o u sn e t w o r ki n f o r m a t i o n w i t h i nt h e s ew e b s i t e st of a c i l i t a t ep r o b l e m - s o l v i n go fu s e r s s e a r c he n g i n et e c h n o l o g y s o l v e dt h ed i f f i c u l t yo fu s e r ss e a r c h i n gi n f o r m a t i o nf r o mt h en e t w o r k ，a n df u l l - t e x t s e a r c ht e c h n o l o g yi sb e c o m i n gt h et a r g e tt h a tc o m p u t e rs c i e n c ea n di n f o r m a t i o n i n d u s t r i e sa r ec o m p e t i n gt or e s e a r c ha n dd e v e l o p i no r d e rt om e e tt h en e e do ft h ea c t u a lr e q u i r e m e n t so ft h et e c h n o l o g yt r a n s f e r c e n t e rw e b s i t ei nb e i ji n gu n i v e r s i t yo ft e c h n o l o g y ，t h et h e s i sg a v ea ni n d e p t ha n d s y s t e m a t i cr e s e a r c ho nt h ea p p l i c a t i o no ft h et e c h n o l o g yt r a n s f e rc e n t e rw e b s i t e ，a n d p r o v i d e dm u l t i - f a c e t e da n dm o r ea c c u r a t ei n f o r m a t i o nf o rt h eu s e r st h r o u g hf u l l - - t e x t s e a r c hs y s t e m t h et h e s i sf i r s tr e s e a r c h e df u l l - t e x ts e a r c ht e c h n o l o g yi nd e t a i l s ，g a v ea ni n d e p t h r e s e a r c ho nt h et e c h n o l o g ya n dt h eb a s i cp r i n c i p l eo ff u l l t e x ts e a r c h ，l a b o r e dt h e s t r u c t u r eo ff u l l - t e x ts e a r c hs y s t e ma sw e l la st h ef r a m e w o r ko fi n d e x ，d a t a b a s e s t r u c t u r ea n dt h ec r e a t i o np r o c e s s ，a n dp u tf o r w a r da no p t i m i z e dm e t h o do fi n d e x c r e a t i o n ，g r e a t l yq u i c k e nt h es p e e do fr e a d i n go ft h et e m p o r a r yd o c u m e n t sa n d i n c r e a s e dt h ec r e a t i o ns p e e do fi n d e xb ym a p p i n gt h et e m p o r a r yd o c u m e n t st ot h e v i r t u a lm e m o r y i na d d i t i o n ，t h et h e s i ss t r e s s e do nr e s e a r c ha n dc o n c l u s i o na b o u tt h e f o u rm o d e l so fs e a r c h ，s o r ta l g o r i t h ma n dc h i n e s es e g m e n t a t i o nt e c h n o l o g y ，a n d i m p r o v e dt h em a x i m u mm a t c h i n ga l g o r i t h m ，f u l l yr e a l i z e dt h e “l o n g - t e r mp r i o r i t y ” p r i n c i p l ea g a i n s tt h el a c ko fd i c t i o n a r ys e g m e n t a t i o n t h et h e s i sa l s oc a r r i e do u tt h e d e t a i l e da n a l y s i so ft h ec o m m o nu s e df u l l t e x ts e a r c hs a d d l e b a gl u c e n e ，a n d c o m p a r e dw i t ho t h e ro p e n s o u r c ef u l l - t e x ts e a r c hm e t h o d s t h et h e s i sa l s oa n a l y z e da n dr e s e a r c h e dt h et y p i c a lm v cm o d e lo nt h ej 2 e e p l a t f o r ma n di t sc o n c r e t er e a l i z a t i o n s t r u t sf r a m e w o r k ，t h ep r i n c i p l e so fm v c f r a m e w o r k ，t h eb a s i cc o m p o n e n t sa n dt h eo p e r a t i n gm e c h a n i s mo fs t r u t sf r a m e w o r k f i n a l l y ，t h et h e s i sd i s c u s s e dt h ed e s i g nt a r g e to ft h ef u l l t e x ts e a r c hf u n c t i o ni n t h et e c h n o l o g yt r a n s f e rc e n t e rw e b s i t e ，a n dd e s i g n e dt h es t r u c t u r eo ff u l l t e x ts e a r c h s y s t e ma n da l lf u n c t i o nm o d u l e s a n dt h ef u n c t i o nm o d u l e s i n c l u d em o d u l ed e s i g no f s t a t i ca n dd y n a m i cp a g e s ，o p t i m i z a t i o no fs e g m e n t a t i o nt e c h n o l o g y ，i m p r o v e m e n to f 1 1 1 l u c e n es o r t i n ga l g o r i t h m ，a sw e l la st h ed e s i g no fd i c t i o n a r yi n t h es e g m e n t a u o n e n g i n ea n di n d e xo ft h ew e b s i t e t h r o u g ht h em e t h o d o fo p t i m i z a t i o no fs e g m e n t a t i o n ， i tc o m b i n e ds i n g l ec h i n e s e w o r d s e g m e n t a t i o nt e c h n o l o g y a n dd i c t i o n a r y s e g m e n t a t i o nt e c h n o l o g y ，w h i c hb r o u g h ta b o u tt h ea d v a n t a g e so fg o o dc o r r e l a t i v i t y a n dh i g hr a t eo fs e a r c h i ti n c r e a s e dt h es c o r eo fl i n k st o w e b s i t e sa n di m p o r t a n t i n f i o 珊a t i o ni nt h ew e b s i t et h r o u g ht h ei m p r o v e m e n to f l u c e n es o r ta l g o r i t h m ，a n dt h e a c c u r a c yo ft h es e a r c hs y s t e mi nt h ew e b s i t e t h et h e s i sr e a l i z e ds p e c i f i cf u n c t i o n s a c c o r d i n gt ot h ef i n a lo v e r a l ld e s i g na n dt h ed e s i g no fv a r i o u sm o d u l e s ，a n dt h e ni t d e p l o y e dt h et e s to p e r a t i n go ft h ea c t u a lw e b s i t e k e y w o r d sf u l l t e x ts e a r c h ；v e r t i c a l s e a r c he n g i n e ；s e a r c hi nt h ew e b s i t e ；c h i n e s e s e g m e n t a t i o n ；s t r u t sf r a m e w o r k i v 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 签名：醢基堑日期：2 彬! “ 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 第1 帝绪论 ! i , i ii 一曼i!皇皇皇曼鼍皇曼曼曼!皇鼍鼍皇皇 1 1 研究背景及现状 第1 章绪论 随着信息时代的飞速发展，计算机网络上出现了越来越多的文本信息，用户 在具备获取最大限度信息量能力的同时，也面临一个突出的问题：如何在上百万 的文本信息中快速有效的获取所需信息? 搜索引擎( s e a r c he n g i n e ) 正是为解决用户的查询问题而出现的，它专门负 责提供用户查询信息。搜索引擎按其工作方式主要可分为三种，分别是全文搜索 引擎( f u l l t e x ts e a r c he n g i n e ) 、目录索引类搜索引擎( s e a r c hi n d e x d i r e c t o r y ) 和元搜索引擎( m e t as e a r c he n g i n e ) 【l 】。全文检索是通过从互联网上提取的各个 网站的信息( 以网页文字为主) 而建立的数据库中，检索与用户查询条件匹配的 相关记录，然后按一定的排列顺序将结果返回给用户，因此他们是真正的搜索引 擎。目录索引虽然有搜索功能，但在严格意义上算不上是真正的搜索引擎，仅仅 是按目录分类的网站链接列表而已。用户完全可以不用进行关键词( k e y w o r d s ) 查询，仅靠分类目录也可找到需要的信息。如y a h o o 雅虎。元搜索引擎在接受用 户查询请求时，同时在其他多个引擎上进行搜索，并将结果返回给用户【2 1 。 全文检索就是指计算机索引程序通过扫描文章中的每一个词，对每一个词建 立索引，当用户查询时，检索程序就根据事先建立好的索引进行查找，并将查找 的结果反馈给用户的检索方式1 3 j 。相对于其它检索技术，全文检索技术更加复杂， 它不仅要查询结构化数据，还要查询非结构化数据。由于使用全文检索技术能够 高效、快捷、充分的使用网络资源，因此全文检索技术早已成为网络时代的主流 技术。 目前在网上使用的全文搜索引擎已经有很多，比较著名的有g o o g l e ， i n f o s e e k 等等。国内也建立了很多的全文搜索引擎，比如：百度等。 i n f o s e e k 是一个简单但是功能强大的全文检索工具，它的一个优点是有一个 面向主题搜索的可扩展的分类。用户可以把搜索短语和相似的分类目录的主题短 语相互参照，而那些主题短语会自动加到你的查询中去。使你的搜索有更好的主 题相关性。 g o o g l e 是当前搜索准确度和用户查询相关度最好的全文搜索引擎。它的主 要优势在于：1 、大容量的页面存储空间。据称g o o g l e 目前收录的w e b 网页总 量已经高达8 0 亿。2 、及时响应速度。据统计，g o o g l e 的普通搜索花费的平均 时间在0 3 秒以内，这得益于其数百台的高性能硬件服务器系统和分布式并行查 北京t 业人学t 学硕i + 学位论文 询软件系统。3 、查询返回的结果不仅仅集中于大型热门网站，而更多的是针对 特定的w e b 页面。这样能够获得较高的用户查询相关度和准确度，因为用户往 往需要得到有更多实际内容和包含更多有用信息的网页页面，而不是热门流行网 站的内容【4 1 。 百度是使用最普遍的中文全文搜索引擎。百度一直以开发最符合中国人使用 习惯的搜索引擎为己任，经过几年多努力，百度已成为世界上最强大的中文搜索 引擎。它的核心技术是超链分析技术，是新一代搜索引擎的关键技术，已为世界 各大搜索引擎普遍采用。超链分析就是通过分析链接网站的多少来评价被链接的 网站质量，这保证了用户在百度搜索时，越受用户欢迎的内容排名越靠前。更大、 更新、更快使百度在中文互联网拥有天然优势，目前百度支持搜索8 亿中文网页， 并且每天都在增加几十万新网页，是世界上最大的中文搜索引擎。 全文检索的核心技术是将源文档中的所有的基本元素的出现信息记录到索 引库中。在中文系统中，基本元素可以是单个汉字字符，也可以是词。因此存在 两种基本的索引库结构，即基于字表的索引库和基于词表的索引库。字表法和词 表法各有优缺点。国内学者对此都各有侧重研究，前者实用性很强，构建直观方 便，纵观近几年单汉字标引和检索技术的发展，其发展趋势可归结到两点：一是 在单汉字标引和检索技术中引入受控标引和检索的技术和思想；二是引入人工智 能技术。检索方面，比较实用的是“首字直接匹配法”。词表法多集中在中文自 动分词研究，自然语言统计分析等方面。 近年来，中文全文检索系统有了一定的发展，但相比国外的英文检索系统的 发展，还有一定的滞后。目i j 已有的中文全文检索系统的信息检索精度和准确性 还不高。 作为全文检索技术的重要组成部分，中文分词技术和各种常见格式文档的处 理方式是研究和应用必然涉及的两个方面，目前使用最为广泛的中文分词方法是 词表切分法，这种方法的核心是词表的匹配方法。这种方法以“长词优先”原则 在绝大多数情况下符合人们的语言习惯作为前提，在词库的支持下对中文进行准 语法和准语义的切分( 意即这种语法和语义的识别完全取决于所建立的词库) 。然 而，在具体实现最大匹配算法时采用中文字串匹配词表的方法来实现，这样的方 式将导致大量的不必要的字符串比较操作，从而严重影响了其分词效率。在中文 分词的解决方案中，走在国内业界最前沿的是中国科学院计算机技术研究所研制 出的基于多层隐码模型的汉语词法分析系统，该系统的功能包括中文分词、词性 标注、未登录词识别等，分词正确率高达9 7 5 8 【5 】。这样一个通用分词系统的设 计模式对于开发l u c e n e 的中文分词模块是非常有借鉴意义的。 目前，针对各种格式文档的处理，其主要实现方式是将各种格式文档先转换 为某种中间格式，然后对中间格式进行索引和查询。合肥工业大学的李毅和山西 第1 币绪论 省网络管理中心的陈庆伟等人在他们各自设计实现的系统中均采用x m l 格式文 档作为中间格式，通过x m l 强大的数据表达能力和平台无关的特性1 6 j ，这种方法 可以提供一个通用的数据源格式，使统一处理各种格式文档成为可能。 随着网络在各行业内的蓬勃发展，出现了越来越多的面向各个主题的网站， 同水平网站( 又称综合性网站) 相比较，专业化网站( 又称垂直网站) 的注意力 集中在某些特定的领域或某种特定的需求，提供有关这个领域或需求的全部深度 信息和相关服务。因此用户迫切需要一个数据分类细致、准确、全面、更新及时 的面向主题的全文搜索引擎来获取主题资源信息。在这种情况下，以全文检索技 术为核心的专业搜索引擎应运而生，专业搜索引擎也称专用搜索引擎、垂直搜索 引擎、实时搜索引擎等，是搜索引擎发展史上的一块里程碑。它保证了对某一领 域信息的完全收录与及时更新，避免了搜索时强大的“噪音”，提高了查询效率， 在提供专业信息方面有着其它检索工具无法比拟的优势1 7 j 。 专业搜索引擎具备有效的信息采集策略，索引更新周期大大缩短，通常能在 卜2 天内提供更新的网上专业领域信息查询，甚至能在数小时内更新查询信息。 专业搜索引擎面向某一特定的专业领域，专注于自己的特长和核心技术，保证了 对该领域信息的完全收录与及时更新。它最大的优势就在于能够把具有相同兴趣 点的人们集中在一个“主题社区 内，及时集中提供各种专业资源查询。同时专 业搜索引擎站点也提供了一个相互交流、共享经验和教训、展望行业发展前景的 机会和场合，双向交流和互动性明显，因此受到越来越多的用户的欢迎。据赛迪 网( w w w c c i d n e t c o m ) 的“国内搜索引擎市场调查报告显示，9 2 的网民认为将 来非常可能或可能使用垂直型的专业搜索引擎瞄j 。 1 2 课题来源 国外全文检索软件的发展比较成熟，并且己经得到了广泛的应用，但由于中 西方文字存在着很大的差异，国外的全文检索软件对于中国用户来说有很多不适 用的地方；同时，由于当前中文全文检索软件的丌发缺乏平台，国内全文检索系 统的实现很多都是基于关系数据库开发的，或者是基于通用数据库系统提供的全 文检索功能开发的。另一方面，国内一些虽称为全文检索数据库，但其实质是通 过检索关系数据库里的结构化数据，如标题、作者、关键字、摘要等，然后链接 而获得全文，真正实现全文检索的并不多。目前在全文检索领域做得比较好的多 是一些学术论文数据库和专业数据库，如清华同方开发的中国期刊全文检索系 统，北大与3 m 公司合作开发的中国对外经济贸易法律全文检索系统一j 。 随着网络化进程的不断推进，许多工作都需要利用高效、快捷的网络平台来 进行处理，而这促进了专业化的网站( 又称为垂直网站) 的不断发展。基于这一 北京t 业人学t 学硕i + 学位论史 背景，我校利用了现有的先进技术建立了具有一站四库结构的技术转移中心网 站。该网站为技术研发单位和生产企业提供信息服务，成为他们之问的合作的桥 梁，为那些有市场应用价值的新技术能够快速的应用在生产活动中创造了有利的 条件，也为有技术难题和有技术需求的企业解决了难题。 为了更好的为网站的个人和企业用户提供信息服务，站内全文检索功能是必 不可少的，它可以为网站的用户提供关于某个关键字的各方面信息，包括专家方 面、需求方面、成果方面、中介方面以及新闻方面的全方位信息，有助于用户更 好的解决问题。因此站内全文检索功能是网站较为重要的辅助功能，本课题正是 来源于技术转移中心的网站。 1 3 课题研究意义 本课题对全文检索的相关技术进行了较为深入的研究，重点放在全文检索技 术的应用上，对中文分词技术、索引和检索的相关技术、排序算法、多种格式文 档统一处理技术做了重点研究。 对于技术转移中心的网站用户来说，如何能够一次获得关于某关键字的各个 方面的信息对于快速分析和解决问题十分重要。然而对于不太熟悉网站结构或者 想要快速、全面的搜集关于某项技术的各方面信息的人来说，确实有一些难度， 或是要多花一些时间。站内全文检索则可以解决这个问题，它可以准确、快速、 全面的向用户提供关于某项技术的各方面的技术信息和服务信息，这样网站内所 有的模块都可以参与到为用户解决问题的服务中，使信息的利用效率更高。 虽然这个系统是针对技术转移中心网站开发的，但对其它的垂直网站也有很 好的借鉴意义，通过对一些模块的增加和修改，就可以实现其它垂直网站的站内 全文检索功能。 1 4 本论文的主要内容及结构 本文主要对全文检索技术进行分析，并对开源工具开发包l u c e n e 的基本功 能和扩展性进行研究，在此基础上设计并实现一个基于l u c e n e 的全文检索系统， 并在技术转移中心网站上部署和应用，实现网站的站内全文检索功能。 论文的整体结构如下： 第一章：绪论。本章探讨了课题的研究背景，课题来源及研究意义，并对目 前全文检索的发展和面临的一些问题进行了分析。 第二章：全文检索技术研究。本章对全文检索技术进行了详细的分析，重点 探讨了全文检索系统的结构和基本原理，分析了检索模型、排序算法、中文分词 技术，并对词典分词中常用的最大匹配算法进行了改进，本章最后对项目中使用 4 第l 章绪论 的开源工具包l u c e n e 进行了分析。 第三章：m v c 模式s t r u t s 框架技术。本章对在全文检索系统中实际使用的 m v c 模式的原理进行了介绍，并对其中采用的s t r u t s 框架运行机制进行了分析。 第四章：技术转移网站站内全文检索系统的设计。本章主要对全文检索系统 的设计过程进行了详细的说明。首先对整体的设计目标和功能进行分析，再分别 介绍了每个功能模块的设计方案，并对分词方法和排序算法进行了优化和改进。 第五章：站内全文检索系统的实现。本章对基于l u c e n e 的站内全文检索系 统进行了实现，并对其在实际网站中的应用测试进行了展示。 结论：总结了本课题的研究情况，并对下一步研究提出了设想。 第2 章伞文柃索技术研究 2 1 概述 2 1 1 检索 第2 章全文检索技术研究 随着计算机技术的发展，计算机辅助检索也存在着一个发展过程，由检索结 果来看，从提供目录、文摘等相关的二次信息检索到可以直接获得电子版的全文； 由检索方法来看，从对特定关键词或者如作者、机构等辅助信息作为检索入口的 常规检索到以原始文献中任意词检索的全文检索等等i l o j 。其中，全文检索由于其 包含信息的原始性、信息检索的彻底性、所用检索语言的自然性等特点在近年来 发展迅速，成为一种非常有效的信息检索技术。 2 1 2 全文检索 全文检索技术是一种面向全文、提供全文的新型检索技术，首先计算机索引 程序通过扫描文章中的每一个词，对全文建立一个能精确定位每个字词的索引， 这点克服了传统顺序索引在多文献集合和复杂查询条件下检索效率低的不足【1 1 1 。 当用户查询时，检索程序就根据事先建立好的索引进行查找，并将查找的结果反 馈给用户。 2 1 3 全文检索系统 全文检索系统是指按照全文检索技术理论建立起来的用于提供全文检索服 务的软件系统。一般来说，全文检索系统需要具备建立索引和提供查询这两项基 本功能。功能上，全文检索系统核心具有建立索引、增加索引、优化索引、处理 查询返回结果集等功能。结构上，全文检索系统核心具有索引引擎、查询引擎、 文本分析引擎、对外接口，加上各种外围应用系统等共同构成了全文检索系统【1 2 】。 图2 - 1 展示了上述全文检索系统的结构与功能。 从图2 1 中看出，全文检索系统中最核心、最关键的部分是全文检索引擎部 分，这部分从功能模块上可以划分为文本分析模块、创建索引模块、查询索引模 块。索引的准备工作和搜索的应用都是建立在这个引擎之上。由此可见，一个全 文检索应用的优异程度，根本上是由全文检索引擎来决定。因此提升全文检索引 北京t 业人学t 学硕 。# 位论文 擎的效率即是我们提升全文检索应用效率的根本。另一个方面，一个优异的全文 检索引擎，在做到效率优化的同时，还需要具有丌放的体系结构，以方便管理员 对整个系统进行优化，或者是添加原有系统没有的功能【1 3 】。比如在现代多语言的 环境下，有时需要给全文检索系统新添加处理某种语言或者处理某种格式文档的 功能，比如支持日文处理的功能，支持对o f f i c e 文档处理的功能。 i i 一一i 图2 - 1 全文检索系统结构图 f i g u r e2 1f u l l - t e x ts e a r c hs y s t e ms t r u c t u r es k e t c h 2 2 全文检索系统组织 全文检索主要由两方面的核心技术结合而实现：一是建立和维护索引库，二 是提供快速有效的检索机制。因而在设计时，要针对实际应用，确定索引库的数 据结构和存储方式，以及如何从原始文档中抽取有用信息，采取一定的方式记录 到索引库中，并在此基础上提供快速有效的检索机制。同时为了方便用户的信息 查询，还应该在提供最基本的单个字符串检索功能基础上，支持多种复杂的高级 检索功能【l4 1 ，例如组合检索、模糊检索等。 8 第2 帝伞文柃索技术研究 2 2 1 索引组织 全文检索中索引的组织方法有两种，即正排表和倒排表。j 下排表是以文档的 i d 为关键词，表中记录项记录文档中每个词的位置信息，查找时扫描表中每个 文档中词的信息直到找出所有包含查询关键词的文档。正排表结构如图2 - 2 所 示。这种组织方法建立索引比较方便，结构简单且易于维护：但是在查询的时候 需对所有的文档进行扫描以确保没有遗漏，这样就使得检索时问大大延长，检索 效率低下i l5 。所以通常都采用另一种词表组织方法：倒排表。 文档l 文档2 关键词1 关键词1 图2 - 2 止排序结构 f i g u r e2 - 2f o r w a r ds o r t e ds t r u c t u r e 倒排表按词或字为关键词( 字) 进行索引，表中关键词对应的记录表项用来记 录所有出现这个词的文档，一个表项就是一个词表段，记录该文档的i d 和该词 在该文档中出现的位置信息。倒排表结构如图2 3 所示。由于每个词对应的文档 数量在动态变化，所以倒排表的建立和维护都较为复杂，但是在检索的时候由于 可以一次得到查询关键词所对应的所有文档，所以效率远远高于正排表 1 6 】。在全 文检索中，检索的快速响应是一个最为关键的性能指标，而索引建立由于在后台 进行，效率相对低一些，不会影响整个搜索引擎的效率。 卤 图2 - 3 倒排序结构 f i g u r e2 - 3r e v e r s es o r t e ds t r u c t u r e 裂 北京- f , i k 火学t 学硕i ? 学化论文 2 2 2 索引库结构 建立一个全文检索系统，首先要将源文档转换为能够进行文本查找的全文索 引库，包括全文的分割处理以及规范格式等，这称为前处理工作，前处理完成后， 即可开始建立索引，先过滤掉源文档中的排版符号，格式控制符等，再把源文档 中的每一个字的出现位置信息记录到索引库中。 前期处理工作主要将网页的内容全部提取出来，去除无用的信息，例如网页 的各种标记，再转换成统一的格式类型。在本文检索系统的处理中，处理的源文 件包括静态文件和动态文件两种，静态文件要去除文件内容中的大量标记，如 h t m l 标记，动态文档则可直接抽取出数据库中的相应字段内容。处理完成后将所 有内容转换成字符串类型的对象，最后一个任务就是根据一个词典，用一个“切 词软件，从处理完的字符串中切出所含的词语，去掉诸如“的”，“在等没有 内容指示意义的词，称为“停用词”【1 7 】。这样一篇网页就主要由一组词来近似代 表了，如p = t 。，t 。，t 。 。 索引库对每个不同的字符都保存一个字表，记录同一个字在文档中的所有出 现位置。建库时只要扫描所有文档，将读到的每个字符的位置信息加到对应的字 表中即可。字表是索引库中最主要的部分，在每个汉字字符对应的字表中，包含 该字符出现在所有文档中的全部位置。为了区分每个位置值属于哪个文档，每个 字符的字表被分为多个字表段，每段对应一个文档，记录该字符在此文档中的出 现位置。字表采用倒排文件结构引，如图2 - 4 所示。 图2 4 字表及字表段结构 f i g u r e2 - 4c h a r a c t e rt a b l ea n di t sf i e l ds t r u c t u r e 2 2 3 索引的创建过程 索引创建过程不需要排序，分为如下两步。第一步分析源文档，产生临时的 中间文件，我们称为分析过程。当前只处理g b 码字符，其中包含全部字符，既 有汉字，又有一般的数字，标点符号等。g b 码第一个字节的范围是0 x a l 0 x f 7 ， 第2 章伞义柃索技术研究 第二个字节的范围是0 x a l 0 x f e 。汉字从“啊开始，首字节为1 7 6 2 4 7 ，第二 个字节为1 6 1 2 5 4 。根据这种分布规律，可以方便地定位每个字符对应的字表信 息。源文档经过处理，其包含的每个字符的对应信息写到一个临时的中间文件。 对于每个字符，其在临时文件中的对应信息包括：该字所出现的当前文档编号， 在该文档中的出现频率，出现的位置序列和该字符出现在下一个文档中的数据的 指针。第二步处理临时文件，依次从临时文件中读取每个字符出现在每一篇文章 中的数据信息，生成最终的倒排文件，在这里称为创建过程【1 9 】。生成的最终倒排 文件中包含每个字符出现在所有文档中的信息。 随着处理数据集规模的增大，相应的分析源文档的时间增大，但第二步创建 过程所需的时间也迅速增大。该过程需要大量的随机读取操作来遍历每个字符对 应的所有信息。当数据的规模增大时，遍历每个字符的临时数据的操作变得很慢。 这是由于字符对应的每个字表的数据在临时文件中有一定距离，遍历需要不断地 移动文件指针来读取这些数据。 利用操作系统提供的虚拟内存技术可以优化索引的创建过程。w i n d o w s 操作 系统用虚拟内存来动态管理运行时的交换文件。为了提供比实际物理内存还多的 内存容量以供使用，w i n d o w s 操作系统占用了硬盘上的一部分空间作为虚拟内 存。当c p u 有要求时，首先会读取内存中的资料。当内存容量不够用时，w i n d o w s 就会将需要暂时储存的数据写入硬盘。内存映射文件技术是w i n d o w sn t 提供的 一种新的文件数据存取机制。利用内存映射文件技术，系统可以在2 g b 的地址 空间中为文件保留一部分空间，并将文件映射到这块保留空间。一旦文件被映射 之后，w i n d o w sn t 将仔细管理页映射、缓冲以及高速缓冲等任务。通过把临时 文件映射到虚拟内存中，可以大大加快对临时文件的访问速度。 对于较小的源数据集，分析处理后生成的临时文件也较小，使用内存映射文 件可以大大加快创建过程。但当数据规模增大时，该方法的性能迅速降低，甚至 比没有使用内存映射文件都差。性能的降低是由于同一个字符相邻的数据在临时 文件中距离过大，导致大量的缺页中断，系统性能大大降低。解决该问题的有效 方法是把原有的单个的大的中间文件分成多个小的临时文件，在分析过程中生成 多个小的临时文件，创建过程依次处理每个临时文件，将其映射到虚拟内存中， 可以充分利用直接内存访问的速度，并且减少缺页中断。 2 2 4 检索功能 先分析系统的检索模型。设t = t l ，t 2 ，t t ) 为系统的特征项( t e r m ) 集合， p = p l ，p 2 ，p p ) 为网页信息库中的网页信息集合，如果再设项t 与网页p 的相关度 函数为r = “t ，p ) ( 如果相关则为取值为大于0 的正数) ，则系统的索引库可以表 北京t 业人学丁学硕卜7 ：1 矽论文 示为i = i t ( t ，p ) o ，( t ，p ) t p ，整个系统可以定义为一个三元组 s = l ( t ，p ，i ) t p i 。这样，对于一个关键词w 来说，所有检索结 果的集合q 为q ( w ) = pl ( t e r m ( w ) ，p ) r ，p p ) ，也就是说与关键词对应项相 关的网页集合。从检索模型看，检索结果主要决定于两个因素：关键词与特征项 的匹配和相关度的计算。 检索功能的实现就是基于索引库的位置匹配。例如对于一个检索词“先进制 造”，首先是找到这四个字相应的索引序列，然后进行匹配运算。假设“先”字 在数据块中出现的位置为第m 个文档中第k 个字节，如果要命中，则“进字必 定也在第m 个文档，位置则是第k + 2 个字节。同理，“制 字的位置应该与“进” 字相差两个字，为第m 文档中的第k + 4 个字节，“造 字为第m 文档中的第k + 6 个字节1 20 。检索的过程应该如图2 - 5 所示。 信息检索模型是将文档表示、查询以及它们之间关系进行建模的框架，它由 一个三元组表示f dqr ( q 。，d 。) 。其中，d 是文档集中的一组文档逻辑视图； q 是一组用户信息需求的逻辑视图，这种视图被称为查询；r ( q ；，d 。) 是一个排序 函数，该函数输出一个与查询q 。q 和文档表示d ，d 有关的实数。这样就在文 档之问根据查询q ；定义了一个顺序。 从文档的内容上，信息检索有四种传统模型：布尔模型( b o o l e a nm o d e l ) 、 向量空间模型( v e c t o rs p a c em o d e l ，v s m ) 、概率模型( p r o b a b i l i s t i cm o d e l ) l 文件头( “先“) m ( k )、 i 文件头( “进“) m ( k + 2 ) j 一一一一一一一一， i 文件头( “制“) m ( k + 4 ) 。 l 文什头( “造“) m ( k + 6 ) 图2 5 索引数据库的检索 f i g u r e2 - 5s e a r c ho fi n d e xd a t a b a s e 和逻辑模型( l o g i cm o d e l ) 。在四种传统模型的基础上，又演变出了各种其他模 型，如模糊布尔模型、神经网络模型、推理网络模型等。 2 2 4 1 布尔模型 布尔模型是信息检索系统提供的基本模型，它将文本表示成布尔表达式，然 第2 币伞文榆累技术研究 后再通过与用户的查询表达式进行逻辑比较来检索相关文本。标准布尔逻辑模型 采用二元逻辑。在布尔模型中，首先要针对文本定义一系列的二元特征变量，这 些特征变量一般是从文本中提取出来的文本索引关键词，有时也包括一些更为复 杂的特征变量，如数据、短语和手工加入的描述词等。其次，使用这些特征变量 的集合来表示文本d i = ( d “，d 胁d ；。) ，其中，n 是特征项的个数；d 。为1 或者o ， 如果第k 个特征项在文本d i 中出现，就赋予1 值，反之置为0 值。同时，用户可 以根据检索关键词在文本中的布尔逻辑关系，用“八 ( a n d ) 、“v ( o r ) 、“1 ， ( n o t ) 等逻辑运算符将多个关键词连接成为一个逻辑表达式来递交查询1 2 2 。通 过对文本表达式与用户查询表达式的逻辑比较进行检索，检索出的文本或者与查 询相关，或者与查询无关。 2 2 4 2 向量空间模型 向量空间模型是实验环境中应用最多的检索模型。在向量模型中，信息获取 系统如果涉及n 个关键词，则建立n 维的向量空间，每一维都代表不同的关键词， 信息库中的文本以及用户的查询都通过该空间中的向量来表示。文档向量是一个 n 元组，其中的每个坐标都通过对应关键词的权重来表示。权重越大，则相应关 键词对于该文档来说越重要。查询向量与文档向量类似，只不过查询向量中的权 重表示对应关键词对于用户来说的重要程度，一般来说权重1 表示期望在文档中 出现的词条，而0 表示不希望出现的词条。文档向量中的词条的权重一般基于词 条在文档中出现的频率，经典的权重计算公式是t f t d f 公式，下面对t f i d f 公 式进行简要的分析【2 3 1 。 在空间向量模型中，文档d 与查询q 的相关性可以用它们包含的共有词项的 多少来度量。假设所有词项集合为w ，那么文档d 和查询q 可以表示为： d = ，q = ( 2 1 ) 其中，w 。，w 。，w 。w ，m 。和n 。分别代表在文档和查询中第k 个词项的出现 次数。引入词频的概念，令 国：生( 2 2 )c 巩= - 一一l z zj j = l 并且用词频来表示文档，得 d = ( q ，0 ) 2 ，( 0 n 对于多个文档的索引库，可将词频的概念引申到多个文档，并且简化相关性 为二元逻辑( 文档中有该词项则相关，无则无关) ，定义词项的文档频率d f 的概 念，用k ；表示词项w ；在文档集合d 中相关的文档个数，m 表示文档集合d 的大小， 则有 d f ：兰( 2 3 ) 设定 纠g 沼4 ， 为倒置文档频率i d f ，它表示词项的文档频率的倒置。将词频和倒置文档频率结 合起来，用i d f 来校正t f ，就得到了t f - i d f 算法的词项权重公式： 哆= 珥啦= o m 地 协5 ， j l 畅 如果将查询也看作一个文档