Heritrix总结及消重算法初探

好久没有更新博客了。最后一次更新居然已经是一个月以前的事了。忍不住问自己，5月份都做了什么？编程珠玑看了几篇，但是没有像之前那样仔细去琢磨。数据压缩好像就停留在SPIHT算法的理解上了。花了两个星期搞了信息检索的作业，老实说，还没有做完。

我这部分的作业内容差不多是这样的：改进Heritrix中的网页消重方法。花了有一个多星期研究了Heritrix的总体构架。参考了网上的一些资料，自己也看了一些源代码，最后这些也都成了我的实验报告的一部分了。下面是我综合多份资料，以及自己对Heritrix的理解的总结。

 

Heritrix是一个纯由java开发，并且开源的Web网络爬虫，用户可以使用它从网络上抓取资源。它具有良好的扩展性，我们可以通过扩展它的各个组件，来实现自己的抓取逻辑。
Heritrix的操作模型如下：
 

 
                                     图1. Heritrix操作模型
用户通过web界面，定义抓取任务，包括定义抓取的范围（scope），frontier的选择以及处理链中选择用的各处理器。之后执行任务，Heritrix通过网络协议从网上下载网页，并将其存储到磁盘中。在这个过程中，heritrix还记录了网页抓取过程中的日志文档，用户通过刷新网页时时获取任务的进展情况。（有关它的启动方法，网上有很多文章，我就不详细介绍了）
Heritrix的整体结构如下：
 

                                             图2. Heritrix系统框架
Heritrix的目标成为一个通用的爬虫框架，用户可以轻松将不同的组件加入到框架中来从而实现自己的抓取策略及目标。一个抓取任务开始于选择和配置一系列组件，抓取任务的流程如下：
1. 在预定的URI中选择一个。
2. 从选择的URI的网址下载远程文件
3. 分析，归档下载到的内容
4. 从分析到的内容里面选择感兴趣的URI。加入预定队列。
5. 标记已经处理过的URI然后又从第1步开始
Heritrix中有三个重要的组件，它们是：Scope、Frontier和Processor Chain。Scope决定了哪些URL将会被选择加入任务列表中哪些则被汰选掉。Scope中的URL包括一开始时定义的种子URL以及由步骤4得到的URL，从而进行筛选。Frontier跟踪哪些URL将被调试以进行下载，哪些URL已经下载过了。它的目标是选择下一个正确的URL进行调度而避免重调而造成冗余。Processor Chain包括各种模块化了的处理器，它们连在一起对每个URL执行特定有序的动作，包括获取URL（步骤2），分析返回的结果（步骤3）以及将发现的URL传回给Frontier（步骤4），还有将URL内容写入磁盘，以及后面的后处理阶段。

由图2中的系统框架我们也可以看出Heritrix中的一些主要的数据结构，如CrawlURI、CrawlOrder、ServerCache等。
组件Web Administrative Console基本上可以算是一个独立的web应用，它是由一个嵌入式的Jetty Java HTTP Server所支持的。该组件提供了一个让用户配置抓取网页时的选用的组件和参数的界面，这些组件和参数由数据结构CrawlOrder接收，并且写在每个任务目录下一order.xml文件中。
CrawlController是系统的一个全局上下文，它拥有所有CrawlOrder的引用，所有的子组件也是通过它进行沟通的。Web Administrative Console也是通过它对爬虫进行控制的。
CrawlOrder中定义了足够的信息产生Scope，Scope为Frontier播种（由一开始的种子URL开始），而之后发现的URL Frontier将通过咨询Scope确定是否将其放入队列中。
Frontier的义务是对URL进行调度，以保证URL不会被不必要地重新访问，调整爬虫对远程机器的访问从而保证礼貌策略。它通过维护多个URL队列（将访问URL队列、已访问URL队列）来实现这个目标。Frontier只会从满足礼貌策略的队列上获取URL。（也就是说，礼貌策略是由Frontier执行实现的）。Heritrix提供了几种类型的Frontier，包括AdaptiveRevisitedFrontier、BdbFrontier以及WorkQueueFrontier，其中WorkQueueFrontier和AdaptiveRevisitedFrontier在拿到一个URL时并不判断其是否曾经被访问过，所以并不常用，可以在Web Administrative Console里进行配置，选择使用BdbFrontier。BdbFrontier使用了一个小型的嵌入式数据库Berkeley DataBase从而排除已经访问过的URL不再被访问。这一部分内容将在第三部分详细介绍。
为了提高爬虫的效率，Heritrix被设计成多线程的，每个工作线程叫ToeThread（在order.xml中可以设置最大的并行线程数），线程的run()函数实现了对每个URL的处理，步骤基本如下：
1. 从Frontier获取next() URL
2. 将URL有顺序的传给各个处理器（不同的处理器执行不同的操作如获取、分析及选择）
3. Finish() URL 报告了整个过程的执行完毕。
每个URL由数据结构CrawlURL表示，该结构将URL及在爬虫对URL经过处理器处理后得到的信息存储在一起，系统间的组件通过CrawlURL交换各自的信息及进度，最终CrawlURI将通过一系列处理过后得到的信息一起带到了Frontier，为Frontier的下一次执行策略提供可能的帮助。
爬虫访问远程机器时，首先需要通过DNS服务获取ip地址，为了减少访问DNS服务器的开销，系统设计了一个ServerCache，ServerCache存取了各个远程机器的相关信息，如ip地址，robot.txt信息、历史反应时间以及爬虫数据。
对于一个被调度的URL，爬虫的全部功能都由一系列特定的处理器实现。每个处理器轮流对URL执行它的任务，对URL进行标注然后结束。执行的任务依URI的任务、历史及获取的内容而各不相同。特定的URL状态甚至可能使某些任务直接被跳过。
在Heritrix中，处理器被整合成5个处理链，包括：
Prefetch Chain：预处理链中的处理器接收CrawlURI，该URL还没有执行任何网络操作。这些处理器一般会迟滞、重新安排或甚至停止相应URL的后续处理，例如为了保证在URL被处理前选获取网站的robot exclusion policy。
Fetch Chain：获取链中的处理器尝试通过网络活动去获取相应URL中的资源，例如在一个http事务中，Fetch processor将通过填写request缓冲区进行网络访问，并将结果保存到response缓冲区中，或者返回错误信息提醒相应缓冲区没有被填写的原因。
Extract Chain: 在抓取链中，处理器对获取到的URL资源进行后续操作，如将感兴趣URL提取出来等。在这一步中，URL只会被发现，而不会被评估。
Write Chain：写入链中的处理器将爬虫的结果（返回的信息或者抓取的特征）写入磁盘等永久存储设备中。默认提供的writer只是简单地将数据写入ARC文件中。第三方提供者可以通过实现新的处理器以将数据以新的方式写入。
Postprocess Chain： 后处理链中的处理器对CrawlURI执行最后的维护工程，例如测试发现的URL是否满足Scope定义的范围，如果必要的话将它们调度到frontier，更新内部的爬虫信息缓存区。

 

后面有相当一部分是翻译了《An Introduction to Heritrix》的，它的介绍确实让我有了一个比较好的整体结构，而且也很权威。当然，更深的理解是在看了很多网络文章之后对它的重读，呵呵。

 

对Heritrix的扩展一般就是实现一些符合自己逻辑需求的processor。

Heritrix中的网页消重策略主要是基于相同网址或镜像网站而言的。他有一些如bloomfilter、bdbfilter的工具对相同网址进行高效率的检测，同时用digest来判断会不会是镜像网页（因为镜像网页完全相同，所以digest生成的hash值是一样的）。而我的目标是实现近似网页的消重。实验中我使用的是google的simhash算法。算法很简洁，但是很强大，效果非常好。有关simhash算法的描述，可以看一下这个博文：http://leoncom.org/?tag=simhash。

我的实现过程大概是这样的：

（1）提取网页中的主要内容，把文本最长的那一部分提取出来。（因为对于近似网页，一般也就是复制主体内容，而这种内容一般比较长）。

（2）分词。实验中发现，英文的查重比中文的效果要好，原因是我的分词方法太过于简单。后来我使用了中科院的中文分词系统对中文内容进行分词后，效果也变得非常好。大家不知道在google的时候有没有发现，英文网页几乎没有重复的，可是中文网页经常重复，不知道是不是跟google的中文分词算法有关，呵呵。

（3）使用simhash算法计算fingerprint。

 

详细的或者等我把实验完全做完了，再把实验报告也上传上来吧，呵呵。目前还差一步就是把以上的东西与heritrix连接起来。是不是应该把这个过程放在一个writerProcessor里面呢？

评论

1 楼 DSONet 2012-11-14  

您好，提到的各种资料都有看过，也提到过思路，但对于具体操作还是不得要领，因此请教fingerprint是如何存储的？且如何进行消重的操作？谢谢。