基于DNS的网页搜索引擎

一种基于DNS的分层式网页搜索引擎研究

王亮1+, 郭一平2 1

?

(华中科技大学 控制系，湖北 武汉 430074) (华中科技大学 图书馆，湖北 武汉 430074)

2

Study of a layered Web search engine based on DNS

1+

2

Wang Liang, Guo Yiping

1

(Department of Control Science and Control Engineer, Huazhong University of Science and Technology, WuHan, 430074 ，China)

2

(Library of Huazhong University of Science and Technology, WuHan 430074, China)

+ Corresponding author:Phn:+86-27-87553494, Fax +86-27-87544415, E-mail: guoypm@hust.edu.cn, http://dris.hust.edu.cn

Abstract: Web search engine based on DNS, the standard proposed solution of IETF for public web search system, is introduced in this paper. Now no web search engine can cover more than 60 percent of all the pages on Internet. The update interval of most pages database is almost one month. This condition hasn't changed for many years. Converge and recency problems have become the bottleneck problem of current web search engine. To solve these problems, a new system, search engine based on DNS is proposed in this paper. This system adopts the hierarchical distributed architecture like DNS, which is different from any current commercial search engine. In theory, this system can cover all the web pages on Internet. Its update interval could even be one day. The original idea, detailed content and implementation of this system all are introduced in this paper.

Keywords: Search engine; Domain name; Information retrieval; Distributed system; Web-based service; Information network

摘 要: 本文介绍了IETF构建公共网页搜索系统的标准提案“基于DNS的网页搜索引擎”。目前没有一个网页搜索引擎可以覆盖超过60%的互联网上全部网页，而大部分的网页数据库更新周期都在一个月左右。在更新率和覆盖率等关键性能上当前的搜索引擎多年来几乎没有任何明显的改进。为了解决搜索引擎遇到的这些瓶颈性问题，本文提出了一种全新的网页搜索引擎，“基于DNS的网页搜索引擎”。此系统采用了与现有商业化搜索系统完全不同的分层的分布式结构。从理论上讲，此系统可以覆盖全部的互联网网页，而且其网页数据库可以做到每天更新。此系统基本思路来源，详细内容和具体实施都将在本文中逐一介绍。

?华中科技大学“211”资助项目

关键词: 搜索引擎;域名;信息检索;分布式系统;基于Web的服务;信息网络 中图法分类号: TP391；TP393.4 文献标识码: A

1 介绍

由于整个WWW是一个大规模动态的分布式系统，网页更新和增加非常频繁，搜索引擎很难跟踪WWW的每一处的变化，因此很难保证覆盖率和更新率的要求。根据1998年的统计数据，几乎所有的网页搜索引擎的数据平均更新周期都达到一个月，而没有一个搜索引擎能够覆盖超过50%的互联网全部网页，而时至今日这些数据依然适用。

搜索引擎遇到的这些颈性问题很大程度上是由其集中式结构造成的，一般的搜索引擎都有一个或多个大的数据中心，在此执行全部的网页下载和索引工作。如著名搜索引擎Google就有上万台服务器来并行完成此工作。但由于WWW系统的地域分布式特性以及网络基础条件等方面的限制，随着WWW系统的迅速扩张，这种集中式系统必然会遇到覆盖率和更新率方面的瓶颈问题。

整个WWW系统的地域分布式特性和现有搜索引擎的集中式体系结构之间的矛盾是造成搜索引擎两个瓶颈性问题的主要原因，要解决这两个问题必须构建一种地域上分布式的搜索引擎。但近年来的搜索引擎研究主要集中在知识挖掘、个性化检索及网页排序算法的改进等方面，在搜索引擎的基本体系结构方面的研究很少，尽管旨在寻找新型搜索引擎的研究都是基于分布式框架的，但发展非常缓慢。

事实上在1994年出现的第一个网页搜索系统Harvest[2]就是一种分布式检索系统，但由于其算法复杂，开销巨大，因此仅停留在理论研究阶段，而没有成为真正的Internet服务。而后兴起的商业化搜索引擎考虑到成本等方面因素都采用了集中式的体系结构，并一直处在主导地位。而此后基于分布式结构的搜索引擎研究大都停留在理论阶段，典型的如CSE（合作式搜索系统），和其它一些研究一样,它们都是Harvest的改进系统。这些方法的主要原则就是要求每个Web服务器都对自己的网页进行索引，然后分别提供检索接口，而搜索引擎则利用这些接口进行信息检索，这种方法可以部分解决更新率的问题，但检索速度很难保证，而且并非所有的web服务器管理者都愿意提供这样的检索接口。文献[4]则针对此问题进一步提出一种分层次的共享网页数据库的解决方案，可以从理论上解决更新率问题并保证检索的速度,但是具体怎么划分不同的层次，以及如何实现等问题依然没有得到很好的解决。

先前分布式网页搜索引擎研究经验教训说明一个成功的分布式系统必须解决两个基本难题，首先是系统基本结构的确定问题，包括整个系统如何进行划分，如何保证系统可以覆盖整个WWW系统等；再者就是实施的激励机制问题，作为一个分布式系统，其管理和建设必然是由不同的单位组织负责的，如果各个单位组织不能从系统的实施中受益，而仅仅是强调共享，技术再先进也只会是纸上谈兵，而这也是目前分布式检索系统难以推行的根本性原因。对一个分布式系统来说实施需求的发现比技术研究本身更为重要。

[3]

[1]

2

2 新方法的来源

2.1 基本思路

我们从DNS技术中得到一些基本的启发。如今几乎每个高校和大的机构都有自己的域名服务器，并与高层服务器协调配合，这种分层的分布式体系使互联网上所有的站点都能得到有效的管理。而DNS技术本身发展也经历了从集中式到分布式的转变，在DNS系统建立之初,仅仅有数百个Web站点,而相应的DNS数据库可以存储在单个服务器上，但是当WWW上站点数目达到上百万时，各个站点分布世界各处而且更新较为频繁，集中式的DNS系统显然很难高效地管理如此多的站点，提供优良的解析服务，DNS最终发展成为一个分层的分布式系统。

由于种种原因，目前所有的商业搜索引擎都采用了集中式构架，但随着WWW的迅速扩张，网页搜索引擎恰恰也遇到了当初DNS技术遇到的问题，如今已有上百亿张网页分布在世界不同角落的服务器上，而当前的搜索引擎却要反复地访问并下载全部的网页到一个数据库系统中，数据的更新率和覆盖率根本无法得到保障。显然集中式的框架是不适于分布式的WWW信息管理的，而正是系统基本结构选择的不恰当导致了当前搜索引擎遇到的数瓶颈性问题。

参考DNS改进和发展的历史可以发现Web搜索引擎若像DNS那样采用一种等级分布式的框架，一些基本的瓶颈性问题就可能会得到一定的解决。而进一步地看，既然DNS能够索引各个站点的名称，那么是否也能索引整个站点的所有网页呢？因此就有了“搜索引擎+DNS”的基本思路。 2.2 系统基本框架

如上所述，基于DNS的搜索引擎采用了和DNS完全相同的基本结构，具体如图1所示。

整个系统分为三层，第三层为DNS的三级域，一般对应于某个组织机构，如一个大学；第二层一般对应于国家的各个主干网；第一层则对应于某个国家。

rootFirst layerUk(England)Ru(Russia)Cn(China)Fr(France)?Second layerGov.cnEdu.cn(CERNET)Com.cn?Third layerHust.edu.cnPku.edu.cnTsinghua.edu.cn?Figure 1 Architecture of system图1 系统结构

采用此基本框架，我们可以简单地在最底层下载网页数据，然后逐级传递到最上层的服务器上。由于网页的下载更新工作都在不同的底层节点进行，而这些节点一般又都对应于某个局域网，因而这种分布采集、逐层递交的方式可以保证整个系统的数据每天更新，这样更新率问题就得到了很好的解决。但是另一个问题

3

是，按照这种方法，顶层的服务器数据存储量可能依然很大，我们可能不得不采用分布计算等复杂技术来保障顶层服务器的数据存储和检索服务质量。要建立一个可以“镜像”整个Internet数据的系统几乎是不可能的,必须采用其它方式来完成此任务。

因此我们首先对搜索引擎基本技术及当前具有代表性的几种信息检索系统和网页搜索引擎的两种基本算法做一简介，在此基础上对系统的基本思想进行具体的实现研究。

3 搜索引擎相关技术

3.1 搜索引擎基本技术

目前大多数实用的商业化网页搜索引擎都是基于集中式结构设计的，其一般包括三个主要部分，网页下载器，搜索器和检索接口，具体如下所述：

? 网页下载器。网页下载器主要从WWW上下载网页，其一般按照网页上的链接关系进行漫游。 ? 检索器。其主要工作是将网页数据进行索引，一般要进行文本倒排等相关工作。 ? 检索接口。其主要功能是为用户提供最终的经过排序的 检索结果。 3.2 两种基本算法

网页搜索引擎按照基本排序算法划分可分为以词频统计为主的第一代搜索引擎和以超链接分析为主的第二代搜索引擎。

1 基于词频统计的搜索引擎[6]。词频统计基于传统的全文检索算法，如文档的向量空间模型和tf*idt算法。此类算法中网页文本的每一个词汇都作为网页的索引词，由词频和位置信息确定索引词的重要性，并作为在此网页在检索结果中的排名权值。一些改进的算法则考虑到网页自身的特点，将标签(Tag)的影响反映在权值计算中。

2 基于超链接分析的搜索引擎。其基本思路为一个网页的排名权值由指向此网页的其它网站网页的数目来决定，即一个网页被链接的次数越多就说明此网页的质量越高。具有代表性的实现算法有两种，由Google提出的PageRank[7][8]算法和IBM研究院Clever系统中采用的HITS( Hyperlink Induced Topic Search)[9]算法。它们都利用了网页和超链接组成的有向图，根据相互链接的关系进行递归的运算。但又有很大的区别，主要在于运算的时机。Google是在网页搜集告一段落时，离线地使用一定的算法计算每个网页的链接权值，在检索时只需要从数据库中取出这些数据即可。这样做的好处是检索的速度快，但丧失了检索时的灵活性。Clever使用即时分析运算策略，每得到一个检索请求，它都要从数据库中找到相应的网页，同时提取出这些网页和链接构成的有向子图，再运算获得各个网页的相应的链接权值。这种方法虽然灵活性强，并且更加精确，但在用户检索时进行如此大量的运算，会导致检索效率的急剧下降

[10]

。目前大多数搜索引擎均采用以

PageRank为基础的改进算法，而实际使用的排序算法往往对基于词频统计得到的权值、超链接分析权值以及用户行为分析等其它因素的计算得到的权值进行综合分析，采用按照比例组合的办法得到一个网页的最终权值[11]。

如果搜索引擎覆盖的范围较小，如仅仅是一个校园网的搜索引擎，则采用基于词频统计的网页排序算法

4

就可基本满足需求，但如果范围较广，如一个国家范围的搜索引擎，一般则采用基于超链接分析的排序算法。 3.3 三种检索系统

按照基本体系结构划分，目前已有三种不同类型的信息检索系统，具体如下所述：

1 基于传统数据库的集中式检索系统。这种系统拥有自己的数据采集装置，如网页搜索引擎中的Spider，电子图书馆的扫描识别系统等，所有的数据都存储并索引在一个数据库系统中。虽然目前很多网页搜索引擎都通过上万台服务器并行提供服务，但按其基本结构划分仍然可归为此类。

2 基于元数据采集的检索系统。当需要整合多种类型的资源或数据源规模较大的情况下，一般采用从各个小的子数据库中采集元数据并整合到一个系统的方式构建信息检索系统。这类系统没有自己的数据采集模块，仅存储起索引功能的元数据，比较常用的如OAI系统。

3分布式检索系统。如果数据源的规模非常大，以至于元数据都很难在一个独立的数据系统中存储并有效管理，则可采用分布式的信息检索结构。分布式信息检索系统中各个子数据库系统分别提供符合统一标准的信息检索接口，执行信息检索时由总系统负责协调各个子数据源完成检索请求。这类系统中没有存储实际的数据记录，仅仅对各个子数据源的检索接口等特征作基本的描述索引。著名的如Stanford数字图书馆计划中的InfoBus系统[5]。

信息检索系统基本结构的选择一般根据以下规则，即随着数据源规模扩大和数据类型的增多一般可以依次选择常规数据库型、元数据采集型、分布式检索型。

4 基于DNS的网页搜索引擎的实现

根据新系统三个层次的具体特点，我们分别采用了不同的系统构架和基本算法，以构建一个更为高效的网页检索系统。我们按照从底层到高层的方式逐一介绍各层的不同的搜索系统。 4.1 第三层：集中式检索系统

第三层的系统将构建一个三级域内的网页搜索引擎，如一个大学校园网的搜索引擎，其设计原理同现有的搜索引擎基本相同，差别仅在于其搜索范围较小。这里采用了集中式的设计结构，此检索系统由三个部分组成：网页下载器，索引器以及检索接口。下面对此三部分逐一介绍。

4.1.1 网页下载器

此系统的网页下载器将下载某个三级域内的所有网页。如 “www.hust.edu.cn ”是华中科技大学域名，那么此域名下的低级域名如计算机系的域名“cs.hust.edu.cn”均可在此三级域名服务器上查到。因此相应的Spider程序只要依照DNS列表就可下载此域内的所有网页。

系统Spider的工作是按不同的站点划分的，其依次访问一个域内的全部站点。当一个Spider访问某个Web服务器时，它将下载此服务器上的所有内容，当遇到指向其他服务器的链接时，也将此链接作为本站内容下载，但不再下载更深层次的链接，这些指向外部的链接相当于Spider的访问终止标记，我们将这样的链接称为“终止标志链接”。

这一点和现有的网页搜索引擎有较大的不同。它们的Spider一般采用自由漫游的方式采集网页信息，没

5

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库基于DNS的网页搜索引擎在线全文阅读。