（计算机软件与理论专业论文）中文搜索引擎的快速检索方法研究.pdf

摘要 摘要 当前，搜索引擎是互联网的一个重要组成部分，也是智能信息处理领域的一个研究 热点问题。研究快速搜索引擎的关键算法和实现机制具有重要的学术意义和实际应用价 值。一个完整的中文网页检索的索引器的构建涉及到索引的数据结构的选取，倒排文件 是大规模中文网页检索中最常用的数据结构，怎么样生成倒排文件，怎样在倒排文件中 快速检索是当前搜索引擎研究的重点。 本文首先阐述了搜索引擎的组织结构、原理和实现机制，从构建网页库、词典库， 到分词算法、建立特征库、索引库，以及建立基于倒排序的快速索引机制，考察了其中 的关键数据结构和快速算法，通过一定数量的网页库测试了系统的性能，得到了比较满 意的结果。论文的最后，在关键词倒排文件的基础上，介绍了移动搜索的特点、关键技 术、与3 g 的关系，另外设计出一种适用于3 g 网络的移动搜索模型。模型中采用基于 关键词倒排文件的检索方式，同时，考虑到移动终端屏幕尺寸小的特点，通过对搜索到 的网页进行分割，抽取出与查询要求最相关的主题区域提交给用户，方便移动用户便捷 准确的获取到w ，e b 信息。 论文的重点在于生成了便于二分搜索的结构化词典，在词典的基础上，改进了前向 最大切词算法，实现了基于关键词倒排索引的快速检索算法，构建了词典、索引表和倒 排表互相之间的关系，设计出一种基于倒排文件的移动搜索模型。 关键词：检索；网页特征表；索引；倒排文件；实时性；移动搜索；网页分割 a b s t r a c t a b s t r a c t a tp r e s e n t t h es e a r c he n g i n ei sa l li m p o r t a n tc o m p o n e n to ft h ei n t e r n e t ；i ti sa l s oah o t r e s e a r c ht o p i ci nt h ei n t e l l i g e n c ei n f o r m a t i o np r o c e s s i n gf i e l d t h es t u d yo ft h ef a s ts e a r c h e n g i n e se s s e n t i a la l g o r i t h ma n dt h er e a l i z a t i o nm e c h a n i s mh a sc e r t a i na c a d e m i cs i g n i f i c a n c e a n dp r a c t i c a la p p l i c a t i o nv a l h e t h ei n d e x e r sc o n s t r u c t i o no fc o m p l e t ec h i n e s ew e b s i t e r e t r i e v a li n v o l v e st h es e l e c t i o no fi n d e x sd a t as t r u c t u r e i n v e r t e df i l ei st h ec o m m o n l yu s e d d a t as t r u c t u r eo fl a r g e s c a l ec h i n e s ew e bs i t er e t r i e v a l t h er e s e a r c h sh o ts p o t sa r eh o wt o g e n e r a t et h ei n v e r t e df i l e a n dh o w r e t r i e v eq u i c k l yi nt h ei n v e r t e d 1 1 1 i sa r t i c l ef i r s te x p a t i a t e dt h es e a r c he n g i n e so r g a n i z a t i o n a ls t r u c t u r e ，t h ep r i n c i p l ea n d t h er e a l i z a t i o nm e c h a n i s m ，f r o mt h ec o n s t r u c t i o nh o m e p a g ed a t a b a s e ，t h ed i c t i o n a r yd a t a b a s e ， t ot h ep a r t i c i p l ea l g o r i t h m ，t h ee s t a b l i s h m e n tc h a r a c t e r i s t i cd a t a b a s e ，t h ei n d e xd a t a b a s e ，a s w e l la st l l ee s t a b l i s h m e n tb a s e do nt h em e c h a n i s mo ft h ef a s ti n d e x i n s p e c t e dt h ee s s e n t i a l c o n s t r u c t i o no fd a t aa n dt h ef a s ta l g o r i t h m ，a n dt e s t e dt h es y s t e m sp e r f o r m a n c et h r o u g h c e r t a i nh o m e p a g ed a t a b a s e ，a n dg o tas a t i s f a c t o r yr e s u l t f i n a l l y ，i n t r o d u c e dt h ec h a r a c t e r i s t i c o ft h em o b i l es e a r c h ，t h ep i v o t a lt e c h n o l o g yo ft h em o b i l es e a r c ha n dt h er e l a t i o n s h i pb e t w e e n t h em o b i l es e a r c ha n d3 g d e s i g n e dam o b i l es e a r c hm o d e lw h i c hc o u l db ea p p l i e dt o3 g n e t w o r kb a s e do ni n v e r t e dk e y w o r df i l ei na d d i t i o n t h em o d e la d o p t sr e t r i e v a lm e t h o db a s e d o ni n v e r t e dk e y w o r d sf i l e ，m e a n w h i l e ，t a k e si n t oa c c o u n tt h ec h a r a c t e r i s t i c so ft h em o b i l e t e r m i n a ls c r e e n ss m a l ls i z e ，a n dt h e nc u t su pt h es e a r c h e d - w e b p a g e ，e x t r a c t st h et o p i cr e g i o n w h i c hi sm o s tr e l e v a n tt oq u e r yr e q u e s t st ot h eu s e r s ，s ot h a tt h em o b i l eu s e r sc o u l d c o n v e n i e n t l yg e tt h ea c c u r a t ew e bi n f o r m a t i o n t h ek e yp o i n to ft h ep a p e ri st h ep r o d u c eo ft h es t r u c t u r a ld i c t i o n a r yw h i c hc o n v e n i e n t f o rb i n a r ys e a r c h ，i m p r o v e dt h ec u tw o r da l g o r i t h mg r e a t l yb a s e do nt h ed i c t i o n a r y ，a n d c o n s t r u c t e dt h er e l a t i o n s h i pa m o n gt h ed i c t i o n a r y ，t h ei n d e xa n dt h ei n v e r t e dl i s t ，d e s i g n e da m o b i l es e a r c hm o d e l w h i c hb a s e do ni n v e r t e df i l e k e y w o r d s ：r e t r i e v a l ；w e b p a g ef e a t u r et a b l e ；i n d e x ；i n v e r t e df i l e ；r e a l - t i m e ；m o b i l e s e a r c h ；w e bp a g es e g m e n t l i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取 得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写过的研究成果，也不包含本人为获得江南 大学或其它教育机构的学位或证书而使用过的材料与我一同工作的同志 对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 期： 关于论文使用授权的说明 本学位论文作者完全了解江南大学有关保留、使用学位论文的规定： 江南大学有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允 许论文被查阅和借阅，可以将学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文， 并且本人电子文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定 签名：立垫怎导师弛霪乏生 日 期：o 。o 罗8 、彬 第一章前言 第一章前言 1 1 课题研究的背景和意义 随着互联网的发展和信息时代的到来，互联网为人们方便获取整个w e b 范围内的数 字信息提供了便利。然而，i n t e m e t 上无穷无尽的信息资源是杂乱无章地存放在一起的， 面对海量的数据，搜索引擎已经成为进行互联网信息检索必不可少的工具【1 1 。根据中国 互联网络信息中一l , ( c n n i c ) 在0 9 年1 月份发布的第二十三次中国互联网络发展状况报 告1 2 1 显示：截止2 0 0 8 年1 2 月3 1 日，中国的网民数量达到2 9 8 亿，搜索引擎的使用率是 6 8 o ，是互联网的基础应用。为中国第二大网络应用。我们可以预见，随着时间的推 移，互联网上将会出现更多的内容，用户对信息的需求也会不断的增加。面对庞大的数 据，如何提供更加迅捷准确的检索服务，是未来很长一段时间内搜索引擎的研究和发展 方向【3 1 。 全文检索是指以文本为检索对象，允许用户以自然语言根据资料内容而不仅是外在 特征来实现信息检索的手段【4 】。查全性、查准性和响应速度是衡量全文检索系统的关键 指标。全文检索不仅可以实现对数据资料的外部特征的检索，诸如标题、作者、摘要、 附录等，而且还能直接根据数据资料的内容进行检索，实现了支持多角度、多侧面地综 台利用信息资源。最初的全文检索是通过在文本中逐个字符扫描匹配完成的，不需要全 文索引这样的辅助数据。随着文本集越来越大，人们对全文检索的需求越来越多样，这 种顺序比较效率低下的弊端就凸显出来。人们受到书目索引的启发提出了全文索引的思 想，而本文研究的倒排索引则是目前应用最广泛的全文索引之一。由于传统数据库擅长 于结构化数据的管理，而文本是典型的非结构化数据，它们之间的巨大差异使得全文检 索系统的实现手段以及全文索引的结构与传统数据库截然不同，因此完全照搬传统数据 库的各种技术是不可行的，必须寻求全新的理论和方法来提高全文检索的效率。此外， 文本检索的研究也能够为对其他几种更复杂的多媒体信息检索的研究提供重要的经验 和借鉴。国内外对全文检索的研究方兴未艾，己有一些较成熟的商用产品相继问世。中 文全文检索与英文检索相比，由于自然语言体系不同，索引机制也不完全相同。英文以 词为单位建索引，与字母无关，而中文以字为最小单位。再者，英文的分词以空格和标 点为分界符，而汉字的分词往往依赖于词库。因而中文全文检索与英文实现相比困难些。 不得不承认目前国内的研究水平与国际上还有较大差距，坐等国外成果，然后加以移植 改造的老路是行不通的，因此在国内进行全文检索快速检索方法的研究非常必要1 5 j 。 综上所述，全文检索技术是现代信息检索的一项重要技术，在w e b 搜索引擎、数字 图书馆等领域中都有广泛的应用价值，因此，研究和探索高效的倒排索引技术不仅具有 理论价值，而且极具商业前景【5 l 。 1 2 国内外研究现状 在当前的主流搜索引擎中，索引结构是核心，直接影响着搜索引擎的检索性能和效 率。一个良好的索引结构可以在被检索数据规模庞大的情况下保证检索操作的速度，是 江南大学硕士学位论文 实现高效率检索的一个决定性因素【5 】。常用的文本索引形式有三类，分别是后缀数组 ( s u f f i x a r r a y ) ，签名文件( s i g n a t u r ef i l e ) 和倒排文件( i n v e r t e df i l e ) 。一个搜索引擎可以选 用上述任何一种形式的索引结构，目前最流行的的，应用范围最广的是倒排文件1 6 j 。 倒排文件是一种常用且高效的用于信息检索的索引文件结构，由词典文件和索引文 件两部分组成【7 l 。倒排索引的优点主要是在处理复杂的多关键字查询时，可在倒排表中先 完成查询的交，并等逻辑运算，得到结果后再对记录进行存取，这样不必对每个记录随机 存取，把对记录的查询转换为地址集合的运算，从而提高速度【8 】。 文献【8 】中提出了一种高效的倒排索引结构，在一定程度上能够节省磁盘空间，并且 能支持增量更新和删除。文献【1 0 】中在l u c e n e 的基础上同时引入了索引配置文件，可 针对不同应用背景来灵活定制索引的细节。文献【1 1 d p 针对中文搜索引擎中索引的时效 性和传统倒排索引在更新时的缺点，提出分组索引技术和一种追加索引的更新算法。由 此可见，倒排索引的数据结构成了当前众多学者，机构研究的课题，国内对倒排索引结 构研究的机构主要是北大天网，清华大学智能系统与技术国家重点实验室，天津大学 m m 中心等，对搜索引擎的研究起源于”中国教育科研网”( c e r n e t ) 的一期工程中的子 项目【1 2 】。 清华大学的陆玉昌教授和他的研究生，在国家9 7 3 基础研究基金项目中，实现了一 种高效检索及即时更新的倒排索引，它是w e b m e ( w e bm i n i n ge n v i r o n m e n t ) 原型系统的 一部分，这部分用来对特定的查询进行高效的检索，并支持即时增量索引，即对新加入 的文档可以立即加入索引，且不用重新对原内容进行重索引，并且在更新索引时不会影 响查询的进行【1 1 。北方工业大学也对倒排索引的算法作了很多研究，他们使用倒排表和 散列结合的技术，处理文档，将其相关内容写成倒排表和辅助表【i 引。北京航空航天大学 的刘畅，张辉充分利用字符串前缀个数及排序顺序的潜在规律，提出了一种新的索引结 构。在查找过程中有效地重用了先前的匹配信息，提高了检索的效率i l 刖。 国外最具有代表性的是开放源码的全文信息检索工具包l u c e n e 的索引机制【l 5 。， l u c e n e 使用各种解析器对各种不同类型的文档进行解析1 1 6 1 ，比如对于h t m l 文档， h t m l 解析器会做一些预处理工作，比如过滤文档中的h t m l 标签等，h t m l 解析器 的输出是文本内容，接着l u c e n e 的分词器( a n a l y z e r ) 从文本内容中提取出索引项以及相 关信息，比如索引项的出现频率。接着l u c e n e 的分词器把这些信息写到索引文件中 1 7 , 1 8 l 。 2 第一章前言 t e x tf i l e 卜刑- p p d fp a r s e r w o r dp a r s e r p a r s e r 一心么一 9 每i 亩 图1 - 1l u c e n e 索引机制架构 f i g 1 - 1l u c e n ei n d e x i n gm e c h a n i s mf r a m e w o r k l u c e n e 中反向索引是一种以索引项为中心来组织文档的方式，每个索引项指向一个 文档序列，这个索引中的文档都包含该索引项。相反，在正向索引中，文档占据了中心 的位置，每个文档指向了一个它所包含的索引项的序列。人们可以利用反向索引轻松的 找到那些文档包含了特定的索引项。l u c e n e 正是使用了反向索引作为其基本的索引结构 【l 引。 s e g m e n t l s e g m e n t 2 图1 2 索引文件的逻辑视图 f i g 1 2l o g i c a lv i e wo f t h ei n d e xf i l e 江南大学硕士学位论文 1 3 研究内容和组织结构 1 3 1 研究内容 在日常生活中，无论看什么书，一般分两种看法：一种是顺序浏览法，从前看到后； 另一种是首先翻看目录，找到我们需要或者想要看的内容，那么就直接翻到该页。如果 只考虑看书的效率，第二种方法应该更会得到人们的青睐。在浩瀚的万维网里，当搜索某 个关键字时，我们同样希望能通过类似直接查看目录的手段，快速找到我们想要的信息。 本文的主要研究内容就是如何通过添加索引的数据结构实现中文搜索引擎的快速检索， 主要做了如下的工作： 1 ) 设计和实现中文网页检索系统，系统用来为检索实验提供接口； 2 ) 结构化汉语词典，对词典添加索引，用来方便存储和切词时的二分搜索； 3 ) 优化前向最大切词算法，通过改进切词算法提高检索速度； 4 ) 创建标准格式和压缩格式的网页词频特征表； 5 ) 建立倒排文档库和倒排文件； 6 ) 实现基于原始网页库，压缩格式特征表，倒排文件的检索； 7 ) 设计出一种基于倒排文件的移动搜索模型； 1 3 2 组织结构 整个论文共分为五章，具体的章节内容安排如下： 第一章为绪论，阐述本文的研究背景，意义，国内外的研究现状，从本文的研究内 容出发介绍了索引的结构。对需要研究的倒排索引做了引导性的说明。 第二章介绍中文搜索引擎的工作原理，中文搜索引擎的关键技术，包括如何抓取网 页，提取网页特征，建立索引数据库等，最后一节也是本文的重点之一，阐述为检索实 验开发的中文网页检索系统，为第四章，第五章的实验部分做好前期的准备工作， 第三章介绍了索引的三种数据结构，详细的分析这三种结构的工作原理，索引的数 据结构选取是加快检索速度的重要因素。 第四章是本文研究的重中之中，本章中首先分别对原始网页库，特征表，倒排表这 三种检索数据源进行了详细的实验和分析，在检索的实验的同时，完成了特征表，倒排 文档库，倒排文件的创建，创建了结构化词典，改进了前向最大切词算法等，最后对检 索的实验做了细致的分析和未来的展望，实验中表明，中文搜索引擎的快速检索离不开 倒排文件的索引结构。 第五章在基于关键词倒排文件检索的基础上，设计了一种移动搜索的模型。分别介 绍了移动搜索的概况，移动搜索与3 g 的关系，移动搜索的模型，详细分析了移动搜索 模型的各个功能模块，最后初步的进行了模拟实验。 4 第二章中文搜索引擎 第二章中文搜索引擎 2 1 中文搜索引擎的工作原理 中文搜索引擎起源于传统的信息全文检索理论，即计算机程序通过扫描每篇文章中 的每个词，建立以词为单位的倒排文件，检索程序根据检索词在每篇文章中出现的频率 对包含这些检索词的文章进行排序，最后输出排序结果。与传统的信息检索理论研究不 同，搜索引擎用户看中的是系统的稳定性、速度、易用性和返回的信息量及相关度【1 9 】。 中文搜索引擎中首先由网页蜘蛛抓自动访问互联网，并沿着任何网页的所有u r l 爬到其它网页，重复这个过程，并把爬过的所有网页搜集到服务器中，由索引构建程序 对收集回来的网页进行分析，提取相关网页信息，根据一定的相关度算法进行大量复杂 计算，得到每一个网页针对页面内容中及超链中每一个关键词的相关度，然后用这些相 关信息建立网页索引数据库。当用户输入关键词搜索后，分析搜索请求，由搜索系统程 序从网页索引数据库中找到符合该关键词的所有相关网页。最后对检索结果进行排序后 返回给用户1 2 。 图2 1 搜索引擎的工作原理 f i g 2 1t h ew o r k i n gp r i n c i p l eo fs e a r c he n g i n e 江南大学硕士学位论文 2 1 1 从互联网上抓取网页 利用网络蜘蛛程序自动访问互联网，并沿着任何网页中的所有u r l 爬到其它网页 中，重复这一过程，并将爬过的所有网页收集到服务器中【2 1 2 2 】。如图2 2 所示： 图2 2w e b 信息的搜集 f i g 2 - 2t h ec o l l e c t i o no fw e bi n f o r m a t i o n e 2 1 2 建立索引数据库 由分析索引系统程序对收集回来的网页进行分析，提取相关网页信息( 包括网页所 在u r l 、编码类型、页面内容包含的关键词、关键词位置、生成时间、大小、与其他网 页的链接关系等) ，根据一定的相关度算法进行大量复杂的计算，得到每一个网页，针 对页面内容中及超链接中每一个关键词的相关度，然后用这些相关信息建立网页索引数 据库2 4 1 。 二重至垂至簪一 图2 - 3 分析网页和建立倒排文件 f i g 2 3 a n a l y s i so f t h ep a g ea n dt h ee s t a b l i s h m e n to f t h ei n v e r t e df i l e 6 第二章中文搜索引擎 图2 4 网页预处理系统结构 f i g 2 - 4p a g ep r e p r o c e s s i n gs y s t e ma r c h i t e c t u r e 2 1 3 在索引库中检索 当用户输入关键词搜索后，分解搜索请求，由搜索系统程序从网页索引数据库中找 到符合该关键词的所有相关网页【2 0 1 。 2 1 4 对搜索结果进行排序 所有相关网页针对该关键词的相关信息在索引库中都有记录，只需综合相关信息和 网页级别形成相关度数值，然后进行排序。相关度越高，排名越靠前。最后，由页面生 成系统将搜索结果的链接地址和页面内容摘要等内容组织起来反馈给用户【2 0 1 。 2 2 中文搜索引擎的关键技术 2 2 1 网页抓取 网络蜘蛛即w e bs p i d e r ，网络蜘蛛是通过网页的链接地址来寻找网页，从网站某一 个页面开始，读取网页的内容，找到在网页中的其它链接地址，然后通过这些链接地址 寻找下一个网页，这样一直循环下去，直到把这个网站所有的网页都抓取完为止。如果 把整个互联网当成一个网站，那么网络蜘蛛就可以用这个原理把互联网上所有的网页都 抓取下来。 网络蜘蛛在搜索引擎中占有重要位置，对搜索引擎的查全、查准都有影响，决定了 搜索引擎数据容量的大小，而且网络蜘蛛的好坏直接影响搜索结果页中的死链接( 即链 接所指向的网页已经不存在) 的个数。如何发现更多的网页、如何正确提取网页内容、 如果下载动态网页、如何提供抓取速度、如何识别网站内容相同的网页等都是网络蜘蛛 需要解决的地方【2 4 1 。 2 2 2 中文分词 中文分词技术属于自然语言技术处理范畴，中文是一种十分复杂的语言，让计算机 理解中文语言更是困难。分词的准确性对搜索引擎来说十分重要，如果分词速度太慢， 即使准确性再高，对于搜索引擎来说也是不可用的，因为搜索引擎需要处理数以亿计的 7 江南大学硕士学位论文 网页，如果分词耗用的时间过长，会严重影响搜索引擎内容更新的速度。因此对于搜索 引擎来说，分词的准确性和速度，二者都需要达到很高的要求【2 5 】。 2 2 3 网页特征提取 对于网络蜘蛛来说，抓取网页格式包括h t m l 、图片、d o e 、p d f , 多媒体、动态网页 及其他格式等。这些文件抓取下来后，需要把其中的文本信息提取出来。准确提取这些 信息，一方面对搜索引擎的搜索准确性有重要作用，另一方面对于网络蜘蛛正确跟踪其 他链接有一定影响。 2 2 4 建立索引数据库 由索引系统程序对收集回来的网页进行分析，提取相关网页信息( 包括网页所在 u r l 、编码类型、页面内容包含的关键词、关键词位置、生成时间、大小、与其它网页 的链接关系等) ，根据一定的相关度算法进行大量复杂计算，得到每一个网页针对页面 内容中及超链中每一个关键词的相关度( 或重要性) ，然后用这些相关信息建立网页索引 数据库。同时随着网页库的更新，索引数据库也要随之更新【2 3 1 。 2 2 5 网页结果排序 网页结果排序主要采用了p a g e r a n k 排序技术，h i l l t o p 算法，锚文本，竞价排名等 排序方法，搜索引擎的技术改进和优化，都直接反应到搜索结果的排序上。许多搜索引 擎都在进一步研究新的排序方法，搜索引擎的排序技术应该朝着解决语意相关性和排序 个性化的方向发展。前者需要完善的自然语言处理技术，后者需要记录庞大访问者信息 和复杂的计算【2 6 1 。 2 3 中文网页检索系统的设计与实现 中文网页检索系统是为了便于研究中文网页快速检索问题对实验条件的一个基本 的要求，完成生成词典，构建带索引的词典和生成网页特征向量，提供检索接口等工作， 使得以后在该方向的研究主要把精力放在理论和方法研究上，而不是把大部分时间耗费 在数据处理和编制程序上。 系统中采用的统一的编程工具v c + + 6 0 ，词典和网页特征向量的存储选用操作系统 自带的文本文件。 系统的所有模块使用统一的程序接口格式，如下： f u n c t i o n n a m e ( p a r a m e t e r l ，p a r a m e t e r 2 9o ，p a r a m e t e r n ) 模块说明：模块功能描述，参数设置，调用模块；输出结果说明； 变量说明； 调用函数说明； 模块主体； 返回值； ) 在系统的设计与实现中，每个模块都有功能说明，说明该模块在整个系统中的位置， 其上一级模块是谁( 即调用该模块的上一级模块) ，该模块中要调用哪些模块，标明模块 中所使用的变量的物理意义，类型，使用范围，输入输出，以及参数设计等。 8 第二章中文搜索引擎 2 3 1 体系结构和总体设计 中文搜索引擎作为一个网络应用软件，主要由信息采集系统( s p i d e r 或c r a w l e r ) 、信 息组织系统( i n d e x e r ) 、信息检索系统( s e a r c h e r ) 和用户接口( u i ) 四部分组成，本文因为研 究的目的是中文网页的快速检索方法，所以设计出的中文网页检索系统中不包括网页的 采集功能，根据原始网页库，特征表，倒排文件三种检索数据源。作出系统的体系结构 图如下所示： 图2 - 5 系统的体系结构图 f i g 2 - 5t h ef i g u r eo fs y s t e ms t r u c t u r e 检索系统中，检索接口用来获取用户提交的查询请求，检索器经过对查询关键词切 词处理后，在数据源中查找到匹配网页，最后将结果计算相关度后返回给查询用户。管 理员可以随时更新数据源，数据源可以是原始网页库，也可以是特征表或者倒排文件中 的一种。系统的主要数据流描述如下图2 6 ： 查询用户 查询关键字 查询结果 塞奎璧囊、业 检索系统 图2 - 6 顶层d f d f i g 2 - 6t o p - l e v e ld f d 9 管理员 江南大学硕士学位论文 特征表 图2 70 层图 f i g 2 - 70l a y e rc h a r t 图2 8l 层图 f i g 2 - 81l a y e rc h a r t 在管理员模块中，当管理员处理索引源信息时，同样要经过分词、计算相关度等操 作，并同时需要更新文件信息。 2 3 2 系统的模块设计与实现 1 ) 数据库管理模块 模块管理整个系统使用到的任何类型的所有数据，包括原始数据，中间生成数据， 和最后系统输出的数据，这些数据分别按不同的处理阶段存储。数据库管理模块的构造 如下2 9 。 l o 第二章中文搜索引擎 图2 9 数据库管理系统结构图 f i g 2 9s 仃u c t u r eo ft h ed a t a b a s em a n a g e m e n ts y s t e m 2 ) 切词系统模块 由于汉语的书写以汉字作为基本单位，词与词之间没有明显的形态界限，要进行汉 语的计算机处理，必须首先将汉语的词与词分割开，即分词。可见，自动分词是中文信 息处理的基础步骤，很大程度上影响了整个中文处理系统的性能。切分的对象有两个， 一是用户输入的关键词，切词的结果是得到关键词索引词典，然后把它作为原始词典切 分网页，原始网页库则作为另一被切分的对象，最终得到网页中关键词的总的词频，以 此来记录符合用户查询要求的网页信息。 图2 1 0 切词模块图 f i g 2 - 10t h ef i g u r eo fs e g m e n t a t i o nm o d u l e 设c = c 1 c 2 g 是一个待切分的汉语句子，n 为句长。限定单词的最大长度为t ， 切分句子c ，得到词序列矾既，其中彤= g q + 1 g + ，1 5 t s t ，1 i _ s m ，七为 首字的下标。下面分别是比较常用的前向最大和反向最大切词算法 a ) 前向最大切词算法 矾= c i c 2 c r i f 在词典中 矾= c l c 2 c r e l s e 江南大学硕士学位论文 = c i c 2 c t - i i f 啊在词典中 矾= c i c 2 c r - l e l s e w i = c 1 c 2 c r - 2 直到在词典中找到适合要求的 设g e l = c j c 2 c n ，其中l t l t ， l = t l ； i f l ) 1 r ， 切分网页 、 i r u 1 网页词频 董 匹配网页集 、 图2 1 1 检索模块图 f i g 2 - 11t h ef i g u r eo fs e a r c hm o d u l e 江南大学士学位论女 2 3 3 检索接口 检索接口是用户，检索系统的之间的连接部分，它能够将用户需求转化为系统容易 接受的格式，并将系统检索的结果转化为用户习惯的使用方式。因此必须符合使用简单， 拥有h e l p 文档帮助功能，用户界面中所用术语的标准化和一致性等要求，其可视化查 询界面如下图2 1 2 所示。 图2 - 1 2 检索入o f i g 2 1 2s e a x c h e n t r a n c e 检索结果可视化界面如下图2 - 1 3 所示： 图2 1 3 检索结果 f i 9 2 - 1 3s e a r c h r e s u l t 第三章索引数据结构的设计 第三章索引数据结构的设计 索引是将一种或多种书刊文献中有关信息名称( 如字、词、人名、书名、刊名、篇名 等) 分别摘录，分类或按主题编排起来，或成册，或附在一书之后，注明出处，用以检索 文献信息的工具，它能提供信息的线索。索引是目录的延续和深化【删。一个完整的中文 网页检索的索引器的构建涉及到索引数据结构的选取，本章首先介绍索引的三种数据结 构，最后详细的分析这三种结构的工作原理。 本章中定义引自文献【1 2 】与【3 2 】。 3 1 正排表 正排表是以网页的编号为关键字，表中记录网页中每个字的位置信息，查找时扫描 表中每个网页中字的信息直到找出所有包含查询关键字的文档。正排表结构如图3 1 所 示： 图3 - 1 正排表结构图 f i g 3 - 1l i s ts t r u c t u r ei ss c h e d u l e d 正排表的组织方法在建立索引的时候结构比较简单，方便建立，且易于维护：因为索 引是基于网页建立的，若是有网页库进行更新，直接为该网页建立一个新的索引块，连 接在原来索引文件的后面。若是有网页删除，则直接找到该网页的编号对应的索引信息， 可以将其直接删除。但是在查询的时候需对所有的网页进行扫描以确保没有遗漏，这样 就使得检索时间大大延长，检索效率低下【2 9 1 。 正排表的工作机制虽然非常的简单，但是由于其检索效率太低，几乎没有什么实用 意义【2 9 1 ，因此在搜索引擎中不会采用倒排表作为索引的数据结构。 3 2 倒排文件 定义3 1 ：倒排文件( i n v e r t e df i l e ) ，是描述一个词项集合( t e r m s ) 元素和一个文档集 合( d o c s ) 元素对应关系的数据结构【1 2 】，记： d o c s = d l ，, 2 ，d n ) ，t e r m s = t l ，t 2 ， 当我们以“文档”为出发点时，我们可以讲优中包括哪些f ，或者某一个t j 在d i 文档中出 现多少次。而“倒排文件”直接给出的是一个矗出现在哪些4 中，进而还可以有它在某一个 西中出现在哪些位置( 含多少次) 。用p l ( t j ) l 出现于其中的文档记录的集合，称为对应于f ， 江南大学硕士学位论文 的倒排表( i n v e r t e dl i s t ) ，下面是信息检索研究中常用的几个相关量。 ：文档集合的大小； m ：词项集合的大小； s f i p l ( t e ) i ： 词项，所涉及文档的个数； 凡：第，个词项在第f 个文档d i 中出现的次数。 作为数据结构，倒排文件分两部分：第一部分是由不同词项组成的索引，称为词表 ( v o c a b u l a r y ) ，第二部分由每个词项出现过的文档集合构成，称为记录文件( p o s t i n gf i l e ) 。 每个词项的对应部分称为倒排表，亦称记录表( p o s t i n gl i s t s ) ，可以通过词表访问。 实际中由于倒排文件非常大，通常情况下无法一次装载入内存，只能以文件的形式 保存在磁盘上。等到检索时需要查询某个词语的倒排表的时候，再从磁盘上将相应的部 分读入内存。由于倒排文件是一个变长记录的集合，要想实现对各个倒排表的随机访问， 必须事先知道每个倒排表的位置，才能一次定位到需要访问的倒排表上。这个定位信息 一般作为词表即索引的一部分，也就是说，对每个词语，保存了指向对应倒排表的首地 址和偏移位置。实际运用时，词表的规模比较小，能够一次装入内存，并常驻于内存， 供检索时使用。 从倒排文件的定义可以知道，倒排文件实际由多个倒排表组成，词典中的每个关键 字对应一个倒排表( i n v e r t e dl i s 0 。倒排表实际上就是一个表结构。倒排表的结构图如图 3 2 ： 图3 - 2 倒排表结构图 f i g 3 - 2i n v e r t e dl i s ts t r u c t u r e 全文检索方案是在执行检索操作时比较字或词条在同一文档内的位置是否相邻的 算法方案。在此为了说明倒排文件的工作原理，采用一个全文检索方案加以说明。 在对关键词进行检索时需要对关键词中每个字在倒排表中进行一次检索操作，假设 我们要对k e y 这个关键词进行全文检索， 定义3 - 2 ：缸旷 c l ，c 2 ，c 3 g ) n = l ，2 ，3 ， k e y 是疗个字符的集合，它们的前后位置关系是固定的，双c ) 为包含字符g 的索引 信息二元组d u a l l 的集合，二元组中第一个数字为文档标号，第二个数字为文字在文档 内的位置。 1 6 第三章索引数据结构的设计 双c f ) 可以描述为定义3 3 ： 定义3 3 ： 双c f ) = 研，f 2 i 西，p o s o ，( a r t l d 2 ，p o s 2 ) ，似厂f 厶厶，p o s 辫) ) 其中彳，为包含字符c f 的文档的序号，p o s m 为字符c f 在文档a r t l d m 中出现的位 置，则一个k e y 被检索到的条件数学描述如式l 所示： ( c i k e y 3 x i ( a r r l d x j ，p o s x a s aa n du r r l d x j ) = a a n d ( p o s x r p d 品u 1 ) = 1 )( 3 - 1 ) 从上面的条件公式可以看出检索成功的条件就是对关键字中所有的字符c f 都可以 找到同一篇文档，使该文档包含字符c j 而且这些字符在该文档中的字符位置的差值和它 们在关键词中的位置的差值相同。 例如，搜索“中国 ： 假如索引库中“中字的索引信息为二元组序列为 ( 2 ，5 ) ( 4 ，6 ) ( 5 ，9 ) ( 6 ，9 ) ( 7 ，1 0 ) “国 字的索引信息为二元组序列为： ( 1 ，5 ) ( 2 ，6 ) ( 5 ，1 0 ) ( 7 ，3 4 ) 则根据定义3 1 和3 2 ： k e y = 中，国) s ( 中) = ( 2 ，5 ) ( 4 ，6 ) ( 5 ，9 ) ( 6 ，9 ) ( 7 ，1 0 ) s o n ) = ( 1 ，5 ) ( 2 ，6 ) ( 5 ，1 0 ) ( 7 ，3 4 ) ) 根据式1 定义的匹配成功条件，检索结果x i 为2 和5 从上面检索的结果可以看出“中国两个字在2 ，5 ，7 号文档内都出现了，但是只 有2 和5 号文档内“中国两个字是相邻的，所以检索命中的文档为2 和5 号文档。 3 3 互关联后继树模型 索引的数据结构除了上述的正排表、倒排文件外还有利用互关联后继树模型来实现 全文检索的。与传统的倒排表的索引数据必须具有文档一索引项结构且只能实现简单的 查询不同【3 0 】，互关联后继树模型【3 1 3 2 】不但能够处理具有文档一索引项结构的数据，同时 也能够与p a t 树【3 3 】一样处理无结构数据【蚓：具有创建速度快，查询速度快，空间效率高 等特尉3 5 3 6 1 。 3 3 1 原始模型 设是构成文本的基本符号单元的集合是a i ，a 2 ，a n 。中的一些基本符号，它 们的有序组合便可构成一个文本。我们在每个文本t 的最后人为的添加一个不在中的 符号，用来表示该文本的结束。这个符号称为文本结束符，一般用a s c i i 为0 的字符表 示。在本文中，为了阅读方便文本结束符使用“撑 。通常把加入某一个索引库的所有文 本的集合叫做该索引库对应的全文。 定义3 4 ( 前驱和后继) ：对任意文本