基于 Heritrix 网络爬虫算法的研究与应用

eulogian

贡献于2011-10-29

字数:0 关键词: 网络爬虫

http://www.paper.edu.cn - 1 - 中国科技论文在线 基于 Heritrix 网络爬虫算法的研究与应用 范先爽,刘东飞* 作者简介:范先爽(1985-),男,硕士在读,计算机网络 . E-mail: fanxs1124@163.com (武汉理工大学计算机科学与技术学院,武汉 430070) 摘要:本文首先对搜索引擎中的网络爬虫进行了介绍,详细分析了开源网络爬虫 Heritrix 的 系统结构。 在此基础上, 提出了设计特定的解析器, 解析特定网站网页实现定制抓取的目的。 然后通过消除 robots.txt 文件对个别处理器的影响,以及引入 ELFHash 算法实现了高效、多 线程抓取 Web 资源的目的。最后通过对改进前后的爬虫抓取网页的速度对比,以及在同等 时间的情况下抓取网页个数分析,验证了改进后的爬虫性能有了较明显的提高。 关键词: 计算机应用;网络爬虫; Heritrix;ELFHash 算法 中图分类号:TP31 Study And Application Of Web Crawler Algorithm Based On Heritrix FAN Xianshuang, LIU Dongfei (School of Computer Science and Technology,Wuhan University of Technology,Wuhan 430070) Abstract: In this paper,the web crawler in search engine was firstly introduced,based on the detailed analysis of the system architecture about open source web crawler Heritrix,Proposed design of a particular parser,parsed the particular web site to achieve the purpose of particular crawl.Then by eliminating the impact on individual processors caused by robots.txt file,and introduced the ELFHash algorithm implements the purpose of efficient, multi-thread access to the web crawler resources.Finally,by the comparison of the speed of crawl web page between before-improved and after-improved,and the analysis of the number of crawled pages in the same long time,verify the performance of the after-improved web crawler has been more obvious increased. Key words: computer application; web crawler; Heritrix; ELFHash algorithm 0 引言 互联网是一个宝库,搜索引擎是打开宝库的一把钥匙。使用搜索引擎,使我们检索信息 的能力获得了空前的提高,成本有效地降低,可以说,搜索引擎是现代的计算机技术、因特 网技术与传统的索引理论相结合的成功典范。随着网络覆盖范围的不断扩大,Web 信息爆 炸性的增长,互联网已经成为一个巨大的海量信息空间。搜索引擎为人们在具有海量信息的 互联网上查找信息资源提供了方便。但是,随着信息多元化的发生和用户对搜索引擎提出的 个性需求,面向所有用户的通用搜索引擎己经不能满足特定用户的更深入、快速、及时的查 询需求。网络爬虫的搜索和抓取效率一直在人们研究的一个主要方向,网络爬虫是搜索引擎 的基础。无论多么强大的搜索引擎工具,在其后台,都需要有高效的网络爬虫来支援它。网 络爬虫,又被称为蜘蛛 Spider,或是网络机器人、 BOT 等,这些都无关紧要,最重要的是: 由于爬虫的存在,才使得搜索引擎有了丰富的资源。 Heritrix 是一个纯由 Java 开发的、开源 的 Web 网络爬虫,用户可以使用它从网络上抓取想要的资源。它来自于 www.archive.org。 Heritrix 最出色之处在于它的可扩展性,开发者可以扩展它的各个组件,来实现自己的抓取 逻辑。 http://www.paper.edu.cn - 2 - 中国科技论文在线 1 搜索引擎工作原理 1.1 搜索引擎简介 搜索引擎一般由网络蜘蛛程序、索引数据库和用户查询接口三部分组成 [1]。搜索引擎的 自动信息搜集功能分两种。一种是定期搜索,即每隔一段时间(比如 Google 一般是 28 天), 搜索引擎主动派出 “蜘蛛”程序,对一定 IP 地址范围内的互联网站进行检索,一旦发现新的 网站,它会自动提取网站的信息和网址加入自己的数据库。 另一种是提交网站搜索,即网 站拥有者主动向搜索引擎提交网址,它在一定时间内( 2 天到数月不等)定向向你的网站派 出“蜘蛛”程序,扫描你的网站并将有关信息存入数据库,以备用户查询。由于近年来搜索引 擎索引规则发生了很大变化,主动提交网址并不保证你的网站能进入搜索引擎数据库,因此 目前最好的办法是多获得一些外部链接, 让搜索引擎有更多机会找到你并自动将你的网站收 录。 当用户以关键词查找信息时,搜索引擎会在数据库中进行搜寻,如果找到与用户要求内 容相符的网站,便采用特殊的算法 ——通常根据网页中关键词的匹配程度,出现的位置 /频 次,链接质量等 ——计算出各网页的相关度及排名等级,然后根据关联度高低,按顺序将这 些网页链接返回给用户。 1.2 网络爬虫 网络爬虫(又被称为网页蜘蛛,网络机器人),是一种按照一定的规则,自动的抓取 万维网信息的程序或者脚本 [2]。另外一些不常使用的名字还有蚂蚁,自动索引,模拟程序或 者蠕虫。网页的抓取策略可以分为深度优先、广度优先和最佳优先三种。深度优先在很多情 况下会导致爬虫的陷入 (trapped)问题,一般情况下广度优先和深度优先方法如图 1 所示: 图 1 广度优先和深度优先方法图 Fig.1 Breadth-first and depth-first approach 广度优先搜索策略是指在抓取过程中,在完成当前层次的搜索后,才进行下一层次的搜 索。该算法的设计和实现相对简单。在目前为覆盖尽可能多的网页,一般使用广度优先搜索 方法。 也有很多研究将广度优先搜索策略应用于聚焦爬虫中。 其基本思想是认为与初始 URL 在一定链接距离内的网页具有主题相关性的概率很大。 另外一种方法是将广度优先搜索与网 页过滤技术结合使用,先用广度优先策略抓取网页,再将其中无关的网页过滤掉。这些方法 的缺点在于,随着抓取网页的增多,大量的无关网页将被下载并过滤,算法的效率将变低。 最佳优先搜索策略按照一定的网页分析算法,预测候选 URL 与目标网页的相似度,或 与主题的相关性,并选取评价最好的一个或几个 URL 进行抓取。它只访问经过网页分析算 http://www.paper.edu.cn - 3 - 中国科技论文在线 法预测为 “有用”的网页。存在的一个问题是, 在爬虫抓取路径上的很多相关网页可能被忽略, 因为最佳优先策略是一种局部最优搜索算法。因此需要将最佳优先结合具体的应用进行改 进,以跳出局部最优点。将在第 4 节中结合网页分析算法作具体的讨论。研究表明 [3],这样 的闭环调整可以将无关网页数量降低 30%~90%。 2 Heritrix 系统架构 2.1 Heritrix 项目简介 开源网络爬虫 Heritrix 是由互联网档案馆和北欧国家图书馆联合规范化编写于 2003 年 初。第一次正式发布是在 2004 年 1 月,并不断的被互联网档案馆和其他感兴趣的第三方改 进着。Heritrix 是一个由 java 开发的,开源的 web 网络爬虫,用户可以使用它从网络上抓取 想要的资源。 Heritrix 最大的特色在于它的可扩展性,开发者可以扩展它的各个组件,实现 自己的抓取逻辑 [4]。目前已发展到 1.14.4 版本,本文使用的是 1.14.4 版本。 2.2 Heritrix 系统介绍 Heritrix 的工作流程是不断循环的,具体流程是 [5]: (1) 在线程池中,选择一个预定的 URL 中 (2) 从选择的 URL 网址下载远程文件 (3) 分析,归档下载到的内容,写入磁盘镜像目录 (4) 从分析到的内容里面根据策略选择 URL,加入预定队列 (5) 标记已经处理过的 URL (6) 从第 1 步继续进行,直到所有的 URL 处理结束,抓取工作结束 Heritrix 的系统架构图如图 2 所示: 图 2 Heritrix 系统结构 Fig.2 Heritrix System structure 从图 2 可以看出, Heritrix 总体上是一个平台结构,内部的组件都具有松耦合的特点。 任何一个部分都可以进行拆卸并替换,这就给我们进行基于 Heritrix 的自定义开发提供了条 件。 下面简单介绍一下各个组件的作用: 1. CrawlController CrawlController(中央控制器 )是抓取任务的核心组件,它控制着整个抓取的流程。 2. CrawlOrder CrawlOrder(抓取任务)是整个抓取工作的起点,它记录了任务的所有属性,即在创建任务时 http://www.paper.edu.cn - 4 - 中国科技论文在线 的一系列设置。 3. Frontier Frontier(链接制造工厂 )负责所有链接的处理。将已经爬过的 URI 做标记,并将未处理的链 接放入待处理队列。 4. ToeThread ToeThread(处理线程)Heritrix 是多线程的,每个 URL 被一个线程处理,这个线程就叫做 ToeThread,每个线程都会包括一条处理链。 5. Processor Processor(处理器 )代表着单个的处理器,所有的处理器都是它的子类。它包括以下几种: 2.3 Heritrix 抓取策略分析 Heritrix 是使用 Berkeley DB 来构建一个链接队列。这些队列被置放于 BdbMultipleWorkQueues 中时,总是先给予一个 Key,然后将那些 Key 值相同的链接放在一 起,成为一个队列,也就是一个 Queue。但是,这个 Key 值到底该如何计算呢?事实上,这 里也说的 Key 值,应该是做为一种标识符的形式存在。也就是说,它要与 URL 之间有一种 内在的联系。 在 Heritrix 中,为每个队列赋上值的策略, 也就是它的 queue-assignment-policy。 在默认的情况下, Heritrix 使用 HostnameQueueAssignmentPolicy 来解决 Key 值生成的问题。 这种策略其实是以链接的 Host 名称为 Key 值来解决这个问题的。也就是说,相同 Host 名称 的所有 URL 都会被置放于同一个队列中间。这种方式在很大程度上可以解决广域网中信息 抓取时队列的键值问题。但是,它对于某个单独网站的网页抓取,就出现了很大的问题。以 Sina 的新闻网页为例,其中大部分的 URL 都来自于 Sina 网站的内部,因此,如果使用了 HostnameQueueAssignmentPolicy,则会造成有一个队列的长度非常长的情况。 在 Heritrix 中, 一个线程从一个队列中取 URL 链接时,总是会先从队列的头部取出第一个链接,在这之后, 这个被取出链接的队列会进入阻塞状态,直到待该链接处理完,它才会从阻塞状态中恢复。 假如使用 HostnameQueueAssignmentPolicy 策略来应对抓取一个网站中内容的情况,很有可 能造成仅有一个线程在工作,而其他所有线程都在等待。这是因为那个装有绝大多数 URL 链接的队列几乎会永远处于阻塞状态,因此,别的线程根本获取不到其中的 URI,在这种 情 况下,抓取工作会进入一种类似于休眠的状态。因此,需要改变 queue-assignment-policy 来 避免发生这种情况。 3 改进 Heritrix 的抓取策略 3.1 定制合适的 Key 值散列算法 被改变的 Key 值的生成方式,应该具有什么样的要求呢?从上面的分析中可以知道, 这个 Key 值最重要的一点就是应该能够有效的将所有的 URL 散列到不同的队列中,最终能 使所有的队列的长度的方差较小,在这种情况下,才能保证工作线程的最大效率。任何扩展 queue-assignment-policy 的默认实现的类,均继承自 QueueAssignmentPolicy 并覆写了其 getClassKey()方法,getClassKey 方法的参数为一个链接对象,而我们的散列算法,正是要根 据这个链接对象来返回一个值。比如使用字符串的长度等, URL 散列算法,最为出名的是 ELFHash 算法[6], ELFhash 函数是对字符串的散列。它对于长字符串和短字符串都很有效, 字符串中每个字符都有同样的作用,它巧妙地对字符的 ASCII 编码值进行计算, ELFhash 函数对于能够比较均匀地把字符串分布在散列表中。这里给出 MyQueueAssignmentPolicy http://www.paper.edu.cn - 5 - 中国科技论文在线 类,它通过 ELFHash 算法实现 Key 值分配。 public class MyQueueAssignmentPolicy extends QueueAssignmentPolicy { @Override //重写 getClassKey()方法 public String getClassKey(CrawlController controller, CandidateURI cauri) { String uri = cauri.getURI().toString(); long hash = ELFHash(uri);//利用 ELFHash 算法为 uri 分配 Key 值 String a = Long.toString(hash % 50);//取模 50,对应 50 个线程 return a; } public long ELFHash(String str) { long hash = 0; long x = 0; for(int i = 0; i < str.length(); i++) { hash = (hash << 4) + str.charAt(i);//将字符中的每个元素依次按前四位与上 if((x = hash & 0xF0000000L) != 0)//个元素的低四位想与 { hash ^= (x >> 24);//长整的高四位大于零,折回再与长整后四位异或 hash &= ~x; } } return (hash & 0x7FFFFFFF); } } 3.2 实验数据分析 如果使用 Heritrix 默认的 key 值分配,那么当对某一个域名下的所有网页进行抓取的时 候效率会很低。下面是对新浪新闻主页上的网页进行抓取的实验结果。其中图 3 是改进之前 的结果图,图 4 是改进后的结果图。 图 3 改进之前结果图 Fig.3 Results before improved http://www.paper.edu.cn - 6 - 中国科技论文在线 图 4 改进后结果图 Fig.4 Results after improved 图中绿红相间长条是抓取状态栏,其中绿色的显示当前已经被抓取的链接数量,红色 表示还在队列中等待被抓取的链接。在绿红相间的长条左侧,是几个实时的运行状态, 其中包括抓取的平均速度(KB/s)和每秒钟抓取的链接数(URIs/sec),另外的统 计还包括抓取任务所消耗的时间和剩余的时间,不过这种剩余时间一般都不准, 因为 URI 的数量总是在不断变化,每当分析一个网页,就会有新的 URI 加入队 列中。 从上面的两幅结果图可以看出,加入 Key 值散列算法后的 Heritrix 在抓取速度上有明显 的提高。 最后分别对四大门户网站(新浪,搜狐,网易,腾讯)的新闻网页进行上述实验,得出下 面的实验数据对比表 1: 表 1 结果对比表 Tab.1 The Results Comparison 种子 URL 抓取时间 改进前的抓 取总数 改进后的抓 取总数 改进前抓取 数(/秒) 改进后抓取 数(/秒) http://news.sina.com.cn 5 分钟 1455 5183 4.85 17.27 http://news.sohu.com 5 分钟 1099 3506 3.66 11.69 http://news.163.com 5 分钟 978 2370 3.26 7.90 http://news.qq.com 5 分钟 1325 2049 4.42 6.83 表中的实验数据都是在消除了 robots.txt 文件的影响下进行的。从表中可以看出利用 ELFHash 算法合理的分配 Key 值后对一个域名下的网页抓取速度有了显著的提高,对新浪 新闻网页抓取速度提高了 4 倍左右,其他 3 个门户网站的新闻网页抓取速度也有了不同程度 的提高。 4 结论 开源的爬虫框架 Heritrix 为我们提供了良好的可扩展性,开发者可以扩展它的各个组件 来达到个性化的抓取逻辑。它的抓取策略默认是根据域名来分配 Key 值,但是这个 Key 值 不能有效的将所有的 URL 散列到不同的队列中,这样就不能形成多线程抓取的目的,效率 比较低下,本文引入 ELFHash 散列函数后能高效将同一域名下的 URL 散列到不同的队列中, 从而形成了多线程高效的抓取策略。 http://www.paper.edu.cn - 7 - 中国科技论文在线 [参考文献] (References) [1] 李晓明,闫宏飞,王继明. 搜索引擎:原理技术与系统[M]. 北京:科学出版社,2002. [2] 李勇,韩亮. 主题搜索引擎中网络爬虫的搜索策略研究 . 计算机科学与工程,2008(30):3-12. [3] Cowie J,Lehnert W. Information Extraction[J].Communications of the ACM,1999,1(1):80~91. [4] 李刚,宋伟.征服 Ajax+Lucene 构建搜索引擎[M].北京:人民邮电出报社. 2006. [5] 常晓燕.基于 Java 的新闻搜索引擎的设计与实现.西南交通大学硕士学位论文 2004.4. [6] 严蔚敏. 数据结构[M]. 北京:清华大学出版社, 2000. [7] 洪光宗,王皓.搜索引擎 robot 技术实现的原理分析.现代图书情报技术,2002(1).

下载文档,方便阅读与编辑

文档的实际排版效果,会与网站的显示效果略有不同!!

需要 15 金币 [ 分享文档获得金币 ] 9 人已下载

下载文档

相关文档