首页 > 理工 > 计算机

基于广度优先搜索的网络蜘蛛设计

【关键词:计算机网络】 
【摘要】  网络蜘蛛搜索策略的研究是近年来专业搜索引擎研究的焦点之一,如何使搜索引擎快速准确地从庞大的网页数据中获取所需资源的需求是目前所面临的重要问题。本文重点阐述了搜索引擎的 Web Spider (网络蜘蛛)的搜索策略和搜索优化措施,  提出了一种简单的基于广度优先算法的网络蜘蛛设计方案,并分析了设计过程中的优化措施。

【关键词】 搜索引擎;  网络蜘蛛;  搜索策略

0 引言

近年来,随着 Internet 技术的广泛应用,传统的 通用搜索引擎,如 Google、Fast、Alta Vista 和 GoTo 等正面临巨大的挑战。挑战之一是 Web 信息资源呈 指数级增长,搜索引擎无法索引所有页面。据统计, 目前 Web 上静态页面的数量超过 40 亿个,而且这 一数量还在以平均每天 730 万个页面的速度递增。 在过去的几年中,尽管各种通用搜索引擎在索引技 术、索引数量上有所提高,但远远无法跟上 Web  本 身的增长速度,即使是目前全球最大的搜索引擎 Google,其索引的页面数量仅占 Web 总量的 40%; 挑战之二是 Web 信息资源的动态变化,搜索引擎无 法保证对信息的及时更新。近年来的研究表明,Web 上的页面平均 50  天就有约 50%的页面发生变化, 而目前通用搜索引擎更新的时间至少需要数星期之 久;挑战之三是传统的搜索引擎提供的信息检索服务,不能满足人们日益增长的对个性化服务的需要。因此如何设计网络蜘蛛(Web  Spider)来更有效率的爬 取互联网上的内容成为搜索引擎的一个首要问题。 在设计网络蜘蛛时,不仅需要充分考虑到爬取的效率和站点设置的灵活性还要确保系统的稳定性。一 个优秀的搜索引擎,  需要不断的优化网络蜘蛛的算 法,  提升其性能。本文在分析网络蜘蛛的工作原理 的基础上,  提出了一种基于广度优先搜索算法的网 络蜘蛛的实现,并对提高网络蜘蛛搜索效率的相关看法。

由于不可能抓取所有的网页,有些网络蜘蛛对一些不太重要的网站,设置了访问的层数。[2]例如, 在上图中,A 为起始网页,属于 0 层,B、C、D、 E、F 属于第 1 层,G、H 属于第 2 层,I 属于第 3 层。如果网络蜘蛛设置的访问层数为 2 的话,网页I  是不会被访问到的。这也让有些网站上一部分网 页能够在搜索引擎上搜索到,另外一部分不能被搜索到。 对于网站设计者来说,扁平化的网站结构设计有助于搜索引擎抓取其更多的网页。 网络蜘蛛在访问网站网页的时候,经常会遇到加密数据和网页权限的问题,有些网页是需要会员 权限才能访问。当然,网站的所有者可以通过协议 让网络蜘蛛不去抓取(下小节会介绍),但对于一些出售报告的网站,他们希望搜索引擎能搜索到他 们的报告,但又不能完全免费的让搜索者查看,这样就需要给网络蜘蛛提供相应的用户名和密码。网 络蜘蛛可以通过所给的权限对这些网页进行网页抓取,从而提供搜索。而当搜索者点击查看该网页的 时候,同样需要搜索者提供相应的权限验证。

2 网络蜘蛛的设计

根据抓取过程,蜘蛛主要分为三个功能模块, 一个是网页读取模块主要是用来读取远程 Web  服 务器上的网页内容,另一个是超链分析模块,这个 模块主要是分析网页中的超链接,将网页上的所有 超链接提取出来,放入到待抓取 URL 列表中,再一 个模块就是内容分析模块,这个模块主要是对网页 内容进行分析,将网页中所有超标志去掉只留下网 页文字内容。蜘蛛的主要工作流程如图所示。

首先蜘蛛读取抓取站点的 URL 列表,取出一个 站点 URL,将其放入未访问的 URL 列表(UVURL 列表)中,如果 UVURL 不为空刚从中取出一个 URL 判断是否已经访问过,若没有访问过则读取此网页, 并进行超链分析及内容分析,并将些页存入文档数 据库,并将些 URL 放入已访问 URL 列表(VURL 列表),直到 UVRL 为空为止,此时再抓取其他站 点,依次循环直到所有的站点 URL 列表都抓取完为 止。

为了提高网络蜘蛛的抓取效率,需要引入以下 技术。

(1)、 多线程技术:由于抓取的站点 URL 相当多,采用单线程蜘蛛抓取时速度不够,也不能满足实 际的需要。因而需要多线程技术来创建多个蜘蛛线程来同时抓取,以提高速度。

(2)、 网页抓取:网页抓取是基于 HTTP 协议之上的, 网页上的资源有多种,有网页,有 Word 文档也 有其他类型的文件,这样抓取时需要判断 URL 所指向资源的类型。

(3)、 超链分析:超链分析是一个比较重要的环节,需要对 HTML 的各种标志(tag)有一个很全面 的了解。需要反复测试,考虑各种情形的发生。

超链分析时从网页里提取出来的是相对于当前 页的相对 URL,因而需要根据当前页的绝对 URL 将提取的这个 URL 转换成绝对 URL。在 此过程中需要根据 ParentURL(就是当前页的 URL)作出各种判断。

3 改进方法

商业化的蜘蛛需要抓取上亿的网页,因而抓取 速度是一个关键,另外蜘蛛需要自动运行,尽是减 少人工的参与,因而系统的性能也是一个很重要的 关键,系统能够在发生异常的时候自动进行处理, 防止程序的退出和死机。[3]有一些细节需要注意:

系统应该使用多线程,使用多个蜘蛛同时抓取,在可能的情况下,最好是做成 分布式的蜘蛛程序,蜘蛛应该分布地网 络上多台服务器上协同抓取网页,这样 速度会更快,更符合我们的实际应用。

对于同一网站的网页应该采用同一个 HttpConnection 这样有效地节省创建一 个连接的时间,另外对于抓取的 URL 采用域名缓冲机制(可在网关一级上实 现),这样抓取时减少由域名到 IP  地 址的转换时间以及重复的域名转换。若 能做到这一步将会大大减少抓取时间, 因为访问一 URL 时每次都要进行域名 到主机 IP 地址的转换。

最好是能够将读取网页、超链分析及网 页内容分析三部分分开来做,让它们并 行协同工作,这样效率会更高。因为在这三个过程中网页读取比起其他两个 功能来说是一个长任务,最耗时间。当抓取完一网页后,在抓取下一网页的时候让去执行超链分析和内容分析。这样 在下一网页抓取完成之前超链分析和 内容分析任务就能完成,抓取任务不会 延迟,这样节省了一些时间。

4     结束语

随着人们对“个性化”信息服务需要的日益增 长,专业搜索引擎的发展将成为搜索引擎发展的主 要趋势之一。[4]网络蜘蛛搜索策略问题的研究,对 专业搜索引擎的应用与发展具有重要意义。本文对 现有的网络蜘蛛搜索策略进行了简单的介绍和分 析,提出了一种基于广度优先搜索网络蜘蛛设计方 案。提出了提高网络蜘蛛效率的几种方法。目前的 网络蜘蛛通常采用“固定的”搜索策略,缺乏适应性,如何提高网络蜘蛛的自适应性有待进一步研究。 总之,网络蜘蛛搜索策略问题的研究还处于发展阶 段,无论是模型、搜索算法,还是实验方法都还有

许多有待解决的问题。
更多 >>
热门分类
推荐文章