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

华中科技大学硕士学位论文 摘要 搜索引擎的实现有赖于几个关键模块的协同工作，包括爬行、本地网 页存储、索引、排序搜索结果以及加速搜索性能的链接分析应用等。对搜 索引擎的体系结构及实现原理进行了相关研究，介绍了每个组件的设计与 实现技术。 网页更新是影响搜索引擎效果的关键技术，其算法的设计很大程度上 影响了网页更新度。为了提高网页更新度，提出了一种优化算法即分类更 新的网页爬行策略，此方法以网页的改变历史为基础来评估其改变频率， 并以此作为分类网页的标准，然后基于平均值算法得出不同网页集合的更 新速度，从而实现网页更新，达到均衡分配系统资源的目的。( 经分析表明， 在现实网络中其执行效果优于目前存在的统一更新策略和个体更新策略。1 元搜索引擎提供多个搜索引擎的集成环境，具有比传统引擎覆盖面大、 可扩展性好以及结果相关性高等优点，其中排序各组成系统的返回结果是 提高其效率的核心技术。在充分理解相关度概念的基础上，提出了一种基 于权值的结果优化排序方法，综合考虑用户需求，包括兴趣权值、人数权 值和位置权值，并采用固定容量的网页索取模式，实现了个小型元搜索 引擎的原型系统，i 经实验验证，其执行性能效果较好，并对结果进行了优 l 化排序。 j 关键词：搜索引擎；更新度：元搜索引擎；结果优化排序；信息过滤；相 关性 k 华中科技大学硕士学位论文 a b s tr a c t t h er e a l i z a t i o no fs e a r c he n g i n er e l i e so nt h ec o o p e r a t i v ew o r ko f s e v e r a l m o d u l e s ，i n c l u d i n gc o v e rc r a w l i n g ，l o c a lw e bp a g es t o r a g e ，i n d e x i n g ，r a n k i n g t h e s e a r c h i n g r e s u l t sa n dt h eu s eo fl i n k a n a l y s i s f o r b o o s t i n g s e a r c h p e r f o r m a n c e t h e a r c h i t e c t u r es t r u c t u r ea n dr e a l i z a t i o np r i n c i p l eo fs e a r c h e n g i n ea r er e s e a r c h e d t h ec o m m o nd e s i g na n di m p l e m e n t a t i o nt e c h n i q u e sf o r e a c ho ft h e s ec o m p o n e n t sa r ei n t r o d u c e d p a g ef r e s h n e s si st h ek e y t oi m p a c tt h ee f f e c to fs e a r c he n g i n e ，t h ed e s i g n o ft h ea r i t h m e t i cw o u l dh i g h l yi n f l u e n c et h ep a g eu p d a t i n g t or e f o r mt h e l i m i t a t i o ne x i s t e di n p a g eu p d a t i n g ，a r e f o r m a t i v ea r i t h m e t i cf o rt h e p a g e c r a w l i n gs t r a t e g y o fs e a r c h e n g i n e i s p r o v i d e d ，c a l l e d c l a s s i f i e df r e s h n e s s s t r a t e g y t h i s m e t h o de v a l u a t e st h e c h a n g ef r e q u e n c y o ft h ew e bp a g e s t h r o u g h t h e i rc h a n g eh i s t o r ya n da s s o r t st h e s ep a g e sb a s e do nt h ee v a l u a t i o n t h e nt h ef r e s h n e s sr a p i d i t yo ft h ep a g e sw h i c hb e l o n gt ot h ed e f e r e n tg a t h e r s a r ec a l c u l a t e db a s e do nt h e a v e r a g e v a l u ea r i t h m e t i c t h i sm e t h o dc o u l d a s s u r et h a tt h es y s t e mr e s o u r c ei sd i s t r i b u t e de q u a l l y t h ee x p e r i e n c es h o w s t h a tt h ep e r f o r m a n c eo ft h i sm e t h o di sa l s ob e t t e rt h a nb o t ht h eu n i f o r m f r e s h n e s ss t r a t e g ya n dt h ei n d i v i d u a lf r e s h n e s ss t r a t e g y m e t a s e a r c he n g i n ec a np r o v i d em u l t i - s e a r c he n g i n ee n v i r o n m e n t s oi t h a sm a n ya d v a n t a g e st h a nt h et r a d i t i o n a ls e a r c h e n g i n e ，s u c ha s t h ew i d e r c o v e r a g e ，t h e b e t t e rp e r f o r m a n c et o e x p a n da n dt h e m o r er e l e v a n ts e a r c h r e s u l t s r a n k i n gt h er e s u l t sf r o mm u l t is e a r c he n g i n e si s t h em o s ti m p o r t a n t t e c h n i q u e t o i m p r o v e t h e e f f i c i e n c y o ft h em e t a s e a r c h e n g i n e a f t e r s u f f i c i e n t l yc o m p r e h e n d i n gt h em e a n i n go ft h er e l e v a n c y ，an e wi m p r o v e d r a n k i n gm e t h o di so f f e r e db a s e do nt h ev a l u e i tr o u n d l yc o n s i d e r st h en e e do f t h eu s e r ，i n c l u d i n gi n t e r e s tv a l u e ，p e o p l ev a l u ea n dl o c a t i o nv a l u e ，a n da d o p t s t h ep a t t e r no ft h ef i x e dp a g ec o n t e n t as m a l lm e t a - s e a r c h e n g i n ep r o t o t y p ei s r e a l i z e d t h ee x p e r i e n c es h o w st h a tt h ea c t u a lp e r f o r m a n c eo ft h i sm e t h o di s i i 华中科技大学硕士学位论文 g o o da n di t a l s oo p t i m i z e st h er a n k i n gr e s u l t k e y w o r d s ：s e a r c he n g i n e ；f r e s h n e s s ；m e t a - s e a r c he n g i n e ；o p t i m a lr a n ko ft h e r e s u l t s ；i n f o r m a t i o nf i l t e r i n g ；r e l e v a n c y i i i 华中科技大学硕士学位论文 = = = = = ；= = = = = = = ；= = ；= = = = = = = = = = = = = = = = = ； 1 1课题背景 1 绪论 随着i n t e r n e t 规模的迅速增长，网络上的信息资源也随之迅速膨胀， 人们迫切要求有一个w e b 信息发现服务系统，能够在较短的时间内、在指 定的范围内自动发现新的信息，并对其所覆盖的资料进行自动更新，因此 基于i n t e r n e t 上的信息发现与搜索技术变得尤为重要。其主要功能是自动 在w e b 上按某种策略进行远程数据的搜索与获取。即自动在i n t e r n e t 上搜 寻w w w 和f t p 等站点资源，返回相应数据并生成本地索引由此产生一个数 据库，而查询则是面向最终用户的，是查找者和由机器索引的资源数据库 之间的界面。由于信息的搜索不需要人的介入，速度得到了提高，其覆盖 面和及时性也得到了很大的提高。实现这一功能需要结合计算机网络与数 据库的相关知识，其中，搜索引擎成为其中越来越重要的技术手段。 w e b 搜索技术的研究涉及很多方面，比如。搜索策略页面信息及上 下文的重要性评估。现在国际上最重要的两种方式为g o o g l e 采用的 p a g e r a n k 和k l e i n b e r g 提出的h i t s 算法，另外还有图论算法，w w w 理论研 究。语言的文法分析和词汇的搜集分析，高效的索引和并行算法等。 本课题来源于与国家药品监督管理总局的合作项目：i n t e r n e t 药品信 息及电子商务监管系统。 目前i n t e r n e t 上信息泛滥，各种合法与非法的信息如广告、推荐等层 出不穷。药品是关系到人民生命健康的特殊商品，多数药品在治病救入的 同时，具有不同程度的毒副作用，因而世界各国对于药品都实行严格的监 督管理，以保障人民用药安全、有效。本系统用于i n t e r n e t 药品广告、电 子商务等信息的监管，主要有如下监管内容： 1 授权的站点及授权的广告信息管理，包括授权发布药品广告的站 华中科技大学硕士学位论文 = = = = = = = = = = = ；= = = = = = = = = = = = = = = = = = = 一 点管理，发布的广告信息内容的合法性、正确性检查； 2 i n t e r n e t 上其它有关药品的广告、介绍，以及软广告，包括图像、 声音等，信息的内容正确完整性检查、管理； 3 药品电子商务的监管，用于对i n t e r n e t 电子商务平台的信息流进 行监控，保障交易双方的公平合法，以及检查网上药品交易的情况。 其基本过程大致可以分为四大部分：首先是i n t e r n e t 上信息的搜索与 收集，主要是与药品有关的网页信息；然后是通过过滤、语义搜索和匹配， 寻找与药品广告、推荐介绍相关的信息和数据；接着将它们通过与药品信 息基础库、广告等各种限制条件进行模糊匹配或其它匹配技术，判断这些 信息是否合法；最后采用信息收集、w e bm i n i n g 等技术将结果告知用户。 系统的第一部分i n t e r n e t 上信息资源的发现与搜索是实现网 上监管的第一步，也是系统的关键所在。要实现网上信息资源的发现与搜 索，需要熟悉网络知识如h t m l 、a s p 、j a v a 、j s p 、f l a s h 、x m l 等，而关键 在于结合搜索引擎等技术。 ， 1 2 搜索引擎简介 1 2 1搜索引擎的开发背景 当今世界是信息的世界，作为人们传送信息的桥梁，i n t e r n e t 起到了 极大的作用。随着i n t e r n e t 规模的迅速增长，网络上的信息资源也随之迅 速膨胀。为了便于查找网络上的信息，先后出现了许多网络信息发现工具 【l 。j ，而目前应用最为广泛的则是环球信息网w w w 。w w w 的概念最初是在1 9 8 9 年提出的，其目的是开发一个在全球范围内易于访问的跨计算机平台的分 布式超媒体系统。图形界面w e b 浏览器的出现。把超文本、网络和多媒体 技术融为一体，并把与i n t e r n e t 相连的信息按一定规则组织起来，提供的 查询方法操作简捷、使用方便，得到普遍推广。 w w w 上的信息量在不断地增加，而且更新得非常快，可以说是“日新 2 华中科技大学硕士学位论文 ；= ；= ；= = ；= = ；# = = = 月异”，所以单纯靠用户自己手工查找或通过人力组织所有的信息已经是不 可能的。因此，人们迫切要求有一个w e b 信息发现服务系统，能够在较短 的时间内、在指定的范围内自动发现新的信息，并对其所覆盖的资料进行 自动更新。为了保证信息发现服务系统所提供的检索功能的性能，必须根 据服务检索规贝i j 和从服务器上得到的数据的类型对数据进行加工处理，并 在本地建立索引，从而优化检索工作。除了在i n t e r n e t 上的应用以外，在 i n t r a n e t 建设中也需要索引和检索服务系统对内部网络上的信息加以组 织。为了适应这种需求，人们开发出了很多索引和检索工具，这些索引和 检索工具的核心称为搜索引擎，也被称为c r a w l e r l 4 。】。 1 2 2搜索引擎的产生和功能 1 9 9 3 年以前，多数w w w 用户采用的查找方法是从一个w w w 服务 器中的某一个u r l 开始，沿其中的超级链接h y p e r l i n k 连接到其它u r l 。 但由于世界上的w w w 服务站点数量非常大，所以由手工进行查找效率太 低，并且很难找到令人满意的内容。有的服务站点为了方便用户浏览阅读， 将手工收集到的信息编成h t m l 文件，按某种次序排列组织，如按字母表 次序或地域不同分类等，从而达到使用户可以通过索引查阅的目的。这种 索引服务系统的生成方法是用手工键入新的u r l 地址，并由系统的管理员 将数据输入到数据库中去，需要大量的人力来进行搜集、排序、编成h t m l 文件并进行维护，该方法速度很慢，并且更新周期长，费时费力。 1 9 9 4 年出现了所谓的c r a w l e r 和s p i d e r ，它们的功能是自动在w e b 上 按某种策略进行远程数据的搜索与获取，并生成本地索引。由于不需要人 的介入，速度得以大大的提高，其覆盖面和及时性也得以很大的提高。采 用c r a w l e r 的w e b 索引与检索服务系统主要由两个部分组成：数据搜集和 查询。搜集引擎( 也被称为c r a w l e r 或s p i d e r ) 自动在i n t e r n e t 上搜寻w w w 和f t p 等站点资源，返回相应数据并对它建立索引，由此产生一个数据库： 而查询则是面向最终用户的，是查询用户和由机器索引的资源数据库之间 的界面。 3 华中科技大学硕士学位论文 1 2 3搜索的原理和实现 首先要了解搜索引擎的基本构成。搜索引擎主要由四部分组成：搜索 器，索引器，检索器，用户接口。搜索器的功能是在互联网中发现和搜索 信息。它要尽可能快、尽可能多地搜集各种类型的信息，同时还要定期更 新已有信息，避免死链接和无效链接。索引器的功能是理解搜索器所搜索 的信息，从中抽取出索引项，用于表示文档以及生成文档库的索引表，建 立起自己的物理索引数据库。一个搜索引擎的有效性在很大程度取决于索 引的质量。检索器的功能是根据用户的查询在索引库中快速检出文档，进 行文档与查询的相关度评价，对将要输出的结果进行排序，并实现某种用 户相关性反馈机制。用户接口的作用是输入用户查询、显示查询结果，提 供用户相关性反馈机制。 搜索的原理和实现基于各个w e b 站点之间的数据传输遵循h t t p ( h y p e r t e x tt r a n s f e rp r o t o c 0 1 ) 协议，只要按照h t t p 协议对w e b 服务器发 出申请，服务器将根据申请内容作出相应的答复。在正常情况下，如果申 请正确，将返回相应的h t m l 文件及其他相应的信息。实现搜索功能的 c r a w l e r 是一种软件，它在网上进行漫游并搜集它所能得到的信息。c r a w l e r 沿着w w w 文件间的链接在网上漫游，记录u r l 、文件的摘要、关键字或 索引等信息。其漫游结果是形成一个很大的本地数据库，可以通过w w w 浏览器访问与该c r a w l e r 相配合的检索服务器对其结果进行查询。每个 c r a w l e r 完成的功能都不一样，所以它们生成的本地索引结果也不同。 c r a w l e r 的搜索方式是从一个或一组u r l 开始，访问该u r l 并进行本 地索引，同时记录该u r l 所指h t m l 文件中所有新的u r l 锚链；然后再 以这些新的u r l 为起始点，继续进行本地索引，直到再没有满足条件的新 u r l 为止。在记录新u r l 时，可以进行分析和判断，从中去掉不需要或 不想要的u r l ，这不但提高了本地索引的速度，也减少了索引文件在本地 所占用的磁盘空间。将h t m l 文件取到本地以后，去掉其中的辅助部分， 并按一定策略将其中可用于查询的部分，例如关键字和一些特定词等，存 4 华中科技大学硕士学位论文 储到数据库中，形成本地查询数据库，以后进行查询时，就不必到远地重 新获取h t m l 文件。虽然c r a w l e r 和s p i d e r 功能很强，但如果有一组u r l 地址没有被组外u r l 所链接到，那么c r a w l e r 和s p i d e r 就不能检索到它们。 同时由于网络带宽有限，c r a w l e r 和s p i d e r 不能更新太快，因此难免有不能 及时加入的新w w w 地址，所以很多拥有c r a w l e r 和s p i d e r 的w w w 索引 和检索服务站点提供由用户加入新w w w 地址的功能。 1 2 4搜索引擎的一般体系结构 许多搜索引擎都用到了信息检索算法和技术，然而，信息检索技术是 针对相对较小且具有连贯性的集合而设计的，比如报刊文章或图书馆目录。 不适合巨大的、没有连贯性、改变迅速且地理上分散的巨型网络。因此， 需要扩展原有技术来处理网上信息的搜集，这一新技术能有效的生成可升 级的索引结构并更新数据，通过分析网页之间的链接来更好的识别出真正 相关的页面，提高搜索引擎的识别能力。 一 图1 1 一般搜索引擎的体系结构 图1 1 6 1 表示了一般搜索引擎的体系结构。每一个搜索引擎都依靠一个 c r a w l e r 模型来爬行网页。c r a w l e r 是一些很小的程序，这些程序被给定了 华中科技大学硕士学位论文 一些u r l 的开始集，并从网中检索这些网页。c r a w l e r 提取在这些检索网 页中出现的u r l ，并把这些信息送到c r a w l e r 控制模块。这个模块决定下 一次访问的链接，然后把链接返回给c r a w l e r 。c r a w l e r 同时也把检索过的 页面送到页面库中，它不停的爬行网络，直到本地资源例如内存被耗尽。 其中，爬行控制模块 7 - s 决定着爬行操作，用已经爬行过的链接图来决 定c r a w l e r 应该爬行哪些链接，而哪些链接应该被忽略，作为c r a w l e r 部分 的核心，其主要功能是控制各c r a w l e r 的执行，并控制数据流的方向。若 服务器是第一次访问，则应首先处理该服务器所对应的c r a w l e r t x t 【9 】文件， 它是服务器对c r a w l e r 的访问要求。索引模块从每一个页面中提取词语， 记录每个页面中出现的u r l ；集合分析模块负责创造不同的索引；在爬行 和检索的过程中，搜索引擎必须存贮从网上检索到的页面，其中页面 c a t h e 1 0 1 有利于快速获取网页；查询模块负责接收并解释来自用户的搜索 要求，而排序模块则分类结果以便靠近顶部的结果大部分都是用户真正想 要的信息。 1 3 相关研究领域及其发展现状 w e b 搜索技术的研究目前在国际上是一个比较前沿的方向，w w w 对于搜 索技术的探索只是近几年才开始的，现在流行的为第三代搜索引擎如 g o o g l e 【1 1 m 】、a l t a r is t a 1 3 】；而国内对于这方面的研究起步很晚，现有国 内商业i s p 所用的搜索技术大都是借用国外搜索引擎g o o g l e 或者百度搜索 引擎等。大多搜索引擎所研究的一般为文档上的搜索，对于图像、声音等 多媒体信息的搜索、提取则很少考虑。 传统的搜索引擎，例如a l t a v is t a ，y a h o o 等，试图解决i n t e r n e t 上的 资源发现问题。但是，从资源覆盖度、检索精度、检索结果可视化、可维 护性等诸多方面来看，其效果远不能够令人满意。搜索引擎采用的是典型 的集中方式，它们试图遍历整个w e b ，对其上所有的文档生成索引，供用 户检索。这种集中方式给w e b 文档检索带来了一些严重的弊端i t 4 1 ，主要表 6 华中科技大学硕士学位论文 现在： 1 盖度有限，据估计，任何一个搜索引擎索引的w e b 页面都不到页面 总数的三分之一； 2 维护困难，搜索引擎索引数据库的更新频率有限，往往会产生索引 失效； 3 消耗太大，包括网络带宽、搜索引擎自身昂贵的硬件设施等。 而随后提出的元搜索引擎m e t a s e a r c he n g i n e ，通过综合多个搜索引 擎的结果，在一定程度上扩大了覆盖度。但是，元搜索引擎对搜索引擎的 依赖，也无法从根本上解决上述问题。随着信息资源的种类和数量的急剧 增长，一方面，需要管理的信息资源极其巨大，任何一个集中式资源发现 系统都无法完全满足需求；另一方面，各个集中式资源发现系统各行其是， 重复建设。因此，i n t e r n e t 上信息资源的发现与搜索其必然趋势应该是采 取分布协作的策略。 网上信息资源获取的分布协作策略，是指按照某种原则对i n t e r n e t 上的信息资源空间进行划分，得到若干个信息资源子空间。对于每个子空 间，分别建立一个资源发现系统以提供相应的资源发现服务。目前，分布 计算以及多a g e n t 系统等领域的研究已经取得了丰硕的成果，可以用于集 成这些自治、异构的资源发现系统，从而构成i n t e r n e t 上的协作检索群体。 采用分布协作的资源发现策略，各个资源发现系统所要管理的信息资源相 对缩小，可以降低消耗，便于维护；同时，各系统之间通过相互协作，扩 大了覆盖度，这种策略可以有效地克服集中方式的不足，提高资源发现服 务的质量。 1 4 本文主要内容 本文首先介绍搜索引擎的整个体系结构，第二章具体从各个模块来阐 明其功能的实现，第三章和第四章是文章的主体部分。其中，第三章比较 了搜索引擎中目前存在的两种页面更新策略，针对网页爬行提出了一种优 7 华中科技大学硕士学位论文 = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = ；= = = = = 一 化算法即网页分类更新策略，分析结果表明该方法优于目前存在的统一更 新策略和个体更新策略，很大程度上提高了页面的更新度：第四章在说明 元搜索引擎工作原理的基础上，针对其核心技术结果融合算法，提出一种 基于权值的结果优化排序方法，实现了一个小型元搜索引擎的原型系统， 并对此系统进行了性能测试，得出结论；第五章指出仍待解决的问题并探 讨了未来搜索引擎的核心技术。 华中科技大学硕士学位论文 2 搜索引擎的相关研究 首先阐述当前网络搜索引擎的总体发展。然后介绍一般搜索引擎的组 成结构，依次分析每一个引擎组件，包括爬行、本地网页存储、索引、排 序搜索结果以及加速搜索性能的链接分析应用等。并针对每一个组件，介 绍了最普遍的设计与实现技术。 2 1 搜索引擎的发展 根据搜索引擎不同时期的研究重点和服务性能，可以将搜索引擎分为 三代。第一代搜索引擎出现于1 9 9 4 年，这类搜索引擎一般都索引少于1 0 0 万个网页，极少重新搜集网页并去刷新索引。而且其检索速度非常慢，一 般都要等待1 0 秒甚至更长的时间。在实现技术上也基本沿用较为成熟的 i r ( i n f o r m a t i o nr e t r i e v a l ) 、网络、数据库等一些已有技术。在1 9 9 6 年出现 的第二代搜索引擎系统大多采用分布式方案即多个微型计算机协同工作来 提高数据规模、响应速度和用户数量，它们一般都保持一个大约5 0 0 0 万网 页的索引数据库，每天能够响应1 0 0 0 万次用户检索请求。自1 9 9 8 年到现 在，出现了一个搜索引擎空前繁荣的时期，一般称这一时期的搜索引擎为 第三代搜索引擎，第三代搜索引擎的发展有如下几个特点： 1 索引数据库的规模继续增大，一般的商业搜索引擎都保持在几千万 甚至上亿个网页； 2 除了一般意义上的搜索以外，开始出现主题搜索和地域搜索，很多 小型的垂直门户站点开始使用该技术： 3 由于搜索返回数据量过大，检索结果相关度评价成为研究的焦点。 相关的研究可以分为两类：一类是对超文本链的分析，在这方面s t a n f o r d 大学的g o o g l e 系统和i b m 的c l e v e r 系统作出了很大的贡献，另一类是用 华中科技大学硕士学位论文 一：= = = = ；= j = = = = ；= = = = ；= = = = = = = = ；= = = = 一 户信息的反馈，d i r e c t h i t 系统采用的就是这种方法； 4 开始使用自动分类技术。这一阶段的发展为搜索引擎拓展了生存空 间，同时提高了搜索的质量和效率，为以后的发展奠定了坚实的基础。 下面介绍的是第三代搜索引擎的组成结构与具体实现。 2 2 搜索引擎的组成结构 当前主流的搜索引擎都由如下几部分构成【1 5 】，如图2 1 所示 士 搜集器搜索引擎 图2 1 搜索引擎的组成结构 搜集器搜集器主要完成从w w w 上获取网页和超链结构信息的工 作。w w w 结构是一个以网页为结点，超链为边的有向图，搜集器的工作 可以抽象为一个有向图的遍历过程。它从用户配置的一些“种子”网页出 华中科技大学硕士学位论文 发，根据一定的算法，获取新的网页和超链，从而实现不停的从网上获取 网页的功能。 搜集端数据库搜集端数据库主要用于保存搜集器已经搜集获得的网 页和超链结构信息，等待分析器对这些数据进行分析。 分析器根据网上数据的特点，按照特定的算法，对已经搜集获得的 网页和超链信息进行分析，从中提取和用户检索相关的网页描述信息，例 如：网页关键词、编码类型、大小、被其他网页链接次数等，并将提取所 得的信息交给索引器建立索引。 索引器索引器主要用于对已分析好的网页的抽象数据建立索引。分 析器分析所得的网页描述信息，都是页面到页面描述数据的正排表。索引 器的核心工作就是重新整理这些网页描述信息，对必要的数据项建立倒排 表，包括关键词到网页的倒排表、站点到网页的倒排表等，为用户的检索 作准备。 检索端数据库用于保存一切和用户检嗉相关的数据信息，包括各种 索引，网页描述信息，影响检索结果的用户信息。 检索器检索器用于响应用户的检索请求并跟踪用户的检索行为。当 用户提交一个请求后，检索器从检索数据库中得到相关的网页，根据一定 的相关度算法将这些数据进行排序，然后输出给用户。用户得到结果网页 后，会对这些结果进行一定响应，这些信息都由检索器予以跟踪和记录。 用户信息库记录用户的相关信息，如用户的i p 地址，用户的所有检 索串以及用户对这些检索的响应。如果用户向搜索引擎登记了一些他的相 应信息，如他所在的国家地区，他的爱好等，这些信息也将被记录在用户 信息库中，以备以后提高用户检索的质量。 挖掘器挖掘器提取用户相关信息，利用这些信息来提高检索服务的 质量。它主要有两方面的功能：( 1 ) 提高所有检索的质量：这主要是靠一种 统计的效应，根据大量用户行为的分布特性来提高检索的质量；( 2 ) 提高每 一个用户检索的质量：根据用户的登记信息( 如爱好、职业等) 以及对该用 户以前检索行为的学习统计，来返回给他最期望的检索结果。 华中科技大学硕士学位论文 ：= ：= = = = = = ；= = = = = = = = ；= = = = = ；= = = = = = = = = ；= = = 一 2 3 爬行网页 考虑到网络的巨大容量和变化速率，爬行网页时产生了许多问题，包 括：c r a w l e r 检索网页的选择，在爬行网页时，需要正确优化序列中的u r l ， 首先访问重要的页面；c r a w l e r 更新网页的策略，因为网页是以不同速度在 改变，c r a w l e r 需要更新和过滤重要性尺度不同的网页，这些会影响所检索 的网页集合的更新度；最小化被访问网站的负载，c r a w l e r 应该最小化它对 网络资源的影响，否者，管理员或者网络负责人可能会完全封锁c r a w l e r 的进入；爬行过程的并行问题，并行的c r a w l e r 之间必须被适度的协调1 1 6 1 ， 以便不同的c r a w l e r 不会多次访问同一张网页。 2 3 1页面的选择 要选择合适的页面，需要解决以下两个问题，网页重要性的定义以及 c r a w l e r 获取网页的模式。 - 给定一个网页p ，有很多的方式定义它的重要性，比如兴趣驱动1 1 7 1 ， 其目标是获取一个特定用户或者是一群用户所感兴趣的网页，因此重要的 页面就是那些和用户兴趣匹配的页面：又如人数驱动，页面的重要性取决 于页面有多少人浏览，这可以从网页的被链接数中获取；再如最简单的位 置驱动，网页p 的重要性在于它所处的位置，而与网页内容无关。定义网 页重要性时，可以根据具体情况和要求来确定重要性尺度，也可以把这几 种方法组合起来，一个合适的排序尺度可以很大程度的改善爬行性能。 c r a w l e r 评测出网页的重要性尺度，基于这些信息，c r a w l e r 可以按照 下面的两种模式去获取网页： 一般的爬行& 停止模式：在此模型下，c r a w l e r 在网页p o 开始，访问完 k 个页面后结束。一个理想的c r a w l e r 应该访问页面r i ，r k ，这里 r l 是具有最高重要性权值的页面，r 2 具有次高值，以此类推。把r l 到r k 称为最具价值的网页，被c r a w l e r 真正访问过的k 张网页只包括m ( k ) 张网页，且这m 张网页的重要性都高于或等于r k 的重要性。 12 华中科技大学硕士学位论文 在阈值作用下的爬行& 停止模式：假定c r a w l e r 访问k 张网页，并给定 一个重要性目标g ，任何重要性高于g 的被认为是具有价值的网页，c r a w l e r 只访问这些具有价值的网页。 2 3 2 页面更新 一旦c r a w l e r 选择了重要的网页，它就要定期的更新这些页面。不同 的更新策略将得到不同的更新结果。这是搜索引擎提高其效率的关键所在， 下一章将对此问题作出进一步的研究。 2 3 3 爬行策略 c r a w l e r 的爬行策略是指当c r a w l e r 搜索到一个网页之后，下一步应该 转移到哪一个网页的方法。从c r a w l e r 的发展历程来看，它主要有以下几 种搜索策略，但各有优缺点。 ip 地址爬行策略它是最简单的搜索策略，实现的方法是：先赋予 c r a w l e r 一个起始的i p 地址，然后根据i p 地址递增的方式搜索本i p 地址 段后的每一个w w w 地址中的文档，它完全不考虑各文档中指向其它w e b 站点的超级链接地址。优点是搜索全面，能够发现那些没被其它文档引用 的新文档的信息源；缺点是不适合大规模搜索。 深度优先爬行策略它是从起始结点出发，一直搜索到那些不包含任何 超级链接的文件为止，这算一个完整的链，然后再返回某一文档，继续选 择该文档中的其它超级链接，它结束的标志是不再有其它超级链接可以搜 索。优点是能遍历一个w e b 站点或深层嵌套的文档集合：缺点是如果w e b 结构太深，有可能造成一旦进去再也出不来的情况发生。 广度优先爬行策略在广度优先搜索中，先搜索完一个w e b 页面中所 有的超级链接，然后苒继续下一层的搜索，直到最底层为止。 具体实现方法是：取得u r l s 列表中的第一个地址，索取相应的w e b 文档进行信息预处理，并在该文档中找出指向其它w e b 文档的超级链接， c r a w l e r 将找到的超级链接与c r a w l e r 中的屏蔽地址列表中的u r l s 作比较， 华中科技大学硕士学位论文 = = = = = = = = = = = = = j = = = = ；= = = ；= = = = = = = = = = = = = 一 如果不是搜索范围内的网址，则丢弃该地址，若是搜索范围内的网址，再 看该地址是否已被搜索过，若已被搜索过，对其引用计数值加1 ，形成下 一次搜索时的待搜索地址的优先权加权值，若未被搜索过，则将该地址加 入到近期已搜索的w e b 站点地址列表或待搜索的地址列表中。它的优点是 能找到两个w e b 文档之间的最短路径，且不会导致陷进w w w 中的深层文 档中出现出不来的情况发生；缺点是对于深层w e b 文档要花很长的时间才 能到达。 深度一广度结合爬行策略它利用两者各自的优点来弥补对方的缺点， 是搜索引擎的发展方向。利用这种策略构建的搜索引擎，可以沿着广泛分 布于网络上的超级链接漫游，每当它到达一个新的网站，能对该网站的后 续超级链接( 即引用该网站的超级链接) 进行统计，并对该网站进行检索， 且将检索结果返回给用户，接着为所获得的u r l s 运行搜索引擎程序，重 复上述的步骤。 这种检索策略有二个问题需要解决。一是当搜索引擎搜索到同一w e b 站点或同一w e b 文档时，不仅会极大地浪费计算机资源，同时也会影响用 户的最终检索结果，解决的办法是要求搜索引擎对每一个检索过的w e b 站 点或文档作上标记，这样当搜索引擎到达该w e b 站点或文档时，停止对该 站点或文档信息的提取；二是标记的设置，如果没有标记，搜索引擎将会 在网络上不停地执行并漫游下去，因此标记的设置对于这种搜索引擎的搜 索策略十分重要。标记可以这样设置：当搜索引擎搜索过一个w e b 站点或 文档时，就在搜索引擎的服务器上返回一个值代表该w e b 站点或文档已访 问过，当再次搜索到时就可以略过，这种搜索策略的优点是检索结果总是 最新的，同时具有很高的查全率；缺点是当同一时间检索的用户过多时， 可能会造成服务器负担过重或信息的阻塞。 目前，c r a w l e r 检索网页集合仍然存在许多未解决的问题。例如， c r a w l e r 和w e b 站点怎样在爬行策略上协调一致，这一点目前还没有很好 的解决方案，因为当c r a w l e r 在网站检索网页时，它不能干涉w e b 站点的 主要操作。另外，对并行的c r a w l e r 群如何终止其操作的研究也处于非常 l4 华中科技大学硕士学位论文 初步的阶段，仍有许多的问题值得详细探讨。最后，网上有些信息隐藏在 搜索界面之后，这些界面要求提交一个查询或者是填完一个表格，而现在 的c r a w l e r 还不具备产生查询和提交表格的功能，因此c r a w l e r 还不能访问 动态的内容。随着越来越多的站点信息来源于数据库，这个问题将会变得 更加严重。 2 。4 存储 在图2 1 中，网页存贮库对于管理网页者来说应该是一个可升级的系 统。如图所示，存储需要完成两个基本功能。首先，它必须为c r a w l e r 存 储网页提供接口；另外，它必须提供一个有效的a p i 入口，以便索引器和 集合分析模块可以利用它来检索网页。 2 4 1 存储网页存在的问题 网页存储库要管理大量的数据对象，也就是“网页”。网页存储库和文 件系统以及数据库非常相似，但是它不需要提供数据库系统所需的很多功 能，比如事务，日志，目录结构，其目标主要是解决下面几个关键问题： 可升级性：为了跟上网页不断增长的容量，存储库要求无间隙的分布 在计算机与硬盘的集群中。 双重入口模式：网页存储库要高效地提供两种不同的入口模式。给出 一个网页标示符，需要一个随机入口来快速检索这个特定的网页：对网页 流，需要一个数据流入口来接收整个集合，或者是一些重要子集。随机入 口被查询引擎用来检索网页给最终用户，而数据流入口被索引器和分析模 块用以大批量分析和处理网页。 大批量的数据更新：网页改变很快，如果c r a w l e r 检索到新的网页， 那么通过空间压缩和空间重组，被旧网页所占据的空间要被重新回收。另 外，要避免更新过程和应用过程之间读写网页的矛盾。 陈旧的网页：一般的文件和数据系统中，如果对象不再有用时就会被 华中科技大学硕士学位论文 删除。然而，当网页被站点所删除时，并没有通知c r a w l e r ，因此，存储库 必须有一个机制来检测并删除过期的网页。 2 4 2 设计一个分布式的网页库 网页库1 8 1 被设计成为一个内部相连的存储节点集合。有三个关键问题 会影响到存储库的特征和性能。分别是，网页在节点上的分布方法，节点 上网页的物理组织方式以及网页库中网页的更新策略。 可以用不同的方法来存储网页。例如统一分配方法，就是把所有的网 页统一对待，独立于标示符。相反，哈希分配方法是通过网页的标示符把 网页分配给节点。在此情况下，网页的标示符通过哈希函数产生一个节点 标示符，然后根据这个节点标示符网页被分配到相应的节点。 网页的物理组织方式需要考虑到节点的具体操作，在一个单独的节点 内，有三种操作可能会被执行，分别是网页的增加插入，高速信息流和随 机的网页访问，物理页面的组织对这些操作起到了关键作用。 对网页库的更新决定于c r a w l e r 的特征。更新网页库时，可采用成批 模式或稳定模式的c r a w l e r 。 成批模式的c r a w l e r 会周期性的爬行i n t e r n e t ，可以是一个月一次，也 可以在特定的时间内爬行。因此网页库只有在一个月的某段时间内是更新 的；相反，稳定的c r a w l e r 不会停止爬行，它不断地为网页库搜索更新过 的网页。 成批模式的c r a w l e r 在检索网页时，可以被设置成为每次完成一个完 整的爬行，即搜索整个i n t e r n e t ，也可被设计成为只在某些特定的网站和网 页上爬行。前者爬行所得到的网页完全代替已存在的库中的网页集合。后 者只须爬行并更新部分存在的集合。 基于上述分类，网页库可选择i n p l a c e 或者s h a d o w i n g 两种网页更新 方式。在i n - p l a c e 方式中，c r a w l e r 将所检索到的网页直接插入到库中已存 在的集合，替代老的网页集合。在s h a d o w i n g 中，c r a w l e r 将检索到的网页 存储到库中，独立于已存在的集合，并不立刻更新网页。 华中科技大学硕士学位论文 s h a d o w i n g 的特征在于它完全分开了网页更新与读访问操作。单个的 存储节点不会同时处理页面更新和页面检索，从而避免读写冲突的矛盾， 提高了网页库的性能。但它是以损害网页的更新度为代价的，因为在检索 网页的过程中，页面被c r a w l e r 更新的时间和页面可被访问的时间之间存 在延迟。 一般来说，成批模式的c r a w l e r 和s h a d o w i n g 更新方式匹配比较好， 而稳定模式的c r a w l e r 适合与i n p l a c e 更新方式匹配。图2 2 给出了网页库 的结构，图中采取的是s h a d o w i n g 方式，读操作和更新操作分开进行。 图2 2 网页库结构 页面库是整个搜索引擎结构中很重要的一部分。为了能够有效的支持 不同查询搜索访问模式和索引器模块，网页库必须用到和c r a w l e r 特征相 符合的更新策略。 文中主要针对的是网页库中存储的文本文件和h t m l 页面，事实上，存 储、索引d9 2 0 j 以及搜索图像、声音以及视频文件以后将会变得越来越重要。 2 5 索引 索引器和集合分析模块从搜集到的网页中构造出不同的索引。索引模 块构建两种基本的索引：文本( 或内容) 索引1 2 1 - 2 2 1 和结构( 或链接) 索引， 基于这两种索引以及库中的网页，集合分析模块可以再构造出其他有用的 17 华中科技大学硕士学位论文 索引。下面，对索引给出简短的描述，主要是针对其结构和应用。