（计算机应用技术专业论文）基于lucene的搜索引擎应用与研究.pdf

湖北工业大学硕士学位论文 |i rl ! ，鼍! ! 摘要 随着快速增长的网络信息资源，人们很关切如何从互连网上找出对用户有价值 的信息。搜索引擎解决了用户检索网络信息的难题，它是人们获取信息极为有效 的工具。 随着越来越深入的研究搜索引擎，搜索引擎技术正在不断的向前发展。未来的 竞争不仅限于互联网，本机、局域网、企业网内部以及无线网都将被包括在内。 而搜索引擎的设计与实现是一项庞大的工程，要运用较多专业技术知识，所以也 成为了一大难点。 本文首先对搜索引擎的相关知识和工作原理进行了介绍，在实现搜索引擎过程 中所使用的索引和搜索技术进行探讨并对搜索引擎的性能指标进行了描述。 其次研究l u c e n e ，分析l u c e n e 实现全文索引和检索的过程，并对中文分词及 其相关技术进行了叙述。针对l u c e n e 的页面优先算法不足，论文还提出了一种综 合利用p a g e r a n k 算法和d i r e c th i t 算法并考虑到分层结构的页面优先算法，以 提高系统搜索性能。 基于以上关键技术，论文采用n e t 平台的开发环境，提出了一种基于l u c e n e 的搜索引擎解决方案，并完成该模拟系统。 最后，在实现模拟系统对其所使用的技术和方法进行总结，为设计出更优化的 搜索引擎指出方向和方法，使其能更一进提高搜索引擎的工作性能。 关键词：搜索引擎，l u c e n e ，页面优先算法 湖北工业大学硕士学位论文 ! i ii i i ! a b s t r a c t a l o n g w i t ht h er a p i dg r o w t ho fi n f o r m a t i o nr e s o u r c e ，p e o p l ef i n dt h a ti th a sb e c o m e e v e rm o r ed i f f i c u l tt or e t r i e v i n gp o t e n t i a la n du s e f u li n f o r m a t i o na m o n gt h ee n o r m o u s a m o u n to fw e br e s o u r c e t or e s o l v et h ed i 仃i c u l t i e so fi n f o r m a t i o nr e t r i e v a l t h ew e b s e a r c he n g i n ee m e r g e d b e c a u s ei ti st h ee r i e c t i v et o o lt of i n dw h a tw en e e d a l o n gw i t ht h er e s e a r c ho fw e bs e a r c he n g i n e ，t h et e c h n i q u eo fw e bs e a r c he n g i n e i sa l s od e v e l o p e dw i t ht h eu n c e a s i n gs p e e d c o m p e t i t i o ni nt h ef u t u r ea r en o tl i m i t e dt o t h ei n t e r n e t b u ta l s oi nt h el o c a lc o m p u t e r 、t h el o c a la r e an e t w o r k 、t h ei n t e r i o ro ft h e e n t e r p r i s en e t w o r k a n dt h ew i r e l e s s i tn e e d sm u c hp r o f e s s i o n a la n dt e c h n i c a l k n o w l e d g et od e s i g na n di m p l e m e n tt h es e a r c he n g i n e ，s o ，i ti sb e c o m eat e c h n i c a l q u e s t i o n f i r s t l y ，t h ep a p e ri n t r o d u c e st h em a i ni n t e l l e c t u a la n dt h et h e o r yo ft h es e a r c h e n g i n ea n da n a l y s e si n d e xa n dr e s e a r c hi nd e t a i lw h i c ha r et w ok e yt e c h n o l o g i e st o a c h i e v et h ew e be n g i n ea n dd e s c r i b e st h ep e r f o r m a n c ei n d e x s e c o n d l y , t h et h e s i sf o c u s e so nt h el u c e n ea n da n a l y s e st h ep r o c e s so fr e a l i z a t i o n i nt h ei n d e xa n ds e a r c h ，t h e nd e s c r i b e st h et e c h n o l o g yo fc h i n e s ew o r ds e g m e n t a t i o n a c c o r d i n gt ot h es h o r t a g e so fl u c e n e ，t h i sp a p e rp r o p o s e san e wa l g o r i t h mw h i c hi s b a s e do nt h ep a g e r a n ka n dt h ed i r e c t h i ta l g o r i t h ma n dc o n s i d e rt h en e t w o r ko f h i e r a r c h i c a ls t r u c t u r ea st oi m p r o v i n gt h es y s t e mp e r f o r m a n c eo fs e a r c h t h i r d l y , i th a sb e e np r o v e nt h a tt h es y s t e mc o u l db er e a l i z e dw h i c hi sb a s eo nt h e a b o v ec r u c i a lt e c h n o l o g i e sa n dt h ep a p e rh a sb e e na c h i e v e dw h i c hi sb a s e do nt h e n e t d e v e l o p m e n te n v i r o n m e n t a tl a s t ，t os u mu pt h et e c h n i q u e sa n dm e t h o d si nr e a l i z i n gt h es i m u l a t i o ns y s t e m ， t od e s i g nt h eb e t t e rs e a r c he n g i n ew ep r o v i d et h ed i r e c t i o na n dt h em e t h o d ，w h i c hc a n i m p r o v et h ep e r f o r m a n c e k e y w o r d s ：w e bs e a r c he n g i n e ，l u c e n e ，p a g ep r i o r i t ya l g o r i t h m 学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行研究工作所取 得的研究成果。除文中已经标明引用的内容外，本论文不包含任何其他个人或集体已经 发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在文中以明确方 式标明。本声明的法律结果由本人承担。 学位论文作者签名：梅日期：如口7 年，月如日 | 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权保留 并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授 权湖北工业大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采 用影印、缩印或扫描等复制手段保存和汇编本学位论文。 学位论文作者签名：- 黼 嘲：下肛日 指导教师签名：皂吱仁 嗍功。r 训 湖北工业大学硕士学位论文 1 1 研究的目的和意义 第1 章引言 互连网上的信息每天都在不断增长，而i n t e r n e t 可看作成人类巨大的一个知 识库，是我们学习和工作必不可好的一个重要工具，与我们生活密不可分。据统 计，整个互联网的网页达到i 0 0 多亿，而且每年还在快速增长 i 】。互联网技术的研 究课题之一就是帮助用户找到自己想要的信息，而搜索引擎是一种技术，它的出 现使得这个问题得以解决。搜索引擎是一种搜索工具，目的在于帮助用户找到他 们想要查询的信息，搜索引擎以一定的策略在互连网上搜集、发现资源，并对资 源进行提取、处理与加工，是帮助用户找到所需信息与资源的一种有用的工具。 搜索引擎解决用户搜索信息的难题，是帮助我们快速、准确、有效地获取网络信 息资源的有利工具【2 】。 1 2 本文研究的内容 本文的主要研究内容是基于l u c e n e 的搜索引擎模拟系统实现过程中所涉及的 各种理论和技术。 首先介绍了搜索引擎的相关知识其中包括对搜索引擎技术的分类、搜索引擎发 展的趋势和所面临的问题等相关内容。接着阐述了搜索引擎的工作原理并详细分 析在实现过程中用到的相关技术。 其次叙述了搜索引擎性能指标，针对l u c e n e 的页面优先算法不足，论文还提 出了一种综合利用p a g er a n k 算法和d i r e c th i t 算法并考虑到分层结构的页面优 先算法，以提高搜索引擎系统搜索的性能。 随后研究了l u c e n e ，详细分析l u c e n e 实现全文索引和检索的过程，并对中文 分词及其相关技术进行了叙述。在这些理论基础之上证明系统的可实现性，以及 完成该模拟系统。 基于以上关键技术，论文采用n e t 平台的开发环境，提出了一种基于l u c e n e 的搜索引擎解决方案，并完成该模拟系统。 湖北工业大学硕士学位论文 1 3 本文的组织结构 本论文一共由六章组成。 第一章节为引言，介绍了论文研究的目的和意义、本文研究的内容和组织结构。 第二章首先阐述了搜索引擎概念以及搜索过程的中所涉及到的问题，其次介绍 了搜索引擎的分类、国内外研究的现状、发展趋势以及所面临的问题。 第三章介绍有关搜索引擎的技术。首先讲解了搜索引擎工作的原理、基本构成 和工作流程。其次介绍了搜索引擎中网络爬虫、索引器、搜索器等相关技术。 第四章叙述了搜索引擎的性能指标，针对l u c e n e 的页面优先算法不足，论文 还提出了一种综合利用p a g er a n k 算法和d i r e c th i t 算法并考虑到分层结构的页 面优先算法，以提高系统搜索性能。 第五章对l u c e n e 的核心技术进行分析。首先叙述了l u c e n e 的一些相关知识， 以及它的数据结构和软件工具包。接下来介绍了l u c e n e 在实现搜索引擎过程中两 个关键部分：索引和搜索。随后讨论了中文分词，包括分词的概念和研究现状、 中文分词与搜索引擎的关系、所使用的相关算法。 第六章介绍了系统的设计与实现。首先介绍了系统实现的目标，再对各功能模 块进行一一讲解，并且指出了系统的不足之处。 第七章是总结与展望。 湖北工业大学硕士学位论文 _ 一 _iii i _ ! ! ! 第2 章搜索引擎概述 2 1 搜索引擎相关概念 搜索引擎是一种搜索工具，目的在于帮助用户找到他们想要查询的信息与资 源，以一定的策略在互连网上搜集、发现资源，并对所收集到的资源进行处理与 加工，是帮助用户找到所需信息与资源的一种有用的工具【3 】。 搜索的过程就是：搜索引擎接收用户提出的要求，然后对其进行处理和加工， 从文件组中筛选和提取文件，这些文件是符合用户要求的。 这里涉及到几个基本问题： 1 搜索引擎怎样读懂用户的要求。这是用户和搜索引擎之间的接口问题。 2 当搜索引擎读懂用户的要求时，如何来进行处理。这涉及到不同文件格式 的解析和如何最快地处理这些文件，以及如何揣摩用户的真正意图，在文件数量 特别大时，如何提供最符合需要的结果。 3 如何把搜索的结果显示给用户。 解决了这三个问题后，一个搜索引擎就成型了【4 】。 2 2 搜索引擎的分类 目前，i n t e r n e t 上已有数千个能提供检索服务的站点，这些站点的搜索引擎 在收录的范围、内容、检索方法上都各有不同，采用的技术也各具特色。但总的 来看，可分成四大类：基于机器人的搜索引擎、目录的搜索引擎、元搜索引擎等【5 】【6 1 。 2 2 1 机器人的搜索引擎 机器人的搜索引擎是由s p i d e r 索引程序来完成索引网页的，可按照一定的遍 历方法搜索互连网上的信息。它的工作原理是由起始u r l 地址出发，根据某种算 法把这些新网页或是相应的文档信息加入到全文索引数据库，当用户从外界输入 关键字、词时，搜索引擎就会从索引数据库中查找与用户关键字匹配的网页信息 资源。搜索引擎索引程序根据网页的超链接地址提取与其相关的网页页面信息， 还可根据超链接地址跳转到其他页面，直到搜索结果结束。当用户输入关键字时， 可以在搜索到的数据库中查找匹配关键字，把相应的网页呈现给用户【7 】。 湖北工业大学硕士学位论文 2 2 2 目录搜索引擎 目录搜索引擎比r o b o t 搜索引擎需要更多的人工干预，其数据库由人工的研究 与改进。目录的搜索引擎原理是：搜索引擎技术人员先遍历某个门户网站，在门 户网站下有很多的网页，根据网页的内容进行归纳为不同的类别，再把网页的网 址、信息、类别等相关网页描述信息存入索引数据库中。搜索引擎索引到不同的 网页信息资源按照事先定好的目录进行排放。当用户在用户界面中进行输入关键 字、词利用搜索引擎进行查找时，只需检索网页的链接网址、信息内容、所属类 别等相关内容就可以进行查询和搜索工作。基于目录的搜索引擎结果比依靠人工 分类的搜索引擎更精确原因在于目录搜索引擎是人工分类，而搜索结果中难以及 时反映站点本身的变化【8 】。 2 2 3 元搜索引擎 元搜索引擎不是真正的搜索引擎，只能算作一种搜索引擎代理。它内部没有搜 索器，并且也没有相应的索引数据库。当用户从用户界面进行搜索查询时，它把 用户键入的关键字、词转换为搜索引擎的可以识别的命令格式，分别提交给其它 搜索引擎软件，经过组织、整理返回的搜索引擎结果，再把结果集返回给用户【9 】。 2 3 国内外发展现状 在互连网，我们可以发现在互联网上有很多搜索引擎这种便于人们搜索的工 具，国内比较常见的有：b a i d u ，s o h u ，s i n a 等，而在国外同样也存在很多搜索引 擎工具供人们提供搜索服务，例如：i n f o r s e e k ，m e t a c r a w l e r 等。在众多搜索引 擎中，精确率做得最好的还数g o o g l e ，它是互连网上用户运用最多的搜索引擎网站 下面来分析它的构架： 4 湖北工业大学硕士学位论文 图2 1g o o g l e 的搜索引擎结构 如图2 1 所示，g o o g l e 在实现它的搜索引擎中主要由这么几个部分工作： 由搜索器在各个门户网站中根据其遍历算法搜索网页，并且网页在搜索前也按照 某种算法计算其每个网页的p a g er a n k 值，根据每个网页的链接以及u r l 地址或 是利用网页中的锚来查找与它搜索相关的网页，再由爬行器把这些网页收集到本 地的存储服务库中，并把它与已有的词典进行比较、匹配，比较后，再归类到相 应的数据库中，当用户从外界键入关键字、词要查找相关信息时，它会与索引数 据库中已有的信息相对照，如果匹配成功，则提示结果并返回给用户，如果发现 数据库中没有相对应的字段信息，则提示未发现搜索结果。 而a l t a v i s t a 也是一个较著名的搜索引擎，它的库存容量非常大，并且在用户 进行查找至到搜索引擎返回给用户结果所花费的时间非常短，达到了响应速度非 常快的服务，因此国外用此搜索引擎的人也比较多。它不仅提供一些基本查询， 更重要的是它会提供一些高级查询，有近似搜索，支持与和或运算等其它一些功 能，从它的扩展功能中，可以更好的为用户提供搜索的结果，从而提高搜索引擎 的查全率。 y a h o o 是一个分类目录的搜索网站，在这个网站建立初期，它的搜索结果全都 是由g o o g l e 提供的，但是随着自身网站的发展以及用户的需求量增加，它开始开 发属于自己的搜索引擎技术。与一般搜索引擎不同的是，y a h o o 是一个分类目录搜 索引擎，它实现的是用户输入关键字、词后，不直接返回结果，而是提供一个目 录，目录有主题词，按照主题词的细分，一步步向下进行查找，直到找到相关的 信息与内容。这类搜索引擎网站比较适用于专题搜索，当用户为找某一专题信息 时，它的精确度会有很大提升。比如用户想查找关于财经类的网页信息与内容， 它输入“财经”关键字时，它会提供一个关于“财经”主分类的类目，再按照它 湖北工业大学硕士学位论文 所提供的分类目录信息，一步步朝下进行查找，直到找到相关内容与信息为止。 y a h o o 搜索引擎就是这样实现其搜索功能的。 百度是中国人较爱使用的一种中文搜索引擎。它的优势在于它所提供的中文搜 索功能。在国外的搜索引擎由于语言的差异性，可能提供的结果往往没有正确分 析用户的真正意图或是不理解中文的具体含义。而百度了解这一需求后，开发基 于习惯中国人的搜索方式，能够提供中文人名的搜索、识别，简繁体中文自动转 换，中文自动纠错等相关功能，由此深得中国人的喜爱。 国内外的搜索引擎技术已基本成型，并且使用的人也非常多，为了更快、更准 的找到所需要的信息，这种需求推动了搜索引擎的进一步发展。 2 4 搜索引擎的发展以及趋势 随着信息时代的到来，越来越多的个人和企业习惯用互连网来解决问题，这成 为了他们所依耐的一项基本工具。目前搜索引擎在诸多方面发生着深刻的变化， 对搜索引擎的评价不仅在数据库中数据量的规模、数据更新的频率、用户检索出 信息与资源时搜索引擎所提交的速度，而且在数据的归纳、数据与数据间的组织 与连接、数据间的存储等方面的突破，国内国际对搜索引擎的风险投资主要集中 在垂直搜索、非信息( f t p 、桌面等类信息的检搜索、多媒体搜索等项目) 。 搜索引擎技术的未来发展趋势正向以下几个方面进行开展： 1 挖掘与检索的结合 国际互联网上的页面数量越来越多，而且形式也在不断地增加，是人类巨大的 一个知识库。我们要把搜索引擎从这些知识库中有效地提取用户所需要的信息。 面对搜索引擎中的挖掘与检索的结合，微软亚洲研究院的互联网搜索与数据挖掘 组正在从事以下领域的研究工作：文本与数据挖掘、网页信息抽取、结构化数据记 录抽取、新的搜索排序法与深层互网搜索与数据挖掘、大规模文本分类与聚类、 互联网建模、大规模链接分析图、网络社区搜索与数据挖掘、对象级互联网搜索、 移动搜索以及多媒体搜索等。并致力于将数据挖掘、机器学习与知识发现技术和 信息分析、组织、索引与可视化过程的结合。g o o g l e 搜索技术开发主要在两个层 面着重突破：一方面从一维到三维，众所周知，目前使用的搜索都是一维的，而现 实世界是以三维形式存在的，如何通过关联词获得平面文字、时间以及空间信息 组成的三维信息将成为未来搜索技术发展的重要目标。另一方面，g o o g l e 还推出 了其著名的六度空间理论，提出了自己的展战略社区、通信、合作，根据六度空 间理论，将把现有的人信息查找模式推进到人一信息一人互动搜索架构，让信 6 湖北工业大学硕士学位论文 息数据结构更加智能化、架构化。 2 多种信息类型的搜索 虽然网络上同时并存着比如：h t m l 、e x e 、p p t 、m p 3 等相关文件。但人们可以 搜索的范围仍然很有限。人们希望未来的搜索引擎朝着多媒体的格式方面发展、 3 个性化的支持 现代生活的人们总是有着自己的新追求和目标，所感兴趣的内容与方向也不相 同，有人对体育偏好，有人喜欢财经类的网页信息，而有人则喜欢新闻类的网页 作为浏览，未来的搜索引擎应考虑到用户有不同的需求，针对不同的需求来考虑 如何设计满足不同需求的搜索引擎。 4 自然语言查询 人工智能的一个核心研究领域是对自然语言处理。而人类处理自然语言的能力 是依靠现有的软件，我们应进一步开发性能更好的软件来达到更好的自然语言处 理能力。实现一个良好的搜索引擎应能分析与理解自然语言，它是建立基于互联 网的知识库的关键技术之一【1 2 】。 2 5 搜索引擎所要解决的问题 搜索引擎是帮助人们在互联网上查找信息困难的一个有效的工具，但它的设计 目标抑制了其发展进程。应该在以下几个方面考虑未来搜索引擎所存在的问题： 1 索引覆盖率不高。互连网上的信息日益增长，而且更新速度也非常快，要使 得搜索引擎能遍历、索引到每个网页似乎不太可能。 2 索引数据库中的信息资源无法同时更新互连网上的信息。互连网上的信息数 量和结构上都千变万化，并且每天都在实时更新，搜索引擎从某个时间段搜索下 的网页，由于数目太多，如果想与互连网上的信息同步更新，就需要有专人来整 理其内容。并且对一些过时的、无用的网页链接应该进行删除。 3 无法满足个性化的需求。不同的用户所想使用的搜索引擎达到的效果不同， 有的用户喜欢搜索股票类网页，而有的用户偏向于体育类的网页。良好的搜索引 擎应该能做到各需所须。 4 没有完善的处理多媒体资源。现在搜索引擎的搜索的对象主流有文本格式， w o r d 格式，图片格式等。原因是搜索引擎排序软件只能接受以上几种格式的网页。 对m p 3 、p p t 、a v i 等格式的多媒体资源的搜索引擎较少。多媒体技术的发展，对 搜索引擎提出了更高的要求，搜索引擎应更好地支持动态网页，尽快解决动态网 页查询的问题。 湖北工业大学硕士学位论文 5 专业性搜索引擎较少、专业性搜索引擎是能够针对具体的某一行业或是具 体的主题建立相应的信息。比如：新闻、体育、股票等查询服务的搜索引擎。目 前的搜索引擎大多综合性的，收录各方面、各学科和各行业的信息，在反映专题 或专业信息方面很难做到全、快、精、准。例如：财经人员对网络的需要主要表 现为对财经等信息资源的需求，但目前的搜索引擎收录信息类型众多，能够提供 专题信息查询服务的专业性搜索引擎很少，用户不可能也没有必要去浏览所有的 网页，这就给用户获取相关文献造成了极大的信息障碍。 2 6 论文的创新 论文采用理论研究与实际相结合，研究方法较为科学。论文结构严谨，层次分 明，采用了递进式的分析结构，逻辑性强，文笔流畅，表达清晰，重点突出。针 对l u c e n e 的页面优先算法不足，本文提出了一种效率较高的页面优先算法，并且 运用到本系统中。其中的创新点有： 1 、结合了基础排序算法和p a g e r a n k 算法以及d i r e c th i t 算法，对网页页面 的客观评估更加全面、客观。 2 、对于各个因素设置权重系数，有利于灵活调整各种因素对页面优先度得分 的影响程度。经过经验数据分析和人工调整，可以将搜索系统性能调整到最佳状 态。 3 、结合了用户点击率高d i r e c t h i t 算法加分机制，利用用户对网页页面的 主观评估提高搜索系统的准确度。 湖北工业大学硕士学位论文 第3 章搜索引擎的关键技术分析 3 1 搜索引擎的工作原理 搜索引擎的基本原理是从已有的资源出发，通过这个资源的概要和链接确定新 的所需搜索的信息点，由搜索引擎的设计的相关程序遍历这些需要搜索的信息点， 对这些信息点上的文档进行索引、分类、并组织到索引数据库中去。从逻辑上讲 通过这种递归遍历的方法最终可以把所有信息加入索引数据库中。当用户使用搜 索引擎的时候，输入用户所需查找内容的关键字、词，检索程序就会在索引数据 库中读取索引数据库中己遍历的，并且保存在索引数据库中信息与用户关键字进 行匹配，检索出相应或相关的信息通过一定的组织方式把它输出给用户【13 1 。 3 1 1 搜索引擎的框架 一个满足用户所需的搜索引擎一般由s p i d e r 、索引器、检索器和用户界面四 大部分组成。下面分别介绍这四个组成部分 1 4 t 1 5 】。 1 搜索器。在互联网中发现和搜集信息是靠搜索器完成的。它根据搜索遍历的 条件在互联网上收集大量且更新过的新的网页信息，为避免死链接和无效链接， 搜索索引库中的信息需要定时进行更新和处理【1 6 】 1 7 】。 2 索引器。索引器的作用是理解搜索引擎s p i d e r 搜索回来的信息，从中抽取 出索引项，把文档以及相关的索引库中的信息建立索引表。在单索引项中，因为 英文间有明显的间隔符，所以很好进行区分，对于以词组为单位的中文，必须对 词语进行分析。 3 检索器。根据用户的查询关键字、词在索引数据库中快速检出与此相匹配的 相关文档与信息，进行文档与查询字、词的相关度进行对比，对将要显示给用户 的结果进行处理并对其进行相关用户所需相关度进行排序，并实现某种用户相关 性反馈机制，把搜索到的结果以用户界面的方式返回给用户，这就是检索器的功 能18 1 。 4 用户接口。用户接口的作用是输入用户查询、显示查询结果、提供用户相关 性反馈机制。目的是为了使用户在搜索引擎的帮助下能快速的查找到自己所需的 信息与资源【i9 1 。影响一个搜索引擎系统的性能有很多因素，还需对其进行详细分 析【2 0 1 。 9 湖北工业大学硕士学位论文 通过以上几个组成部分，可以构建一个搜索引擎系统，当用户从用户接口中输 入所需查找的信息与资源有关的关键字、词时，搜索引擎系统会按照其设计的搜 索遍历程序，从互连网上按其网页的链接地址遍历网页后，保存到索引数据库中， 再对所索引到的数据进行加工、整合。对结果进行优化，按照一定的优先算法对 结果进行排序，存储到索引数据库中。当用户从外界键入关键字、词时，搜索引 擎程序会从索引数据库中进行查找相匹配的网页或数据信息，并以一定的方式通 过用户接口显示给用户。 3 1 2 搜索引擎工作流程 首先来看搜索引擎组成结构图，如图3 1 所示： 图3 1 搜索引擎组成结构 网络搜索引擎的工作流程，可以看作四步：用s p i d e r 程序从互联网上根据相 关算法抓取网页与链接，抓取网页后对网页信息进行处理、加工后建立索引数据 库，保存在索引数据库中，用户在索引数据库中搜索与他相匹配的网页或资源， 搜索引擎对搜索结果进行加工、处理和并按照一定的算法对网页进行优先度排序 【2 l 】【2 2 】 o 1 从互联网上用s p i d e r 程序抓取网页。通过s p i d e r 沿着网络链接自动从网络 上获取大量网页。 2 建立索引数据库。把s p i d e r 收集到的网页；由分析索引系统程序进行分析 并对其进行加工、处理，提取相关网页信息建立搜索引擎索引数据库【2 3 1 。 3 对搜索结果进行网页相关排序。当用户在用户界面输入关键字、词搜索时， 由s p i d e r 程序从索引数据库中找到与用户输入关键字、词相匹配的网页信息，并 把网页存入索引数据库中。与用户的相关度越高，网页就排在越前面。方便用户 l o 湖北工业大学硕士学位论文 进行搜索查看结果。 4 对搜索结果进行处理排序。搜索引擎对s p i d e r 搜索出相应的网页后需要呈 现给用户，按照相关度的排序算法，把与用户相关度越高的网页优先排在返回结 果集中1 2 4j 2 引。 按照上面的几个程序与步骤就可以简单的构架一个搜索引擎系统供用户进行 索引和搜索用，但在实际的过程当中，搜索引擎所用到的技术：索引和搜索有其 自身的原理与使用技术，专业性较强，所以在构架过程当中会用到很多专业性较 强的技术。搜索引擎之所以有实用和借鉴的地方是因为其要求专业性太强，使很 多人对其望而却步，下面我们就来讨论下在搜索引擎过程当中用到的两大关键技 术：索引和搜索。 3 2 搜索引擎的相关技术 搜索引擎的相关技术主要包括搜索器、索引器和搜索器等技术。下面对其进行 讲解。 3 2 1 搜索器的相关技术 搜索器( c r a w l e r ) 本质上是一种计算机索引程序，利用该程序从互连网的各个 门户网站上按照遍历的条件不断抓取网页信息，再把所搜索到的网页按照文档进 行归类，当用户从用户界面搜索关键字、词进行查找相关网页时，就从索引数据 库中查找相应网页2 6 1 。 图3 2 计算机索引器结构示意图 从图中所知：计算机索引器最关键的是如何对所收集到的网页进行分析、处理。 湖北工业大学硕士学位论文 而其中最重要的是对h t m l 网页的标记分析和页面链接的提取1 2 7 。 3 2 2 索引器的思想 索引器的思想：建立索引库的目的是为了减少查询时间，提高查询效率。同时 也要兼顾到建索引更新的效率【2 8 1 。而最关键的技术实现是在中文分词。相关内容 在第四章节中有详细的介绍。 在搜索引擎索引程序设计中，每次索引到一个新的网页或是文档时，都必须把 已经建好的索引表以倒排的方式读写，再把新的网页信息或是内容增加到索引表 的末尾，这就花费大量的时间建索引。而另外一种索引方法是每次把新的网页或 是信息加入到索引表的尾部，但建索引的时候需要倒排索引表。这两种索引方法 都有利有弊，应该采取均衡的方法来采用不同的索引方法【2 9 1 。 用户键入关键字、词时，由搜索引擎程序从索引数据库中用文档与关键字、词 匹配的方法来查找用户所需的网页与信息资源，当发现索引数据库中有网页或是 文档与关键字、词匹配时，就按照一定的优先算法把结果通过用户接口显示给用 户。所以说这也是搜索引擎设计所要考虑的一个问题【3 0 1 。 湖北工业大学硕士学位论文 iii i 第4 章搜索引擎性能指标和改进的页面优先算法 4 1 评价搜索引擎性能指标 1 查全率 搜索引擎查全率是指从搜索引擎检索结果中的相关信息与搜索引擎系统中相 关信息的比值。但是在网络环境下，信息处于动态的变化过程中，搜索引擎查全 率指标比较难测算。因此，可以通过搜索引擎相对查全率作为搜索引擎查全率的 补充。搜索引擎相对可操作性较强，但受人为不确定因素的影响较大。 艨引靴栋引= 蒺簇篱鬻篇枷。 2 查准率 查准率的概念为检出的相关条目数与检出的条目数之比。查全率与查准率是一 对矛盾体，当它们的值达到一定时，查全率高了必然就相应地降低了查准率，反 之亦然。评价搜索引擎时，应该以搜索引擎所服务的主要用户的需求特点为标准。 用户往往更强调查准率的提高。值得注意的是，无论是强调查全率还是强调查准 率，搜索引擎都不能忽视网络上重要的新的相关内容 3 h 1 3 2 1 。 3 报道与内容更新速度 首先，网络上最新的信息应能及时在搜索引擎中反映出来。由于各网页的更新 不是同步进行的，使得搜索引擎自身数据库的更新情况比较复杂。陈旧的和其信 息源己无法链接的网页要及时删除，若不做及时删除，无疑会增加用户查询负担。 但对于具有较长时间的使用价值且没有相应新的内容补充进来的信息应做适当保 留【3 3 】【3 4 】 出o 4 响应时间 评价标准包括两个方面： ( 1 ) 进入搜索引擎的等待时间。 ( 2 ) 等待查询结果的时间。 虽然网络查询要比一般的手工查询特别是手工异地查询要快得多，但以目前我 国的经济条件，用户难以承受过长时间的网上等待，另外，由于网络的特征，时 间长了网络系统就会停止搜索，造成链接不上的局面。因而对一个搜索引擎来说， 无论它的其它功能多么强，若响应时间不快，用户也会弃之不用。响应时间对用 湖北工业大学硕士学位论文 户是否选择某个搜索引擎起着重要的作用。 搜索引擎的目标是帮助用户迅速查找到所需的网络资源，并及时呈现给用户 用户希望最符合需求的资源能在搜索引擎的查询队列里排在前面从用户的搜索 行为习惯来看，用户通常最关心首页的信息，第二页，第三页越往后的信息用户 越不愿意，也没有耐心去翻页浏览所以，如果有重要的网页资源被排在检索结果 的后面，则被用户点击的机率就很小了总而言之，排序是搜索引擎最关键的技术 之，排序策略和算法决定了排序效果的优劣通过搜索引擎程序帮助用户从大量 的网页信息与资源中快速查找到所需的信息资源，并呈现给用户。用户希望与此相 关的网页能优先排在返回的页面当中，从而提高它寻找页面的时间。我们在设计 搜索引擎的时候应该考虑到用户的搜索方式，总是优先查看返回的前几个网页。 所以，从索引数据库中返回给用户的网页，它的优先级排序是搜索引擎关键的技术 之，排序效果的优劣由搜索引擎设计的排序策略和算法决定【3 5 1 。 4 2p a g e r a n k 算法和dir e c t hit 算法 设计一个优化的页面优先算法可以很大程度上提高搜索引擎的查准率。也可使 搜索引擎的性能得到更一步提高。可以从两个方面考虑设计一个性能占有优势的 页面优先算法。第一：提高链接信息量大且经常被访问的网页。第二、提高经常 被用户浏览或是点击的网页，同时提高用户浏览时间较长的网页，对他们进行优 先排序，第一时间显现给用户。 4 2 1 p a g e r a n k 算法 众所周知，g o o g l e 在搜索引擎上有其独特的优势而受到用户的喜爱。g o o g l e 被 评价的优点不仅仅在于索引量很大，去除无用的( 广告) 标语构成单一页面的功能、 独自的c a c h e 系统、动态制成摘要信息、为实现高速检索而设置的分散系统( 数 千台规模的l i n u x 群集器) 等，而最大的优点是它检索结果的正确性，即将最好的 结果排在搜索结果的最前面。这对用户来说是非常有用的。一种能够自动判断网 页重要性的技术一p a g e r a n k 由此而生。p a g e r a n k 取自g o o g l e 的创始人l a r r y p a g e ， 它是g o o g l e 排名运算法则( 排名公式) 的一部分，p a g e r a n k 是g o o g l e 对网页重 要性的评估，是g o o g l e 用于评测一个网页“重要性”的一种方法。在揉合了诸如 t i t l e 标识和k e y w o r d s 标识等所有其它因素之后，g o o g l e 通过p a g e r a n k 来调整 结果，使那些更具“重要性”的网页在搜索结果中优先提供给用户，从而提高搜 索结果的相关性和质量。 1 4 湖北工业大学硕士学位论文 p a g e r a n k 算法原理是：当大量其他网页引用互连网上某个页面时，那么被引 用页面的页面等级p a g e r a n k 就越高【3 6 1 。当有大量网页特别是一些门户网站的网页 链接指向某网页页面时，说明该网页的页面质量很高，其p a g er a n k 值也该相应 提高。因为在互连网中，页面的引用是以链接的方式出现的。反之，当某网页页 面没有其他网页页面链接指向此页面，而只有它指向其他网页页面的链接，则说 明该网页页面的可被其他页面引用信息可能不多，这时应该适当降低他的 p a g e r a n k 值【3 7 】。 图4 1 网页的p r 值关系图 从图4 1 中，可看出要想网页页面的p a g e r a n k 值较高，必须满足以下条件之 ： ( 1 ) 此网页有较多从外部链入到它的网页，最好是一些大型门户网站的首页。 此网页有许多外部页面链接到它时，则说明该网页页面被引用次数多，所以p r 等 级值较高。 ( 2 ) 有一些大型门户网站的首页或是p r 值高的网页链入到此网页，即有p r 值 高的网页页面指向它。能够被高p r 等级的网页引用，说明此网页所包涵的内容丰 富，值得大型的网页引用，所以其p r 等级质量也应该相应地得到提高。如果该网 页只有链出到其它网页的链接，而没有被其他网页链入，或者仅由p r 值低的网页 链入链接到网页，其p r 值也应该降低【3 8 】。 4 2 2dit e e t hit 算法 d i r e c t h i t 算法的工作原理是：当用户使用搜索引擎查询自己所需的信息时， 搜索引擎按照页面优先度算法把搜索到的结果按一定的组织方式返回给用户。互 联网用户通过搜索引擎返回的结果，与自己预期想要的结果进行对比，取其最接 近想法的网页进行查看【3 9 1 。当然，用户习惯浏览某些网页，或对某些网页感兴趣 是带有习惯性行为，或是偶然性，但是，通过对大量日志分析，如果很多用户都 喜欢选择某些网页时，那么就可以从客观上说明这部分网页与用户相关度有直接 湖北工业大学硕士学位论文 联系，所以应该对这类网页增加其页面优先度。这时，随着用户的点击率的变化 而动态进行调整网页的页面优先度，使搜索引擎的性能能够得到进一步的优化 【4 0 】【4 l 】。 4 3 改进的页面优先算法 在网络搜索中链状解析算法扮演着重要的角色，网络链状结构揭示了网页入度 之间的关系。现存的链状解析算法通常面临两大问题：第一个是网络图的链状分 布要符合权值规律并且稀疏链状矩阵使得大多数网页不能获得正确的入度排序。 第二个问题是新出现的网页很少得到别的链接，导致它不能得到正确的入度。因 此我们提出了一个分层网络结构来解决这些问题。 而在网络分层结构中，网络包含网页，目录，主机和域。因此，整个网络图可 以大概分为几个层次结构，例如网页层，目录层，主机层和域层。通过几个不同 的层次，每层之间的超级链接可分为两种：内部链接和外部链接。同样，相同结 点中的网页间的链接为内部链接，两个不同超级结点中的网页之间的链接叫做外 部链接。而且，链接也分为两种，一种是链入一个网页，另一种是从这个网页链 出。下面就来看互联网网站链接组织结构，来帮助我们进一步分析和计算出更好 的页面优先算法，来整体提高整个系统的性能。 1 互联网网站链接组织结构 网站的组织链接结构如下图所示： 一一一1 一一一- 叶一一1 一一一卜一一一一一 i 料中搦 ： ： ：i： 轴由蚱西由双由m 由 ”，。由 f 些蔓辱 拱墟 t 一二。罐维 由由口由由 ! ：竺堡孵 由由 图4 2 网页分层结构图 图4 2 中上层图包括m 个称为超级结点的顶点，超级结点之间的边称为超级边。 1 6 湖北工业大学硕士学位论文 超级边遵循以下原则：如果在超级结点s ，和s ，中至少有- n 多个网页，那么e 就 表示s ，到s ，的有向超级边。从墨指向s ，的这条边的权值就是从s ，中的网页链接到 s i 中网页的链接条数【4 2 】【4 3 1 。 下层图：我们用p = e o ，只只) 来表示超级结点s 中的所有网页，通过u r l 的 关系将这些网页放到一个超级结点中。 2 分层自由遍历模式 在每次浏览初期，用户随机选择一个超级结点。用户在阅读完超级结点中的一 个网页时，他会选择以下三种可能的行为之一： ( 1 ) 继续阅读当前超级结点中的一个网页时，并且是顺着这个超级结点的分 层链状结构读下去。 ( 2 ) 跳到与这个超级结点链接的另一个超级结点中。 ( 3 ) 结束浏览 通过以上分层自由遍历模式，我们分两步计算分层排序：第一步通过超级结点 之间的链接关系计算超级结点的入度。第二步通过超级结点内部的链接关系计算 网页的入度“】【4 5 】。 3 计算超级结点的入度 我们把上层图看作一个矩阵。假设整个网络含有m 个超级结点，一个m * m 的邻 接矩阵被定义为a 并且彳【f ， 代表从超级结点i 到j 的链接的权值。邻接矩阵a 用 来计算每个超级结点s ，的入度，当浏览一个超级结点时，用户随机选择当前这个 超级结点的一个矩阵并且跳到这个链接所指向的超级结点的概率为1 一口，则跳到 其他超级结点的概率为口，所以超级结点的入度为： s l , = f + ( 1 一口) 串乩彳【f ，】 m i 。, 。- 。一- a 其中口( o 口 蘑字爱 笆事件 1 0 n g b o o l b o o l 摘要 添加索引文件信息记录 开始创建索引 开始创建索引 构造函数 构造函数 实始化需提取文件内客的类型 返回统计已创建文件的大小 设置一否需要报告 设置是否逞出 a d d f i l e d o c u a e n t e v r e p o r t p u b l ic刨建文件索引事件 日 7 = ：。r p j 一 2 实现w e b 的网络索引模块 w e b 的网络索引的类图： 6 2 本地索引模块的类图 2 7 c c c c：11_11_1曲曲曲曲 p p p p c c c c 1l 1 一i 1 _ i 1 上1 曲曲曲曲 p p p p 立叮 e e|l龟111毫 t v l l l l y修n曲曲曲曲“ p p p p p p 型d d d类儿叽竹 y v v c c c，11 上1 上1 上曲曲曲 p p p 湖北工业大学硕士学位论文 i_ml_mlmmm 1 名称类型修饰符摘要 i 基方法 “ ! ： 萤，略 d d h r 呐皿o c 瑚e n t v o id p u b ic添加页面内容集合 ；国；vc r e a t e w e b i n d e xp u b l ic 构造函数 l !园“- i n d e x o p t i m it