《主题搜索引擎的设计与实现.doc》由会员分享，可在线阅读，更多相关《主题搜索引擎的设计与实现.doc（46页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第四代搜索引擎主题搜索引擎的设计与实现Design and Implementation of Focused Search Engine,4th Generation Search Engine北京大学计算机科学技术系计算机软件专业九七级学士毕业论文指导教师：李晓明 王建勇作者：罗昶学号：2001年6月指导老师对论文工作的评语 “面向主题的搜索引擎”，是我们“天网”搜索引擎下一步发展的重要方向之一。罗昶同学的毕业论文，是这一新方向的良好开端。论文从系统实现的角度，较全面的阐述了实现一个高质量主题搜索引擎系统的各个方面，着重分析了导向词、特征提取、权威和中心网页、超链分析以及网页评分等多种搜集
2、策略的运用，并提出了“主题度”的概念，用以衡量主题搜索引擎的质量，意在指明一个搜索引擎在一个主题下的主题度越高，则它越贴近这个主题，用户就越容易找到跟这个主题相关的资料。特别地，将上述认识用于实践中，高质量地完成了一个面向影视主题的搜索引擎系统，搜集了十多万影视信息，在影视信息方面提供着比“天网”通用搜索引擎更有效的服务；论文内容丰富，所涉及的工作量很大，且有较强的系统性，是一篇很有参考价值的论文，为“天网”的发展做出了贡献。 老师签名:_论文摘要互联网上的信息每天都以指数量级的速度爆炸性增长，面对如此浩瀚的资源，搜索引擎为所有网上冲浪的用户提供了一个入口，毫不夸张的说，所有的用户都可以从搜索
3、引擎出发到达自己想去的网上任何一个地方。因此它也成为除了电子邮件以外最多人使用的网上服务。但是，随着信息多元化的增长，千篇一律的给所有用户提供同一个入口显然已经不能满足特定用户更深入的查询需求。同时，这样的通用搜索引擎在目前的硬件条件下，要及时更新以得到互联网上较全面的信息是不太可能的。针对这种情况，我们需要一个分类细致精确、对硬件要求低，数据全面深入、更新及时的面向主题的搜索引擎。由于主题搜索运用了人工分类以及特征提取等智能化策略，因此它比前三代的搜索引擎将更加有效和准确，我们将这类完善的主题搜索引擎称为第四代搜索引擎。本文阐述了第四代搜索引擎天网主题搜索引擎的设计与实现，并着重分析了导向词
4、、特征提取、权威和中心网页、超链分析以及网页评分等多种搜集策略的运用。论文最后定义了独创的“主题度”来衡量主题搜索引擎的性能，一个搜索引擎在一个主题下的主题度越高，证明这个搜索引擎越贴近这个主题，用户就越容易找到跟这个主题相关的资料。 有了“主题度”，就可以很容易的比较使用多种搜集策略以后的天网主题搜索引擎与原天网通用搜索引擎的差别，说明了前者在特定的主题下要比后者更准确贴切。关键词：互联网、万维网、搜索引擎、数据发掘、主题搜索、主题度AbstractInformation on the Internet grows explosively every day. Search engine p
5、rovides all the surfers on it with an entrance, from which they can reach every corner of the web. Therefore, search engine becomes the most popular network service second to email.With information continuing to explode in all directions, however, some specified kinds of users are not satisfied with
6、 only one entrance. In the meanwhile, due to current hardware conditions, it is not likely to crawl full data on the Internet. What we need is a focused search engine, well classified, requesting low hardware condition, containing profound and entire data, and updating in time. Since it uses intelli
7、gent strategies such as human-classification and sample-extraction, it is called the 4th generation search engine, more efficient and accurate than the preceding ones.In this paper, described are the design and implementation of 4th generation search engine, Webgather Focused Search Engine. Mainly e
8、mphasized are its crawling strategies of orientation words, sample-extraction, authority and hub pages, anchor-text analysis and page rank. In the end, Topic Approximation is defined for performance evaluation. The higher the Topic Approximation is, the more accurate the search engine is and the mor
9、e easily users could find out what they really need. With Topic Approximation, its easy to conclude that Webgather Focused Search Engine using intelligent strategies is more accurate than the original Webgather Search Engine without them.Keyword: Internet, WWW, Search Engine, Data Mining, Focused Cr
10、awling, Topic Approximation目录指导老师对论文工作的评语1论文摘要2ABSTRACT3目录4第一章背景介绍71.1 Internet与WWW发展现状71.1.1 Internet的发展历程71.1.2 World wide web(www)71.1.3 Internet的信息分布81.2搜索引擎简介91.3主题搜索引擎第四代搜索引擎101.4 小结10第二章天网搜索引擎系统结构122.1系统简介122.2系统结构及各部分功能122.2.1 WWW信息存取和分析子系统（主控程序）132.2.2 WWW信息收集控制子系统（搜索器）132.2.3 资源索引数据库132.2.
11、4 信息检索子系统142.2.5 管理和监控子系统142.3主控程序及搜索器的实现142.3.1 主控程序142.3.2 搜索器162.4小结17第三章主题搜索策略183.1 导向词183.1.1 导向词及权值的配置183.1.2 根据导向词及权值改变搜索顺序193.2 网页评分(PageRank)193.2.1 引用计数(Hit Number)193.2.2 网页评分(Pagerank)203.3 权威网页(Authority)和中心网页(Hub)213.3.1 什么是权威网页和中心网页213.3.2 发掘权威网页的难度233.3.3 权威网页和中心网页的计算公式233.3.4 计算权威网页
12、和中心网页的算法243.4 超链描述文本分析(Hyperlink Anchor Text Analysis)253.5 小结25第四章天网主题搜索引擎的实现264.1 系统模块图264.2 存储结构274.2.1 系统数据库274.2.2 搜索器和主控程序之间的通讯扩展SOIF结构304.2.3 导向词的存贮334.3 搜索器的实现344.3.1 导向词的加载分析344.3.2 搜集策略的实现354.4 小结38第五章系统现状和性能395.1 天网主题搜索引擎系统现状395.2 主题度的定义395.3 天网主题搜索引擎与通用搜索引擎的比较40第六章总结展望42致谢43参考文献44参考URL45
13、第一章 背景介绍1.1 Internet与WWW发展现状1.1.1 INTERNET的发展历程Internet的前身是美国国防部高级研究计划署的研究试验性网络ARPANET。 1983年TCP/IP 成为ARPANET上唯一的正式协议。 此后，ARPANET上连接的网络、机器和用户快速增长。 1988年NSFNET和ARPANET互联，它的规模以指数增长，很多地区网络开始加入，并且开始与加拿大、欧洲和太平洋地区的网络连接。 后来形成Internet。 90年代初到现在，是Internet增长最迅速的时期。1993年，Internet的增长速度是341%。截止到1996年7月，Internet已
14、连接了个网络，入网主机1228万台，以及数以亿计的用户。到1998年7月，Internet已拥有427万个网址，4300万个域名，3673.9万台主机和3.2亿个网页，其规模大概每年翻一番。1.1.2 WORLD WIDE WEB(WWW)World Wide Web(WWW)是全球性的网络信息系统。一九八九年，位于瑞士的European Laboratory for Particle Physics(CERN)首先开始了WWW的研究工作。随后，许多其他的研究机构、大学和公司也加入WWW研究者的行列，并相继开发出各自的WWW软件。这些WWW软件的运行平台覆盖了目前主流的计算机硬件和操作系统。在
15、此过程中，WWW也不断完善和发展。同时，为了保证不同WWW软件之间的互操作性，一系列WWW协议和标准也正在使用和完善之中。在最近几年里，WWW得到了长足的发展，不仅成为企业必不可少的组成部分，并且开始走进千家万户。根据NEC研究院在自然上发布的数据，截止到1999年2月，Internet上共有网站1600万个，其中公开提供WWW服务的网站280万个；共有WWW网页大约8亿页，这些网页包含了15T字节的数据。按照2000年4月在波士顿举行的第5届搜索引擎年会的会议报告，我们可以知道现今的网页数目已经超过了10亿。WWW在中国的发展速度也十分惊人。根据CNNIC(中国互联网络信息中心)2001年1
16、月17日在京发布的最新的中国互联网络发展状况统计报告，截止到2000年12月31日止，我国上网计算机数有约892万台。我国上网用户人数约2250万人，除计算机外同时使用其它设备（移动终端、信息家电等）上网的用户人数为92万。CN下注册的域名总数为个，WWW站点数（包括.CN、.COM、.NET、.ORG下的网站）约个，我国国际线路的总容量为2799M。关于网页的数目没有具体的统计数据，但根据科学杂志上提供的集合估计法，通过中国几个主要搜索引擎获得的搜索数据（天网、Chinaren、新浪、搜狐、网易），我们可以估计到当前中国拥有的网页数已经超过3000万。1.1.3 INTERNET的信息分布I
17、nternet上的信息资源随着Internet的发展而呈现出以下特点：l 信息量大而且分散l 自治性强l 信息资源多种多样l 不一致和不完整性这些特点对网络软件的性能提出了很高的要求。网络的快速发展给信息挖掘带来了挑战。WWW上信息呈现爆炸性的指数增长，同时伴随着上网经验不足、不太晓得如何查找信息的新用户的加入。用户很可能最大程度的运用超链来在网上冲浪，他们通常从以下两类网站开始：第一类是目录系统，其典型代表是Yahoo!（），它通过有专业知识的网页编辑人员对网上的网页进行精选，建立一个索引目录，来给用户提供服务。这类通过手工维护得很好的系统的优点是提供的网页准确率高，可以有效的覆盖所有热门的
18、主题，但它们的缺点是过于主观，而且需要高昂的代价来建立和维护，更新改进的慢，同时不能很好的覆盖所有深奥的主题。第二类是搜索引擎系统，比如天网（），它通过程序自动地从网上搜集和分析网页，建立索引，为用户服务。这类通过关键词匹配实现查找的自动更新的搜索引擎优点是涵盖的网页数量巨大，但通常返回太多的低质量相关性不大的结果。1.2搜索引擎简介面对浩瀚的网络资源，搜索引擎为所有网上冲浪的用户提供了一个入口，毫不夸张的说，所有的用户都可以从搜索出发到达自己想去的网上任何一个地方。因此它也成为除了电子邮件以外最多人使用的网上服务。搜索引擎技术伴随着WWW的发展是引人注目的。搜索引擎大约经历了三代的更新发展：
19、第一代搜索引擎出现于1994年。这类搜索引擎一般都索引少于1，000，000个网页，极少重新搜集网页并去刷新索引。而且其检索速度非常慢，一般都要等待10秒甚至更长的时间。在实现技术上也基本沿用较为成熟的IR（Information Retrieval）、网络、数据库等技术，相当于利用一些已有技术实现的一个WWW上的应用。在1994年3月到4月，网络爬虫World Web Worm (WWWW)平均每天承受大约1500次查询。大约在1996年出现的第二代搜索引擎系统大多采用分布式方案（多个微型计算机协同工作）来提高数据规模、响应速度和用户数量，它们一般都保持一个大约50，000，000网页的索引
20、数据库，每天能够响应10，000，000次用户检索请求。1997年11月，当时最先进的几个搜索引擎号称能建立从2，000，000到100，000，000的网页索引。Altavista搜索引擎声称他们每天大概要承受20，000，000次查询。自1998年到现在，出现了一个搜索引擎空前繁荣的时期，我们统称这一时期的搜索引擎为第三代搜索引擎。第三代搜索引擎的发展有如下几个特点：1. 索引数据库的规模继续增大，一般的商业搜索引擎都保持在几千万甚至上亿个网页。2. 除了一般意义上的搜索以外，开始出现主题搜索和地域搜索。很多小型的垂直门户站点开始使用该技术。3. 由于搜索返回数据量过大，检索结果相关度评价
21、成为研究的焦点。相关的研究又可以分为两类：一类是对超文本链的分析，在这方面Stanford大学的Google系统7和IBM的Clever系统8作出了很大的贡献；另一类是用户信息的反馈，DirectHit系统采用的就是这种方法。4. 开始使用自动分类技术。Northern Light和Inktomi的Directory Engine都在一定程度上使用了该技术。2000年搜索引擎2000年大会上，按照Google公司总裁Larry Page的演讲，Google正在用3,000台运行Linux系统的个人电脑在搜集Web上的网页，而且以每天30台的速度向这个微机集群里添加电脑，以保持与网络的发展相同步
22、。每台微机运行多个爬虫程序搜集网页的峰值速度是每秒100个网页，平均速度是每秒48.5个网页，一天可以搜集超过4，000，000网页。1.3主题搜索引擎第四代搜索引擎随着信息多元化的增长，千篇一律的给所有用户同一个入口显然已经不能满足特定用户更深入的查询需求。同时，这样的通用搜索引擎在目前的硬件条件下，要及时更新以得到互联网上较全面的信息是不太可能的。针对这种情况，我们需要一个分类细致精确、数据全面深入、更新及时的面向主题的搜索引擎。由于主题搜索运用了人工分类以及特征提取等智能化策略，因此它比上面提到的前三代的搜索引擎将更加有效和准确，我们将这类完善的主题搜索引擎称为第四代搜索引擎。1.4 小
23、结这一章，概述了主题搜索引擎的产生背景以及它在搜索引擎历史上的地位。由于天网主题搜索是建立在原来天网搜索系统的基础上的，第二章将会介绍天网搜索引擎的系统结构，并着重剖析搜索器和主控程序的设计实现，这是因为主题搜索需要对这两部分做较大的改动。第三章将着重分析导向词、特征提取、权威和中心网页、超链分析以及网页评分等多种主题搜集策略的运用。笔者将会在第四章详细介绍天网主题搜索引擎的设计与实现。最后是第五章的系统现状性能以及第六章的总结展望，在这里笔者会比较一下使用了主题搜集策略以后的天网主题搜索引擎与使用以前的天网通用搜索引擎的差别，并展望以后的工作。第二章 天网搜索引擎系统结构2.1系统简介天网由
24、于采用了可伸缩的分布式结构、查询Cache、索引数据库和检索数据库分开等先进、有效的技术，使得系统占用资源少、信息收集速度快、用户查询响应时间快（系统对96.7%以上的查询可在1秒钟之内作出响应）、查准率和查全率较高，基本达到了实用化程度。系统在设计和实现过程中，充分考虑到了用户和管理员的使用习惯，提供了浏览器、电子邮件、中英文用户接口和方便使用、功能丰富的管理工具，因而有很好的可用性和易用性。由于“天网”功能全面、性能突出，软件世界杂志年第7期将“天网”评价为国内最好的中英文搜索引擎。在2001年4月，天网累计访问量和索引网页数均突破了10，000，000。“天网”从1997年10月在CER
25、NET上提供服务以来，得到了用户的欢迎和好评。下面是不同时间统计的系统的使用情况：时间1998年9月1999年9月2000年5月2001年5月平均每天访问人次22001011331817513682.2系统结构及各部分功能天网系统主要由WWW信息存取和分析子系统(主控程序)、WWW信息收集控制子系统(搜索器)、资源索引数据库、信息检索子系统、管理和监控子系统等几个部分组成。各个部分的功能如图2.1所示：HTML文档WWW存取、分析 收集控制子系统信息检索子系统 WWW服务器资源索引数据库WWW浏览器WWW浏览器WebGather图2.1 WebGather系统总体结构示意图HTTPCGI管理和
26、监控子系统WWW存取、分析WWW Server2.2.1 WWW信息存取和分析子系统（主控程序）根据WWW信息收集控制子系统提供的URL和相关信息，使用HTTP协议，在Internet上获取相关资源，并能就对方主机返回的不同状态码作出相应处理。对取回的Web页面(主要是HTML格式)进行分析，自动对中文编码进行识别和转化，对中文信息进行分词、提取页面的标题、关键词、摘要以及其中的超链（HyperLink）。 将分析的结果通过扩展SOIF接口提交给信息收集控制子系统。2.2.2 WWW信息收集控制子系统（搜索器）根据配置文件运用自然语言理解和知识获取技术、引导信息收集系统优先访问特定知识领域和特
27、定地域范围内的信息，向HTML存取分析进程发送需访问的URL及相关信息，接收其发回的访问和分析结果。将相应的数据存入信息数据库中。并对信息收集的频度和流量加以控制。2.2.3 资源索引数据库存储收集到的WWW信息，以及分析的结果。并对其重新进行基于词的分级优化索引，以加快查询速度2.2.4 信息检索子系统提供基于WWW方式的信息检索服务。用户通过任何标准的WWW浏览器直接访问。检索系统可以支持在一次检索中使用多个检索词(中、英文)，并支持检索词之间的逻辑关系（与、或）。还可以指定查询的范围和方式（精确、模糊）。检索结果以HTML形式返回给用户。各项结果的标题与它所对应的URL用超链连接起来。用
28、户只需在浏览器中点中检索结果项的标题，就能马上取得相应页面的实际内容。命中的URL页面按它与用户检索关键词的关联程度排序，使用户的检索更有效率。系统还支持在上一次返回的结果中进行查询。2.2.5 管理和监控子系统提供系统配置，启动、停止、监控、统计等管理功能。信息收集控制子系统与WWW存取分析进程之间的信息交互是通过TCP Socket连接来实现的，因此各子系统可以分布运行于网络中不同的主机上。2.3主控程序及搜索器的实现2.3.1 主控程序主控程序的系统结构如图2.2所示，其中带阴影的模块是实现天网主题搜索引擎时候需要改动的部分，在第四章将会详细介绍。原主控程序的流程如图2.3：主控程序搜索
29、器搜索器Restart进程共享内存图2.4 搜索器模块图2.3.2 搜索器搜索器，负责收集主控进程指定的网页，分析网页，提取网页中的信息，将收集的信息回送给主控进程。主控进程和收集分析进程之间通过扩展的SOIF接口交换数据。搜索器在运行时会将它的进程号，正在收集的URL，当前所处的状态，如正在与目标主机建立连接、正在等待主控进程分发URL等，记录在共享内存中，供管理程序使用。搜索器在分析一个网页的时候，可以得到这个网页上的所有超链接URL。对于每一个URL，搜索器都给它赋予一定的权值，才返回给主控程序，以便主控程序按照一定的顺序在下一轮发给搜索器。下面这个公式用来计算URL的权值（未考虑导向词
30、）：Pirority(URL) = a1 * domain_weight + a2 * link_popularity + a3 * priority(parent_url) + a4 * directory_depth 其中domain_weight 表示URL中各个域的权值。link_popularity表示到目前为止，这个超链接被其他网页引用的次数。parent_url表示它的上一级双亲url的权值。directory_depth表示这个url中目录的深度，越深的目录，这个url的权值越低。2.4小结这一章，简单介绍了完整的天网搜索引擎的系统结构，并重点分析了其中的主控程序和搜索器的实现
31、流程和URL选择算法。在下面的两章笔者将会阐述如何对这两部分修改以实现主题搜索功能。第三章将着重分析导向词、特征提取、权威和中心网页、超链分析以及网页评分等多种主题搜集策略的运用。第四章将会详细介绍这些方法在天网主题搜索引擎的实现上的具体应用。第三章 主题搜索策略3.1 导向词3.1.1 导向词及权值的配置导向词就是一组关键词，它们会引导搜索器按照一定顺序搜索整个网络，使得搜索引擎可以在最短的时间里面得到最全面的跟某一个主题相关的信息。通过设置导向词以及它们对应的不同权值，所有标题、作者、正文或超连接文本中含有某一导向词的网页都会被赋予较高的权值，在搜索的时候会优先考虑。搜索器在向主控程序获得
32、URL的时候也是按照权值由高到低的顺序。反之，搜索器在向主控程序提交新的URL和它的权值的时候，主控程序会按照权值预先排序，以便下一次有序的发给搜索器。权值的设置有两种方法，第一种是根据管理员的经验手工设置，第二种是给定一个跟主题有关的网页集合，由程序自动提取这些网页里面共同的特征，在这些网页里面都出现的很多的关键词，它就被选作导向词。我们把第二种方法称为“特征提取”。手工设置的好处是实现简单，同时人的经验一般比较准确，跟实际情况不会出现大的偏差，缺点是导向词可能有缺漏，权值的量化定义不够精确；特征提取的优点是权值量化定义精确，但是它要求选取用来提取特征的网页集合必须是非常有代表性而且是全面概
33、括的，否则导向词就可能实现很大的偏差。综合这两种方法的优缺点，我们的系统采用了这两种方法的结合策略：1 手工设置好一组导向词和它们对应的权值；2 用这组导向词到原搜索引擎中查找出对应的网页；3 按权值的比例选取一定数量的网页（比如权值是10，可以选10n个网页）；4 用这些网页组成的集合作为特征提取程序的输入，得到一组新的导向词。以下是以“电影”为主题的一个例子的导向词及权值的配置:导向词权值电影10影视10导演10编剧10监制10主角8配角8奥斯卡5影星93.1.2 根据导向词及权值改变搜索顺序由上一章提到的URL优先级计算公式：Pirority(URL) = a1 * domain_wei
34、ght + a2 * link_popularity + a3 * priority(parent_url) + a4 * directory_depth 将导向词及其权值考虑在内，可以得到新的URL优先级计算公式：Pirority(URL) = a1 * domain_weight + a2 * link_popularity + a3 * priority(parent_url) + a4 * directory_depth + a5 * Oi3.2 网页评分(PageRank)3.2.1 引用计数(HIT NUMBER)原系统中在搜索器搜集网页的时候，对于每一个网页数据库中都有一个指向该
35、网页的其他网页总数，称为Hit Number。搜集器每访问一个新的网页，都会逐一检查这个网页的所有超连接，如果发现这些超连接里面有指向已经访问过的网页，那么这个已经访问过的网页的Hit Number将会被相应的加一。由此可见，等到搜索器已经访问过的网页集合足够大的时候（理想情况是整个网络），Hit Number越大，表示这个网页被别人引用得越多，由此可以估计这个网页也越重要。这种网页不论是在搜索器抓取网页这方面，还是在检索器最终给用户返回结构这方面，都应该放在优先处理的位置。但是，单纯比较两个网页的Hit Number，有时候可能无法估计出这两个网页正确的重要性排序。比如有两个网页，它们在In
36、ternet上同样只是被引用了一次。一个是一份已经过时的个人简历，被一个个人网站所引用，除了作者以外基本没有其他人关心；另外一个是当天发生的重大国际新闻，被Yahoo！所引用，每一秒钟都被世界各地不同肤色的数以百计的人浏览。这时候你不能由两个网页的Hit Number一样（都是1）就得出两个网页在Internet上一样重要的结论。这样，我们需要一个更加深入的指标来评测，这就是下面提到的网页评分（PageRank）。3.2.2 网页评分(PAGERANK)在考虑一个网页被另一个网页的引用时候，不是单纯的将被引用网页的Hit Number加一，而是将引用网页的连接数作为权，同时将该引用网页的重要性
37、也考虑进来（看看上面提到的例子，Yahoo！引用的网页显然比个人网站引用的网页重要，因为Yahoo！本身很重要），就可以得到扩展后的网页评分。最早提出网页评分的计算方法是Google。它们提出了一个“随机冲浪”模型来描述网络用户对网页的访问行为。模型假设如下：1) 用户随机的选择一个网页作为上网的起始网页；2) 看完这个网页后，从该网页内所含的超链内随机的选择一个页面继续进行浏览；3) 沿着超链前进了一定数目的网页后，用户对这个主题感到厌倦，重新随机选择一个网页进行浏览，并重复2和3。按照以上的用户行为模型，每个网页可能被访问到的次数就是该网页的链接权值。如何计算这个权值呢？PageRank采
38、用以下公式进行计算：其中Wj代表第j个网页的权值；lij只取0、1值，代表从网页i到网页j是否存在链接；ni代表网页i有多少个链向其它网页的链接；d代表“随机冲浪”中沿着链接访问网页的平均次数。选择合适的数值，递归的使用以上公式，即可得到理想的网页链接权值。该方法能够大幅度的提高简单检索返回结果的质量，同时能够有效的防止网页编写者对搜索引擎的欺骗。因此可以将其广泛的应用在检索器提供给用户的网页排序上，对于网页评分越高的网页，就排的越前。3.3 权威网页(Authority)和中心网页(Hub)3.3.1 什么是权威网页和中心网页权威网页，顾名思义，是给定主题底下的一系列重要的权威的网页。其重要
39、性和权威性主要体现在以下两点：第一点， 从单个网页来看，它的网页内容本身对于这个给定主题来说是重要的；第二点， 从这个网页在整个互联网重的地位来看，这个网页是被其他网页承认为权威的，这主要体现在跟这个主题相关的很多网页都有链接指向这个网页。由此可见，权威网页对于主题搜索引擎的实现有很重大的意义。主题搜索引擎一个很关键的任务就是从互联网上无数的网页之中最快最准的找出这些可数的权威网页，并为他们建立索引。这也是有效区别主题搜索引擎和前三代传统通用搜索引擎的重要特征。中心网页，是包含很多指向权威网页的超链接的网页。最典型中心网页的一个例子是Yahoo！，它的目录结构指向了很多主题的权威网页，使得它兼
40、任了很多主题的中心网页。由中心网页出发，轻而易举的就会到达大量的权威网页。因此，它对于主题搜索引擎的实现也起了很大的意义。权威网页和中心网页之间是一种互相促进的关系：一个好的中心网页必然要有超链接指向多个权威网页；一个好的权威网页反过来也必然被多个中心网页所链接；。他们的关系如图3.1所示。权威网页中心网页图3.1 权威网页和中心网页权威网页权威网页中心网页3.3.2 发掘权威网页的难度前三代传统搜索引擎很大程度运用了单个网页内容（网页上出现的关键词）来发掘重要的网页，而忽略了网页在互联网中的地位。用这种方法要从互联网上无数的网页之中找出这些可数的权威网页，有较大的难度。再看一下上面的图3.1
41、，如果每一个权威网页都像图上那样写着“权威”两个字来让你发现，那么我们的工作将会简单的多，可是现实却没有这么理想。首先，根据关键词出现的频率很难判定这个网页的权威性。考察一下这个例子：比如你想找关于“北京大学”的权威网页。显然，北京大学的主页是互联网上关于“北京大学”最权威的网页之一。用基于关键词的传统的搜索引擎来查找，很自然的会输入“北京大学”或者“北大”。这时候的查询效果不一定很理想。因为互联网上有成千上万包含“北京大学”或“北大”作为关键词的网页（如“北大方正”，“北大在线”，“北京大学网络中心”等），而北大主页并不一定是“北京大学”或“北大”这两个关键词出现的最多最显著的网页。这样，不
42、禁令人猜想到，根本没有一种方法可以从网页内在内容本身来判断这个网页的权威性。其次，很多权威网页本身并没有包含跟它所属主题相关的关键词。比如你想找出网上“电脑销售”的大公司。如果你以“电脑销售”作为关键词，你很难找到“联想”或“方正”公司的主页，因为他们的主页上根本不会出现“电脑销售”的字眼。但他们的的确确是“电脑销售”的权威网页。由此我们可以得出结论，要找出权威网页，必须将该网页的内在因素和外在因素都考虑在内，也就是说，除了要分析这个网页包含的关键词，还要分析互联网上其他网页指向这个网页的超链接。3.3.3 权威网页和中心网页的计算公式虽然上面提到了发掘权威网页的难度，但根据权威网页和中心网页
43、互相促进的关系，可用递推的方法循环计算出权威网页和中心网页。对于与某一个主题相关的网页集合中的每一个网页，我们都给他们定义两个参数：A（Authority）和H（Hub）。A值越高表示网页的权威度越高，H值越高表示网页的中心度越高。将网页集合用有向图G=（V，E）表示，其中节点集V由网页组成，有向边集合E表示网页间的超链接。对于IV，AI、HI分别表示I对应的网页的权威度和中心度。为了控制A、H的范围，我们将A、H定义在0，1，并且规格化A、H使得：IV(AI)2 = 1IV(HI)2 = 1对于每一个节点I，均有：AI = （i，j）E(HJ)（3.1）HI = （i，j）E(AJ) （3.
44、2）（本文只给出一个计算A值和H值的递推公式，有关该公式的收敛性证明，请参阅参考资料5）3.3.4 计算权威网页和中心网页的算法根据上面提供的公式，我们很容易就得到计算权威网页和中心网页的算法：计算权威网页和中心网页算法（G，k）G: 网页集合对应的有向图；k: 一个常数；定义z ：向量(1，1， 1，1) R n ；X0 := z；Y0 := z；For i = 1，2，k用 (Xi-1，Yi-1)代入公式(3.1)得到新的Xi；用 (Xi，Yi-1)代入公式(3.2)得到新的Xi；规格化Xi得到新的Xi；规格化Yi得到新的Yi；EndReturn (Xk，Yk).3.4 超链描述文本分析(
45、Hyperlink Anchor Text Analysis) 图：网页的互链结构 A C D B互联网的魅力在于“互联”，从互联网上任何一个地方出发，就可以轻而易举的到达世界上其它的地方。实现互联是通过一系列的“超级文本链接”（Hypertext Link），可以这样说，没有了“超级文本链接”，互联网会变得不名一文。每一个超级链接都有一个描述文本（Anchor Text），这个文本反映了该网页与该链接所至网页的某种关系，是互联的关键所在。通过分析这个描述文本，就可以得到网页之间重要的关系。原系统将这个描述文本与其所在的网页关联。我们在新系统的实现中，将描述文本与其所指向的网页相关联。这样做会对程序的编写带来一定的复杂性，因为搜索器在处理当前网页的时候，会遇到这个网页上很多的超链接描述文本，如果将它们都与当前网页关联，处理起来就很简单；否则，如果对于每一个超链接描述文本都将其与目标网页关联，就需要频繁的切换当前处理的网页，影响到了搜索器处理网页的速度。虽然这样做增添了程序的复杂度，但是却有它自身的很多好处：首先，描述文本通常比网页上的文本要更加精确的概括这个网页；其次，基于文本切词的搜索引擎并不能处理网络上的所有格式，比如一些图像，程序，数据库和多媒体等格式的文件，但是依靠超链接里