当前位置:首页 > 搜索引擎营销 > SEO优化技术 > 正文

搜索引擎蜘蛛工作原理及分布式蜘蛛体系结构设计

  • 2012-02-27
  • 来源:阿龙网
  • 作者:
  • 人气:0
  • 评论:0
关于搜索引擎蜘蛛程序的一些原理及体系结构纯技术文章,一些地方可能不会看的很明白,对于SEO行业,经常和搜索引擎及其爬虫程序打交道,仔细浏览下,一些不清楚而自己又很想了解的地方,可以借助搜索来需找相关解释

关于搜索引擎蜘蛛程序的一些原理及体系结构纯技术文章,一些地方可能不会看的很明白,对于SEO行业,经常和搜索引擎及其爬虫程序打交道,仔细浏览下,一些不清楚而自己又很想了解的地方,可以借助搜索来需找相关解释,对工作还是有帮助的(个人认为值得注意的地方已加红显示)。

搜索引擎蜘蛛工作原理

1、聚焦爬虫工作原理及关键技术概述

搜索引擎蜘蛛是一个自动提取网页的程序,它为搜索引擎从Internet网上下载网页,是搜索引擎的重要组成。传统爬虫从一个或若干初始网页的URL开始,获得初始网页上的URL,在抓取网页的过程中,不断从当前页面上抽取新的URL放入队列,直到满足系统的一定停止条件。聚焦爬虫的工作流程较为复杂,需要根据一定的网页分析算法过滤与主题无关的链接,保留有用的链接并将其放入等待抓取的URL队列。然后,它将根据一定的搜索策略从队列中选择下一步要抓取的网页URL,并重复上述过程,直到达到系统的某一条件时停止,另外,所有被爬虫抓取的网页将会被系统存贮,进行一定的分析、过滤,并建立索引,以便之后的查询和检索;对于聚焦爬虫来说,这一过程所得到的分析结果还可能对以后的抓取过程给出反馈和指导。

相对于通用搜索引擎蜘蛛,聚焦爬虫还需要解决三个主要问题:

1.对抓取目标的描述或定义;
2.对网页或数据的分析与过滤;
3.对URL的搜索策略。
抓取目标的描述和定义是决定网页分析算法与URL搜索策略如何制订的基础。而网页分析算法和候选URL排序算法是决定搜索引擎所提供的服务形式和爬虫网页抓取行为的关键所在。这两个部分的算法又是紧密相关的。

2、抓取目标描述

现有聚焦爬虫对抓取目标的描述可分为基于目标网页特征、基于目标数据模式和基于领域概念3种。

基于目标网页特征的爬虫所抓取、存储并索引的对象一般为网站或网页。根据种子样本获取方式可分为:

1.预先给定的初始抓取种子样本;
2.预先给定的网页分类目录和与分类目录对应的种子样本,如Yahoo!分类结构等;
3.通过用户行为确定的抓取目标样例,分为:用户浏览过程中显示标注的抓取样本;通过用户日志挖掘得到访问模式及相关样本。
其中,网页特征可以是网页的内容特征,也可以是网页的链接结构特征,等等。

基于目标数据模式的爬虫针对的是网页上的数据,所抓取的数据一般要符合一定的模式,或者可以转化或映射为目标数据模式。

另一种描述方式是建立目标领域的本体或词典,用于从语义角度分析不同特征在某一主题中的重要程度。

3、网页搜索策略

网页的抓取策略可以分为深度优先、广度优先和最佳优先三种。深度优先在很多情况下会导致爬虫的陷入(trapped)问题,目前常见的是广度优先和最佳优先方法。

3.1、广度优先搜索策略

广度优先搜索策略是指在抓取过程中,在完成当前层次的搜索后,才进行下一层次的搜索。该算法的设计和实现相对简单。在目前为覆盖尽可能多的网页, 一般使用广度优先搜索方法。也有很多研究将广度优先搜索策略应用于聚焦爬虫中。其基本思想是认为与初始URL在一定链接距离内的网页具有主题相关性的概率很大。另外一种方法是将广度优先搜索与网页过滤技术结合使用,先用广度优先策略抓取网页,再将其中无关的网页过滤掉。这些方法的缺点在于,随着抓取网页的增多,大量的无关网页将被下载并过滤,算法的效率将变低。

3.2 最佳优先搜索策略

最佳优先搜索策略按照一定的网页分析算法,预测候选URL与目标网页的相似度,或与主题的相关性,并选取评价最好的一个或几个URL进行抓取。它只访问经过网页分析算法预测为“有用”的网页。存在的一个问题是,在爬虫抓取路径上的很多相关网页可能被忽略,因为最佳优先策略是一种局部最优搜索算法。 因此需要将最佳优先结合具体的应用进行改进,以跳出局部最优点。将在第4节中结合网页分析算法作具体的讨论。研究表明,这样的闭环调整可以将无关网页数量降低30%~90%。

4、网页分析算法

网页分析算法可以归纳为基于网络拓扑、基于网页内容和基于用户访问行为三种类型。

4.1、基于网络拓扑的分析算法

基于网页之间的链接,通过已知的网页或数据,来对与其有直接或间接链接关系的对象(可以是网页或网站等)作出评价的算法。又分为网页粒度、网站粒度和网页块粒度这三种。

4.1.1、网页粒度的分析算法

PageRank和HITS算法是最常见的链接分析算法,两者都是通过对网页间链接度的递归和规范化计算,得到每个网页的重要度评价。 PageRank算法虽然考虑了用户访问行为的随机性和Sink网页的存在,但忽略了绝大多数用户访问时带有目的性,即网页和链接与查询主题的相关性。针 对这个问题,HITS算法提出了两个关键的概念:权威型网页(authority)和中心型网页(hub)。

基于链接的抓取的问题是相关页面主题团之间的隧道现象,即很多在抓取路径上偏离主题的网页也指向目标网页,局部评价策略中断了在当前路径上的抓取行为。部分文献提出了一种基于反向链接(BackLink)的分层式上下文模型(Context Model),用于描述指向目标网页一定物理跳数半径内的网页拓扑图的中心Layer0为目标网页,将网页依据指向目标网页的物理跳数进行层次划分,从外层网页指向内层网页的链接称为反向链接。

4.1.2、网站粒度的分析算法

网站粒度的资源发现和管理策略也比网页粒度的更简单有效。网站粒度的爬虫抓取的关键之处在于站点的划分和站点等级(SiteRank)的计算,SiteRank的计算方法与PageRank类似,但是需要对网站之间的链接作一定程度抽象,并在一定的模型下计算链接的权重。

网站划分情况分为按域名划分和按IP地址划分两种。一些文献讨论了在分布式情况下,通过对同一个域名下不同主机、服务器的IP地址进行站 点划分,构造站点图,利用类似PageRank的方法评价SiteRank。同时,根据不同文件在各个站点上的分布情况,构造文档图,结合 SiteRank分布式计算得到DocRank。利用分布式的SiteRank计算,不仅大大降低了单机站点的算法代价,而且克服了单独站点对整个网络覆盖率有限的缺点。附带的一个优点是,常见PageRank 造假难以对SiteRank进行欺骗。

4.1.3、网页块粒度的分析算法

在一个页面中,往往含有多个指向其他页面的链接,这些链接中只有一部分是指向主题相关网页的,或根据网页的链接锚文本表明其具有较高重要性。但是,在PageRank和HITS算法中,没有对这些链接作区分,因此常常给网页分析带来广告等噪声链接的干扰。在网页块级别(Block level) 进行链接分析的算法的基本思想是通过VIPS网页分割算法将网页分为不同的网页块(page block),然后对这些网页块建立page to block和block to page的链接矩阵, 分别记为Z和X。于是,在 page to page图上的网页块级别的PageRank为 W(p)=X×Z; 在block to block图上的BlockRank为 W(b)=Z×X。 已经有人实现了块级别的PageRank和HITS算法,并通过实验证明,效率和准确率都比传统的对应算法要好。

4.2、基于网页内容的网页分析算法

基于网页内容的分析算法指的是利用网页内容(文本、数据等资源)特征进行的网页评价。网页的内容从原来的以超文本为主,发展到后来动态页面(或称 为Hidden Web)数据为主,后者的数据量约为直接可见页面数据(PIW,Publicly Indexable Web)的400~500倍。另一方面,多媒体数据、Web Service等各种网络资源形式也日益丰富。因此,基于网页内容的分析算法也从原来的较为单纯的文本检索方法,发展为涵盖网页数据抽取、机器学习、数据挖掘、语义理解等多种方法的综合应用。本节根据网页数据形式的不同,将基于网页内容的分析算法,归纳以下三类:

1.针对以文本和超链接为主的无结构或结构很简单的网页;
2.针对从结构化的数据源(如RDBMS)动态生成的页面,其数据不能直接批量访问;
3.针对的数据界于第一和第二类数据之间,具有较好的结构,显示遵循一定模式或风格,且可以直接访问。
分布式搜索引擎蜘蛛体系结构设计体系结构研究所属范围

分布式搜索引擎蜘蛛包含多个爬虫,每个爬虫需要完成的任务和单个的爬行器类似,它们从互联网上下载网页,并把网页保存在本地的磁盘,从中抽取URL并沿着这些URL的指向继续爬行。由于并行爬行器需要分割下载任务,可能爬虫会将自己抽取的URL发送给其他爬虫。这些爬虫可能分布在同一个局域网之中,或者分散在不同的地理位置。

根据爬虫的分散程度不同,可以把分布式爬行器分成以下两大类:

1、基于局域网分布式搜索引擎蜘蛛:这种分布式爬行器的所有爬虫在同一个局域网里运行,通过高速的网络连接相互通信。这些爬虫通过同一个网络去访问外部互联网,下载网页,所有的网络负载都集中在他们所在的那个局域网的出口上。由于局域网的带宽较高,爬虫之间的通信的效率能够得到保证;但是网络出口的总带宽上限是固定的,爬虫的数量会受到局域网出口带宽的限制。

2、基于广域网分布式搜索引擎蜘蛛:当并行爬行器的爬虫分别运行在不同地理位置(或网络位置),我们称这种并行爬行器为分布式爬行器。例如,分布式爬行器的爬虫可能位于中国,日本,和美国,分别负责下载这三地的网页;或者位于CHINANET,CERNET,CEINET,分别负责下载这三个网络的中的网页。分布式爬行器的优势在于可以子在一定程度上分散网络流量,减小网络出口的负载。如果爬虫分布在不同的地理位置(或网络位置),需要间隔多长时间进行一次相互通信就成为了一个值得考虑的问题。爬虫之间的通讯带宽可能是有限的,通常需要通过互联网进行通信。

在实际应用中,基于局域网分布式搜索引擎蜘蛛应用的更广一些,而基于广域网的爬虫由于实现复杂,设计和实现成本过高,一般只有实力雄厚和采集任务较重的大公司才会使用这种爬虫。本论文所设计的爬虫就是基于局域网分布式搜索引擎蜘蛛。

分布式搜索引擎蜘蛛整体分析

分布式搜索引擎蜘蛛的整体设计重点应该在于爬虫如何进行通信。目前分布式搜索引擎蜘蛛按通信方式不同分布式网路爬虫可以分为主从模式、自治模式与混合模式三种。

主从模式是指由一台主机作为控制节点负责所有运行搜索引擎蜘蛛的主机进行管理,爬虫只需要从控制节点那里接收任务,并把新生成任务提交给控制节点就可以了,在这个过程中不必与其他爬虫通信,这种方式实现简单利于管理。而控制节点则需要与所有爬虫进行通信,它需要一个地址列表来保存系统中所有爬虫的信息。当系统中的爬虫数量发生变化时,协调者需要更新地址列表里的数据,这一过程对于系统中的爬虫是透明的。但是随着爬虫网页数量的增加。控制节点会成为整个系统的瓶颈而导致整个分布式搜索引擎蜘蛛系统性能下降。主从模式的整体结构图:

主从模式的整体结构图

自治模式是指系统中没有协调者,所有的爬虫都必须相互通信,比主从模式下爬虫要复杂一些。自治模式的通信方式可以使用全连接通信或环形通信。全连接通信是指所用爬虫都可以相互发送信息,使用这种方式的每个搜索引擎蜘蛛会维护一个地址列表,表中存储着整个系统中所有爬虫的位置,每次通信时可以直接把数据发送给需要此数据的爬虫。当系统中的爬虫数量发生变化时,每个爬虫的地址列表都需要进行更新。环形通信是指爬虫在逻辑上构成一个环形网,数据在环上按顺时针或逆时针单向传输,每个爬虫的地址列表中只保存其前驱和后继的信息。爬虫接收到数据之后判断数据是否是发送给自己的,如果数据不是发送给自己的,就把数据转发给后继;如果数据是发送给自己的,就不再发送。假设整个系统中有n个爬虫,当系统中的爬虫数量发生变化时,系统中只有n-1个爬虫的地址列表需要进行更新。

自治模式的结构图

混合模式是结合上面两种模式的特点的一种折中模式。该模式所有的爬虫都可以相互通信同时都具有任务分配功能。不过所有爬虫中有个特殊的爬虫,该爬虫主要功能对已经经过爬虫任务分配后无法分配的任务进行集中分配。使用这个方式的每个搜索引擎蜘蛛只需维护自己采集范围的地址列表。而特殊爬虫需除了保存自己采集范围的地址列表外还保存需要进行集中分配的地址列表。混合模式的整体结构图:

混合模式的整体结构图

大型分布式搜索引擎蜘蛛体系结构图

大型分布式搜索引擎蜘蛛体系结构图

从这些图可以看出,分布式搜索引擎蜘蛛是一项十分复杂系统。需要考虑很多方面因素。性能可以说是它这重要的指标。当然硬件层面的资源也是必须的。不过不在本系列考虑范围。
 

相关推荐

网友评论

共有0条评论

您的评论需要经过审核才能显示!

热门评论

热门排行

图文信息

相关专题

最新信息