英语原文共 8 页

PyBot:一种网络爬虫算法

摘要：

PyBot是Python开发的Web爬虫程序，使用广度优先搜索(BFS)来爬虫Web。万维网(WWW)建立在开放的互联网上，它的成功改变了人类分享和交换信息和思想的方式。随着动态Web的爆炸式增长，用户不得不花费大量时间从Web检索一小部分信息。搜索引擎的诞生使人类的生活变得更容易，因为它只是把人们带到他们想要的资源。网络爬虫是搜索引擎用来从万维网自动检索信息的程序。

关键词minus;爬行者;机器人;蜘蛛;机器人协议;爬行者协议

一、介绍

网络爬虫是一种以收集数据为目的，系统地遍历万维网的计算机程序。这些机器人并不像病毒或智能代理那样，在互联网上移动到不同的计算机上。每个机器人同时打开许多连接。这对于以足够快的速度检索web页面是必要的。机器人驻留在一台机器上，并向Internet上的其他机器发送对文档的HTTP请求，就像web浏览器在用户单击链接时所做的那样。所有Web爬虫程序真正做的是自动化以下链接的过程。大多数Web爬虫都采用广度优先的检索策略来增加Web的覆盖率。我们的PyBot爬行器也使用宽度优先的检索策略。

搜索引擎的主要目标是在快速扩展的Web上以更快的速度提供更相关的结果。标准搜索引擎有三个重要的顺序任务，如图1所示。他们是爬行、索引、搜索。

其中，爬行是最重要的一种。Web爬虫用于许多目的。爬虫程序的主要目的是下载用于索引的Web页面，以及其他目的，如页面验证、结构分析、可视化、更新通知、镜像，以及用于垃圾邮件目的，如获取电子邮件地址等。

索引模块提供关于页面返回给爬虫程序的排名信息，以便爬虫程序可以首先收集重要的页面，如图1所示。网络爬虫有很多名字，比如蜘蛛、机器人、机器人和蚂蚁。

爬虫程序的主要目的是为搜索引擎访问Web中的页面并以系统的方式下载它们。爬虫程序从通用资源定位器(URL)开始，探索该页面中的所有超链接，访问这些页面和页面。这些下载的页面被索引并存储在搜索引擎中。一个搜索引擎将根据它的搜索性能、搜索结果的质量以及有效地抓取和索引Web的能力来进行评级。这就是为什么搜索引擎正在做大量的研究来做一个更好的网络爬虫。

Web爬虫程序是为做各种工作而开发的。以下工作是由爬虫完成的重要工作。它们是:

1.下载网页。

2.解析下载的页面并检索所有超链接

3.对于检索到的每个链接，重复该过程。

爬虫程序可以用于在internet或intranet上爬行整个站点，它对我们的PyBot很有效。一些爬虫程序使用并行下载来减少时间。一旦指定了URL，爬虫程序将跟踪在该页面中找到的所有链接，并转到所有链接并下载页面。它将继续执行，直到所有链接都被探测或爬虫想要停止。爬虫程序将Web站点视为树结构，如图2所示。这里的开始URL是树的根，根的子节点是它们的链接。有些子节点可能没有根节点的子节点2这样的链接，它们被称为悬浮子节点。

开发和运行Web爬虫是一项具有挑战性的任务，因为它涉及性能、可靠性和社会问题[1]。性能问题与Web爬虫发现Web的速度有关，可靠性问题与爬虫如何在爬虫过程中与各种Web服务器和名称服务器进行交互有关。社会问题涉及爬虫如何尊重网站的政策，如不访问某些页面等。还有其他一些因素也会影响爬虫程序的性能，比如网站策略、internet的爆炸式增长、更改速度、动态页面的增长和存储需求。

本文组织如下。下一节将展示关于爬行器的先前工作。第三节给出了我们提出的爬虫算法。第四节给出了本文方法的实验结果。第五部分是本文的结束语，并对今后的工作进行了展望。

二、准备工作

Web爬虫程序使用了一些爬行技术，这里突出了一些重要的技术，它们是:通用爬行:通用Web爬虫程序从一组特定URL及其链接收集尽可能多的页面。在这种情况下，爬虫能够从不同的位置获取大量的页面。一般用途的爬行会降低速度和网络带宽，因为它正在抓取所有页面。有重点的爬行:有重点的爬行器旨在只收集特定主题的文档，从而减少网络流量和下载量。集中的爬虫程序的目标是有选择地查找与预定义主题集相关的页面。它只抓取web的相关区域，从而大大节省了硬件和网络资源。重点抓取的最关键的评估是度量比率，比率是获取相关页面和从抓取中有效过滤不相关页面的速率。这个收获率必须很高，否则专注的爬虫只会花费大量的时间来消除无关的页面，使用普通的爬虫而不是[3]可能会更好。分布式爬行:在分布式爬行中，使用多个进程从Web上爬行和下载页面，从而构建一个可伸缩的、易于配置的系统，即容错系统。分载降低了硬件需求，同时提高了整体下载速度和可靠性。

A.机器人排除标准

在Web爬行世界中，Web爬行器应该遵循一些规则，这些规则被称为Robot policy或Robots Exclusion Protocol，甚至Robots .txt协议。这是一个防止合作的网络爬虫访问网站的全部或部分的约定。以下是机器人在网上爬行时必须遵循的一些策略:

1.所有机器人之前都必须访问Robots .txt文件下载任何文件。

2.机器人必须向Web服务器声明其身份。

3.机器人必须最小化Web服务器的负担使用较低的检索率和访问Web服务器仅当服务器被轻微加载时。

网站所有者可以通过在网站层次结构的根目录中放置文本call robots.txt(例如www.curtin.edu.my/robots.txt)来给web爬虫程序提供指令。这个文本文件应该包含特定格式的指令。网站上的robots.txt文件的功能是请求指定的机器人在搜索时忽略指定的文件或目录。设计不良的机器人会导致严重的网络和服务器过载问题，这就是为什么所有机器人都必须遵循机器人策略的原因。此外，不遵守机器人政策的机器人可能会被列入黑名单或被网站禁止。

B.搜索引擎的类型

有5种主要类型的搜索引擎。它们是:

1)基于爬虫的搜索引擎:基于爬虫的搜索引擎使用一种名为Spider或robot或Crawler或bot的自动化程序来抓取网页，下载并创建索引并存储在数据库中。当用户执行搜索时，搜索引擎将检查其web页面数据库中用户搜索的关键字，以显示链接结果列表。它们包含链接到的web页面的全文。基于蜘蛛的搜索引擎不断地在互联网上搜索，用新的或修改过的页面更新他们的信息数据库。谷歌和Yahoo!搜索的搜索引擎。

2)基于目录的搜索引擎:基于目录的搜索引擎使用人工编辑器编辑页面所属的类别，并将页面放在“目录”数据库中的该类别中。例子是雅虎目录搜索引擎。

3)元搜索引擎:元搜索引擎(也称为多线程引擎)一次搜索多个主要引擎。元搜索引擎不抓取Web或维护Web页面的数据库。相反，它们充当中间代理，将查询传递给主要引擎，然后返回结果。例如Dogpile和Vivisimo搜索引擎。

4)混合搜索引擎:混合搜索引擎结合了基于爬虫的结果和基于人的目录结果。例如，MSN搜索更有可能显示LookSmart上的人力清单。然而，它也提供了Inktomi提供的基于爬虫的结果。

5)基于概念的搜索引擎:基于概念的搜索系统试图确定你的意思，而不仅仅是你说了什么。在最好的情况下，基于概念的搜索返回与所探索的主题相关的文档，即使文档中的单词与您输入查询的单词不完全匹配。例如Excite、Essie(用于结构化医学文本)、Compass(用于HTML、深度web数据)。

一个标准的Web搜索引擎架构如图3所示。标准的搜索引擎架构包括三个主要部分——web爬行、索引和查询。查询是在这三个主要组件首先完成之后执行的。首先是一堆机器，它们扮演着爬虫或蜘蛛的角色，有时也被称为机器人，它们被编程来爬网。他们出去，在整个Web上发出HTTP请求，试图收集Web页面。之后，他们将Web页面存储在数据库中。检查重复的Web页面，不将其存储在数据库中。爬行器完成爬行之后，索引器为收集的数据创建一个反向索引表。然后，反向索引被发送到搜索引擎服务器，等待处理查询。因此，用户可以访问搜索引擎网站，向搜索引擎服务器提交查询，搜索引擎服务器可以立即将结果发送回用户。

C.网络爬虫的政策

Web爬虫程序的结果通常基于它们如何遵循以下四种策略进行评估。它们是:

1)选择策略:选择策略是考虑到Web上的海量数据，为了提高效率，需要先下载重要页面。根据Lawrence和Giles[4]的说法，没有一个搜索引擎能覆盖超过16%的Web内容。Gulli et al.[5]最近的一项研究表明，大型搜索引擎的索引不超过可索引Web的40%-70%。Web爬虫程序非常希望下载最相关的页面，而不仅仅是Web的随机样本。一个页面的重要性取决于它的内在质量，它在链接或访问方面的受欢迎程度，甚至它的URL。在爬行到实际Web之后，需要修改选择策略，以提高检索到的页面的质量。Cho等人在Stanford.edu域中首次研究了爬虫调度策略，其策略包括宽度优先、反向链接计数和部分Pagerank。Najork和Wiener[7]使用宽度优先顺序，对3.28亿页进行了实际的爬行。Abiteboul et al.[8]和Boldi et al.[9]对不同策略下的选择策略进行了研究和仿真，结果表明宽度优先策略效果更好。Chakrabarti等人引入了聚焦爬行。H.T. Lee等人研究了使用单个服务器爬行到60亿页的规模，并比较了他们的结果。

2)重访问策略:大多数网站本质上是动态的，抓取Web需要很长时间，通常需要几周或几个月。当Web爬虫完成它的爬虫时，许多事情可能已经发生了，比如新内容可能已经添加，内容可能已经更新，一些内容可能已经删除了[12]。从搜索引擎的角度来看，不检测事件是有成本的，因此有一个过时的资源副本。根据J. Cho等人的研究，最常用的成本函数是新鲜度和年龄。

3)礼貌原则:根据M. Koster[15]的说法，网络爬虫在很多任务中都是有用的，但这是有代价的。使用Web爬虫程序的成本包括网络资源、服务器过载、编写糟糕的机器人，以及干扰网络和服务器的个人机器人。

Cho等人建议在他们的研究中间隔10秒。来自访问日志的轶事证据表明，来自已知爬虫的访问间隔在20秒到3-4分钟之间。

4)并行化策略:为了提高网络爬虫的性能，特别是在像万维网这样的大型数据存储库上的爬虫，往往会采用类似爬虫的并行计算等技术。Web爬虫可以是一个代理，通过执行多个代理，通过代理之间的交互，可以更快、更有效地爬行Web。另一种方法是有一个爬行系统，它为爬行器分配URL，这样它们就不会爬行相同的URL。

D.现有的web爬虫

有很多关于网络爬虫的工作和研究。Web爬虫程序是为研究和商业目的而开发的。WebBase[2]是斯坦福大学为研究目的开发的爬虫程序之一。WebBase是斯坦福大学原始谷歌存储库和搜索引擎的延续。以下是通用爬虫程序列表:

1. yahoo !是雅虎搜索引擎的

2. Msnbot:这是微软Bing网络爬虫的名字。

3.Googlebot[1]:谷歌使用的爬虫程序，它从web上收集文档，为谷歌搜索引擎构建可搜索的索引。

4.Methabot:是一个用C编写的可脚本的web爬虫程序，在ISC许可下发布。

5.PolyBot[17]:它是一个用c 和Python编写的分布式爬虫程序，由一个“爬虫管理器”、一个或多个“下载器”和一个或多个“DNS解析器”组成。

6.快速爬虫[18]:是一种分布式爬虫，用于快速搜索和传输，其架构的一般描述是可用的。

7.RBSE[19]:它是第一个发布的网络爬虫。它基于两个程序:第一个程序“spider”在关系数据库中维护一个队列，第二个程序“mite”是从Web上下载页面的经过修改的wwwASCII浏览器。

8.WebCrawler[20]:它用于构建Web子集的第一个公开可用的全文索引。它基于lib-WWW来下载页面，并使用另一个程序来解析和排列url，以便对Web图进行宽度优先的探索。它还包括一个实时爬虫，根据锚文本与提供的查询的相似性跟踪链接。

9. 万维网蠕虫[21]:它是一个爬虫，用于构建文档标题和url的简单索引。可以使用grep Unix命令搜索索引。

10. WebFountain[22]:它是一个分布式的、模块化的爬虫程序，类似于Mercator，但是是用c 编写的。

11.webrac[23]:它是一个用Java实现的爬行和缓存模块，是一个更通用的系统eRACE的一部分。

清单上还有一些流行的开源爬虫程序，如Aspseek、crawler4j、GRUB、WIRE[24]等等。

三、 算法

PyBot是用Python 2.7编写的一个简单的Web爬虫程序。首先它获取一个URL，然后从这个URL获取所有的超链接。从超链接开始，它再次爬行，直到没有发现新的超链接为止。它在爬行时下载所有Web页面。PyBot将在其抓取的网站上以Excel CSV格式输出Web结构。下载的页面和Excel CSV格式的Web结构都存储在存储中，用于PyRanking/JyRanking以及分析和索引器。PyRanking和JyRanking是该方法使用的排名系统。排名系统采用Excel CSV格式的Web结构，应用PageRank算法，通过在页面顶部显示最受欢迎的页面列表，生成页面的排名顺序。

在我们提出的方法中，由于资源的限制，分析和索引以及查询搜索模块没有得到实现。

我们使用标准的和最流行的BFS搜索算法来爬行Web。BFS使用的策略是先扩展根节点，然后扩展根节点的所

资料编号：[4688]