结合有监督广度优先搜索策略的通用垂直爬虫方法

高 峰,刘 震,b,高 辉,b

(电子科技大学 a.计算机科学与工程学院; b.大数据研究中心,成都 611731)

0 概述

随着互联网的蓬勃发展,互联网信息数量呈现爆炸性的增长。对互联网用户来说,一个很重要的问题就是如何才能快速的找到其想要的网页内容。信息增长的速度越快,用户的这种需求就越迫切。

传统的垂直爬虫是获取特定网站或特定主题内容数据较为普遍的方法,但是垂直爬虫的一大弊端就是无法实现通用的爬取,需要针对不同的网站重新设计程序,而且人工查找URL队列及人工提取数据解析路径的工作更为繁琐,大大影响了工作效率。一般情况下,一个单独的爬虫程序只能处理某个独立站点的某一类型结构的页面数据。而用户对于数据的需求是多种多样的,如果对于每一个网站的数据需求都需要一个相应的爬虫程序比较费时费力,同时也会影响对应工作或项目的推进速度。

针对上述问题,本文提出一种配置简单、高效且可移植性高的通用爬虫设计方法。其核心思想是将通用型爬虫分为配置信息、初始化和正式爬取3个阶段。在配置信息阶段,用户针对待爬取网站完成基本信息配置;在初始化阶段,自动识别主题相关目标页面URL和目录页面URL,生成解析路径模板并且采用URL聚类的方法抽取出URL正则表达式过滤器;在正式的网页爬取阶段,利用初始化阶段生成的正则表达式过滤器和解析路径模板,以及有监督的广度优先与网页赋权搜索策略,实现对目标页面数据的快速准确提取。在此基础上,本文提出一种GWC(General Web Crawler)原型系统,并且在该原型系统上进行了广泛的实验。

1 相关研究

目前比较流行的自动化信息抽取工具有RoadRunner[1]、MDR[2]以及基于MDR的改进方法Depta[3-6]等。但这些工具的目标都是从结构相似的网页,如目录列表页面、查询结果页面或表格中,抽取信息,因为这类页面中的数据记录子树具有相似的结构,所以利用子树相似度算法的研究可达到较好的数据抽取效果,但是该类方法对待抽取网页中信息的结构化程度要求比较严格,这也是该类抽取方法最大的局限。文献[7-8]对于评论信息的抽取也属于该类抽取方法,文献[9]利用深层的匹配节点越多,2棵树的相似度越大的思想,提出一种高效的深度加权的树相似性算法,其对于每一个评论记录中具体数据项的抽取进行了详细深入的研究,但是同样也仅适用于评论信息的抽取。同时,这些方法仅利用HTML标签及结构信息,缺乏语义表达能力,最近很多研究已经注意到这个问题,并且利用页面的视觉信息来实现Web数据的抽取[10,11]。

目前,国内外对正文信息的抽取也有较多的研究。文献[12]设计的Crunch系统利用区域中链接文本/普通文本(link/text)的比值与某个既定阈值的大小关系来确定网页的正文区域。文献[13]改进文献[12]方法,将基于链接/文本比率和基于文本量的方法以类似于信息论中信息量计算的方式进行结合,对博客类网页的信息抽取达到较好的效果。目前对正文信息抽取的研究大多适用于信息量较大的网页,如新闻、博客、论坛等,对于正文信息量较少的网页抽取效果并不好,如大众点评网等。而且有些方法对于一些阈值的设置介绍并不明确,存在依靠经验设置的不足。

针对上述研究的不足,设计一种通用的垂直爬虫技术是非常有必要的,而本文设计方法能够对不同网站不同类型的网页实现快速、准确的数据爬取和阈值的动态自动设置。

2 GWC原型系统整体框架

通过配置简单少量的信息,指导爬虫搜索策略的设计和数据解析路径自动提取,是本文通用型垂直爬虫的设计前提。本文研究方法将用到的几个基本配置信息如表1所示。

表1 基本配置信息

GWC原型系统的整体框架如图1所示,根据预先配置的少量基本信息,从不同网站中快速实现定制化数据精确提取,无需二次处理,并将数据存储到数据库。

图1 GWC原型系统的整体框架

GWC原型系统主要模块的功能介绍如下:

1)配置模块:完成少量基本信息的配置,如入口链接、关键词和目标爬取数据,指导爬虫实现定制化数据抓取。

2)初始化模块:在初始化阶段预先爬取一定数量的URL,并自动识别出目标页面URL和目录页面URL,同时生成URL正则表达式过滤器和数据精确解析路径模板(Wrapper),其中,URL正则表达式过滤器包括目录页面正则表达式过滤器和目标页面正则表达式过滤器。

3)正式爬取模块:依据有监督的广度优先与网页带权搜索策略实现目标页面的抓取,使用数据精确解析路径模板实现数据自动准确抽取。

在不需要修改源代码的前提下,仅通过修改少量配置信息即可对不同网站实现快速、准确的定制化信息爬取存在两大难点:1)如何设计高效准确的通用型爬虫搜索策略;2)如何实现数据解析路径自动提取。针对以上2个难点,本文提出一种较为有效的通用型垂直爬虫设计方法。

3 有监督的广度优先网页带权搜索策略

网页的抓取策略通常可以分为深度优先、广度优先和最佳优先3种。深度优先在很多情况下会导致爬虫的陷入问题,目前常见的是广度优先和最佳优先方法。本文采用的是有监督的广度优先网页带权搜索策略,利用正则表达式过滤器广度优先大范围搜索相关页面,同时辅以基于隧道技术的网页权值计算达到有监督的最佳优先效果。本文设计的搜索策略能够保证爬虫充分、快速、准确的对相关页面进行定位及下载。

在很多情况下,垂直爬虫都是被设计用来只抓取某个指定网站中的特定主题网页,而对于这些页面的搜索通常设计人员会预先在网页源码中人工分析出所要解析的URL,将这些URL的解析路径预先写入到程序中,并且通常可能会预先人工维护一个初始爬取URL队列,以保证爬虫程序在运行过程中充分、精准的从页面中解析出相关的URL,从而过滤掉所有的噪音URL,这些工作耗费大量时间和精力。合理的搜索策略将保证爬虫减少无关页面的下载和避免陷入的问题,将极大地保证爬虫的爬取效率和爬取数据的准确性。为此,本文采用一种高效的有监督的广度优先网页带权搜索策略。

3.1 正则表达式过滤器

正则表达式过滤器包括目录页面正则表达式过滤器和目标页面正则表达式过滤器。它的作用包括2个方面:一是当解析页面的HTML文件获取到URL时,先用过滤器进行判断,如果URL与正则表达式匹配,则放入待爬取队列,如果不匹配,则过滤掉该URL,同时用以区分目标页面和目录页面进行不同的网页解析;二是在计算页面权值时作为一个计算参数,用来判断页面是否包含目标页面URL。

在初始化阶段,利用预先配置的有限的入口链接和关键词信息,使程序在预爬取一定数量的页面后可以自动准确的找到目标页面URL和目录页面URL并为目录URL分类,最后将每一类URL抽取出正则表达式,实现过程如下描述。

预配置的入口链接一般都是初始目录页面链接,而需要通过这个入口在网站中找到所有的目标页面URL,因为之前没有配置目标页面URL信息,所以初始时程序并不知道待爬取的目标页面URL的格式,相关信息只有预先配置的少量关键词信息(关键词是目标页面的标识信息),同时目标页面与目录页面中所包含的URL数量存在较大差异,而且目标页面在网站中数量也通常是较大的,利用这些有限信息完成对目标页面URL的识别和相关目录页面的分类。

初始化阶段预先从入口链接广度优先爬取一定数量的页面(一般4 000个～5 000个就可以满足需求),并且在爬取过程中每下载一个URL则判断该页面是否包含关键词信息,如果包含则将页面权值置为0,否则在父页面权值的基础上加1(在后续部分会有带权网页计算的详细介绍,而此部分只利用关键词作为网页权值计算参数),然后将带权值的网页URL加入到爬取队列中,在程序进行下一次爬取时会优先下载权值低的URL,这样会保证程序在有限的预爬取时间里尽可能多地爬取到与主题相关的目标页面和目录页面URL。同时在下载页面时会统计并保存该页面所包含的URL数量。当预设数量的页面爬取结束后,通过计算入口链接页面包含的URL数量与这些下载页面包含的URL数量的差值,并取差值的平均值作为区分目录页面和目标页面的阈值,然后程序对这些URL数量差值大于这个阈值页面URL进行聚类,最大的类则为预期的目标页面URL类,再通过URL正则表达式的生成规则抽取出目标页面正则表达式过滤器。最后将预爬取到的所有URL进行聚类,剔除掉目标页面URL类,则剩下的URL类即是目标页面URL类。而通常聚类的数量很多,通过大量实验证明本文只取前10个最大的类即可包含所有主要目录页面类别,并分别抽取出正则表达式作为目录页面URL正则表达式过滤器。

本文将这一阶段定义为初始化阶段,在初始化阶段抽取出URL正则表达式过滤器和提取数据解析路径模板。

3.1.1 URL正则表达式的生成规则

首先介绍URL的数据结构。把一个URL分成3个部分(去掉http协议部分):Host,Path和Query。其中,Path由一系列directory参数组成,Query由一系列键值对组成。例如URL为http://news.qq.com/a/20150415/044667.htm?tu_biz=1.114.1.0&du=1,其中,Host为news.qq.com,Path为/a/20150415/044667.htm,Query为tu_biz=1.114.1.0&du=1,组成该Query的键值对为(tu_biz,1.114.1.0)和(du,1)。

由于本文设计的通用型垂直爬虫每次的爬取都是针对某个特定网站,所解析到的URL都是该网站中的URL,因此无论是对于每一类的目标页面还是目录页面的正则表达式生成,都会将Host部分直接保留下来,而Path和Query部分都是将其细分,然后对每一个参数都在同类URL中提取共有的正则表达式规则。通过对大量网站的观察,本文总结出常见的URL正则表达式生成规则,如表2所示,其基本包括了URL常见的参数形式。

表2 正则表达式生成规则

3.1.2 URL聚类

由于可获取到的主题相关目录页面不止一个,这些目录页面依据它们的URL结构特点可以划分聚合成不同的种类,而每一类可以将其依据URL正则表达式的生成规则自动抽取出这一类URL的正则表达式作为其过滤器。

每条URL本质就是一个由简单字符组成的字符串,URL聚类的实质就是将相似的URL字符串划分为同一类,因此URL聚类的关键就是URL字符串相似度的计算。根据URL的结构,由于本文针对的是特定网站的爬取,因此每一类的Host部分必然是相同的,Path部分不同数量的directory参数和参数值的不同决定了该条URL所指向的同一网站不同类型的网页,而Query部分的距离不用于对2条URL距离的判断,如果2条URL除了Query其他部分都相同,则这2个链接指向的页面基本是由同一个模板产生或属于同一主题,因此URL相似度计算的关键就是Path部分相似度的计算。而Path部分的每一个directory参数都具有不同的实际意义,参数之间也通常会有较大的差别,并且每一位置的相似度对于整条URL的相似度贡献值是不同的,位置越靠前的参数相似度越高也就意味着URL的相似度越高。因此,将Path部分整体作为一个字符串进行比较显然是不合理的,需要将Path部分按directory参数进行拆分,对每一个参数分别进行相似度计算,再将参数的相似度进行整合从而得到2条URL的相似度。经过大量网站的观察发现,Path部分的directory参数基本都是非常短的字符串,长度基本在20个字符以内。常见的字符串相似度算法有编辑距离算法、最长公共子串算法、贪心字符串匹配算法等,对于较短字符串的相似度计算,算法之间的时间效率差别不大,因此本文选择了常见的计算简单的编辑距离算法进行URL的相似度计算。

基于上文中介绍的URL数据结构,本文利用各个部分的距离来计算URL之间的相似度。2条URLi、j的相似度用sURLij表示,首先要判断2条URL的Host部分是否相同,若Hosti≠Hostj,则直接将sURLij值置为0,若Hosti=Hostj,判断Path部分的长度(即参数个数)是否相等,如果Path_Lengthi≠Path_Lengthj,也将sURLij直接置为0,这两步的计算是为了保证将Host部分不同的URL以及Host部分相同但Path部分长度不同的URL直接聚合成不同的类,即聚成的每一个URL类都必须保证Host部分相同而且Path部分长度也相同。

当Hosti=Hostj且Path_Lengthi=Path_Lengthj时,分别计算出2条URL的Path部分每一位置directory参数的编辑距离edit,并做归一化处理,将每一部分参数的编辑距离与该部分参数的理论上最大编辑距离(即2条待比较串最长串的长度)做比值,URL之间越相似其相似度的值应该越大,因此将URL比值加1再取倒数。同时,由于Path部分每一位置的directory参数具有实际意义,而且每一位置的参数对于整条URL相似度的贡献度是不同的,位置越靠前的参数相似度越高就意味着整个URL的相似度越高,因此将每一部分directory参数设置不同的URL相似度参数,如果Path有m个参数,则第一个位置的参数对应的URL相似度参数为m,其余部分参数的URL相似度参数值依次递减,最后将所有位置参数得到的编辑距离比值倒数与对应位置参数的URL相似度参数乘积求和即为2条URL的相似度。若2个URL的Path部分有m个参数,则URL距离计算公式如下所示:

(1)

其中,m为每条URL Path部分的directory个数,editk为2条URL第k个位置对应的2个directory参数的编辑距离,而max_editk则表示对应的2个directory参数理论上最大的编辑距离,即长度最大的directory参数的长度。

在聚类时通过URL相似度计算公式得到2条URL的相似度,而聚为一类的URL之间的相似度都不小于一个阈值h,本文对于相似度阈值的设定是自动动态设定的,相似度的阈值计算公式为:

(2)

其中,m为每条URL Path部分的directory个数。若满足阈值条件则聚为一类,如果小于阈值则以该条URL为基准新建一个类。URL聚类算法描述如下:

算法1URL聚类算法

输入URL_Queue;//输入为一个URL队列

输出URL_Regex_Queue;//输出URL正则表达式//队列

1.创建一个URL聚类队列URL_Cluster_Queue;

2.while(URL_Queue不为空){

3.从URL_Queue取出一个Url;

4.If(URL_Cluster_Queue 为空){

5.初始化一个仅包含该Url的聚类URL_Cluster;

6.将该聚类添加到队列URL_Cluster_Queue;

7.}

8.Else{

9.Boolean flag=false;

10.foreach(URL_Cluster in URL_Cluster_Queue){

11.sURL= Url与URL_Cluster中每个url的相似度均值;

12.If(sURL>=h){

13.将Url添加到该聚类URL_Cluster;

14.flag=true;

15.break;

16.}

17.}

18.If(flag==false){

19.初始化仅包含该url的新聚类URL_Cluster;

20.将新URL_Cluster 添加到URL_Cluster_Queue;

21.}

22.}

23.}

24.对URL_Cluster_Queue中的每个聚类生成对一个正则表达式,输出到URL_Regex_Queue

在所有的URL聚类结束后,使用URL正则表达式的生成规则为每一类URL抽取出对应类的URL正则表达式,作为目录页面正则表达式过滤器,其示例为:

[http://www.dianping.com/shop/[0-9]+(.[a-zA-Z]+)?/?,http://www.dianping.com/search/category/[0-9]+/[0-9]+/w+(.[a-zA-Z]+)?/?,http://www.dianping.com/mylist/[0-9]+(.[a-zA-Z]+)?/?,http://www.dianping.com/member/[0-9]+(.[a-zA-Z]+)?/?,http://www.dianping.com/search/keyword/[0-9]+/.*(.[a-zA-Z]+)?/?,http://www.dianping.com/[a-zA-Z]+/food(.[a-zA-Z]+)?/?,http://www.dianping.com/member/[0-9]+/badge/[0-9]+(.[a-zA-Z]+)?/?]

3.2 带权网页计算

大部分网站都可以看作3层结构(如图2所示):初始种子页面,目录页面,目标页面(无关页面)。网络爬虫在这种网页结构上不断的向深度和广度游走,搜索与目标主题相关的页面,最终目标是搜索到全部目标页面,而在这个过程中将会经过大量的无关页面和相关的目录页面。如果爬虫沿着无关页面深度搜索下去将远远偏离目标页面,极大地影响爬虫的工作效率和爬取数据的准确性。为此,本文提出有监督的广度优先与网页带权搜索策略,以保证爬虫能够在网站3层结构中沿着正确的方向游走,减少无关页面的下载,提高搜索效率,而该策略最关键的就是带权网页的计算。

图2 网站3层结构

基于这种网站3层结构,通用型垂直爬虫的设计在爬取时将其划分为2个阶段,初始化阶段和正式爬取阶段。在初始化阶段,预爬取大量URL找到尽可能多地与目标页面相关的目录页面,从而生成目录页面正则表达式过滤器。对于确定一个页面是否是目录页面,本文采用目标页面正则表达式和目标页面关键词相结合的方法,如下文详细介绍。

3.2.1 主题孤岛问题

文献[14]提出在实际的网络中主题相关的网页并不总是连在一起的,从一个主题相关的页面链接到另一个主题相关页面经常需要穿过多个无关页面,因此也造成网络中存在主题孤岛的现象,即一个主题岛周围往往会被一些主题无关页面包围致使与其他主题岛分割。

文献[15]提出了一种简单的隧道技术来解决主题孤岛问题,它们将每个页面设置一个权值,如果该页面是主题相关页面,则它的权值置为0,如果是主题无关页面,则该页面的权值在其父页面的权值基础上加1。如图3所示,节点代表页面,加黑节点代表主题相关页面,其他节点代表主题无关页面,箭头代表一张页面到另一张页面的链接。根据隧道技术,节点1代表的页面的权值为0,节点2、3、4代表的页面的权值为1,节点5代表的页面的权值为0,节点6、7、8代表的页面的权值为2,节点9代表的页面的权值为0,而节点10代表的页面的权值为1。垂直爬虫在爬取时只抓取权值小于一个阈值的页面,如阈值为2,则节点6、7、8、9、10代表的页面都不会被抓取,如果阀值设为大于2,那么图3中的所有页面都将会被抓取。

图3 页面距离示意图

3.2.2 基于隧道技术的网页权值计算

本文在上述隧道技术的基础上,明确了与目标页面相关网页的判断和权值计算:对于任意页面URL1,如果URL1对应的HTML文档包含指向目标页面的URL即有可通过目标页面正则表达式过滤器的URL,或者该HTML文档中包含配置文件中的关键词,则将该URL1的权值置0,当没有关键词,而且不指向相关页面时,则URL1的权值在指向它的页面的权值基础上加1。例如,设URL1中指向其他页面的任意一个URL为URL2,若URL2对应的HTML文档包含指向目标页面的URL或者包含关键词,则权值置0,否则在URL1权值的基础上加1。

URLWeight=

(3)

其中,URLWeight表示网页的权值。

按照上述定义,URL权值越大代表该URL与目标页面关系越小。设置不同的阈值爬取的效果一般是不同的,以预爬取5 000个页面为例,其中,随机选取新浪股票网站抓取股票相关的页面和大众点评网抓取川菜主题相关的店铺信息页面结果为示例(此处只关心抓取到的与主题相关的页面数量),不同阈值和条件爬取结果如表3所示。

表3 不同阈值和条件爬取结果

由表3可知,设置不同阈值对于爬取到的相关页面数量是有影响的,其中新浪股票的结果不是很显著,因为这是一个相对较大的专题,在开始爬取时就会有大量的相关页面,而大众点评的川菜专题相对较小,爬取时会遇到大量无关页面。因为阈值的限定可以帮助程序找到更多的相关页面,所以大众点评的结果就更为显著一些。而本文是利用初始化阶段预爬取的效果使程序自动预设一个URL权值的阈值,该阈值是所有预爬取页面权值的平均值并取四舍五入后的值。

系统在进行关键字判断时,首先会剔除HTML文档中所有a[href]标签的属性值和文本内容,因为这样可以大大减少因跳转链接的不相关内容导致爬取到其他无关页面,从而得到更准确的判断且去除干扰使结果更加干净,而且也会使保存异常结果的文件中的异常结果大大减少。

4 数据解析路径模板自动抽取

每一个实体数据节点在网页中都对应一条唯一的XPath路径,爬虫在解析实体数据时就是根据这条解析路径抽取出对应数据项,而实体数据的XPath路径通常需要开发人员在网页源码中人工分析,或者借助其他工具提取。为实现爬虫程序自动提取数据解析路径,生成所需实体数据标签的提取路径模板,本文设计了有效的数据解析路径抽取算法。例如大众点评网中北京新世纪日航饭店这个目标页面,输入标题“北京新世纪日航饭店”,可以得到标题所在的路径,之后所有的目标页面都可以从该路径中提取标题信息。

目标页面模板生成基本流程如图4所示。

图4 目标页面模板生成流程

从预先配置的基本信息中读取前2条目标页面URL(可先分别记为A、B),并将它们的HTML文件下载下来,以这2个页面为模板,将它们的HTML文件解析成HTML树形结构,然后取出2棵树中相同的结点,形成一棵新的树,新生成的树即为该页面类型的模板。对于2棵树A和B,先只遍历树A,将A中结点放入节点队列的同时将该节点的父节点路径也放入队列。这里定义的路径是符合jsoup查询语法的从根节点到该节点的路径,这样做的好处是将路径保存起来之后可以直接使用。从队列中提取节点时,先用jsoup查找树B中相同路径下是否存在相同的节点,若存在,就把该节点和该节点的路径放入队列,且对于叶子节点和非叶子节点需存在不同队列。遍历完后便得到了2棵树所有相同叶子节点的路径,这样便形成了一棵树,即形成了网页模板。

在得到公共节点及节点路径的模板后,需要根据预先配置的目标爬取实体数据信息确定待爬取数据的精确解析路径,实现数据的定制化爬取。其实现思想是:依次从预先配置的目标爬取数据文件中取出每个需爬取的实体数据标签内容,并以标签内容为依据先遍历已保存的叶子节点队列,若找到了一个叶子节点的文本内容或属性值与标签内容相等,则将该叶子节点及该节点的路径保存到相应的队列中,如果叶子节点没有所需的标签,则自底向上遍历非叶子结点完成同样的动作,若叶子节点和非叶子节点队列中都没有找到与标签内容相等的节点,则查找包含实体数据标签内容的节点;然后将找到的节点路径向根节点回溯,每回溯一个节点时,如果该节点在同一层兄弟节点中没有同名节点,则在节点路径中直接保存其节点名即可,若同一层中有同名节点,需先判断是否有能区分其他同名节点的属性值(包括id、class及其他属性),如果有则在路径中保存该节点名的同时保存该属性名及属性值,若同名节点中没有这种属性,则需保存该节点在这层同名中的相对位置,以便其他节点准确找到该节点。

当所需爬取的标签内容数量不固定的时候(如评论),在提取准确路径时,将这2个标签的路径都提取出来,如以下2条路径:

1)div[class=tent]>li:nth-of-type(1)>p[class=info]>span:nth-of-type(2)。

2)div[class=tent]>li:nth-of-type(2)>p[class=info]>span:nth-of-type(2)。

然后从路径的最后一个节点往根节点回溯,并同时判断2条路径对应的节点是否是兄弟节点,如果不是则继续回溯,如果是则将路径的对应节点直接用节点名表示并停止回溯。

3)div[class=tent]> li>p[class=info]>span:nth-of-type(2)。

路径3)是1)、2)这2条路径的公共路径,同时也代表了这类标签的公共路径,依据这条路径,在正式爬取阶段就可以将该类标签内容全部解析出来。

经过以上流程,最终会得到需爬取标签的通用解析路径即通用模板,而这些路径是以json格式保存到数据解析路径模板文件中。其中,key是“标签名称#标签内容所在部分”的形式表示,标签内容所在部分指出了该标签内容在节点中的位置,如果为text说明在节点的内容部分,如果为某一属性(如id),则说明标签内容在节点中该属性的值(如id="top"中的top)的部分,value则是符合jsoup解析规则的标签的通用路径。示例如图5所示。

图5 通用路径示例

依据上述描述,本文数据解析路径模板自动抽取算法包括2部分,如下所示:

算法2公共网页模板提取

输入Dom_Tree1,Dom_Tree2

//预先配置的2个目标页面的DOM树

输出Leaf_queue,Non_leaf_queue

//保存叶节点路径的队列和非叶节点路径的队列

1.取Dom_Tree1根节点root1;

2.将root1和空路径加入新建节点队列Nodequeue;

3.//队列Nodequeue中每个元素保存一个节点和父节点//路径

4.While(Nodequeue不为空){

5.取Nodequeue队头节点node和父节点路径;

6.计算node节点路径NodePath =父节点路径+">"+node节点名;

7.If(用NodePath在Dom_Tree2找到相同节点node{

8.If(node没有孩子节点)

9.将node节点和节点路径NodePath加入叶节点路径队列Leaf_queue;

10.Else{

11.将node节点和节点路径NodePath加入非叶节点路径队列Non_leaf_queue;

12.foreach(childNode in node孩子节点){

13.将childNode和node节点路径NodePath同时加入Nodequeue;

14.}

15.}

16.}

17.}

18.return Leaf_queue,Non_leaf_queue;

算法3精确节点路径提取

输入tags.json,Leaf_queue,Non_leaf_queue

//tags.json为预先配置的目标爬取实体数据

输出accurate_nodepath_queue

//精确的节点解析路径队列

1.foreach(targetData in tags.json){

2.int flag1=0,flag2=0;

3.Node Tnode=null;

4.foreach(leafNode in Leaf_queue){ //遍历叶子节点

5.If(leafNode文本数据或者属性值等于targetData){

6.Tnode=leafNode;

7.flag1=1;

8.break;

9.}

10.else if(leafNod文本数据或者属性值包含targetData){

11.Tnode=leafNode;

12.flag2=1;

13.continue;

14.}

15.}

16.While(flag1=0){

17.foreach(nonLeafNode in Non_leaf_queue){//遍历非//叶子节点

18.If(nonLeafNode的文本数据或者属性值等于 targetData){

19.Tnode=nonLeafNode;

20.flag1=1;

21.break;

22.}

23.else if(flag2==0&& nonLeafNode的文本数据或者属性值包含targetData){

24.Tnode=nonLeafNode;

25.continue;

26.}

27.}

28.}

29.取Tnode 节点路径TnodePath;

30.foreach(node in TnodePath){//反向遍历节点路径//TnodePath上的节点

31.If(node的兄弟节点中不存在同名节点){

32.在节点路径TnodePath直接保留node节点名;

33.Continue;

34.}else if(node在兄弟同名节点中存在不同的属性值)//{优先考虑ID和class属性

35.在节点路径TnodePath中对应的node节点名后面加上此属性及属性值;

36.Continue;

37.}else{

38.计算该节点node在兄弟同名节点中的相对位置并加入TnodePath中;

39.}

40.}

41.将遍历修改后的TnodePath加入到精确解析路径队列accurate_nodepath_queue;

42.}

43.Ruturn accurate_NodePath_queue;

5 实验结果与分析

5.1 实验爬虫设计

在概述部分介绍的信息抽取工具和方法都是针对某一类型的网页实现数据的抓取,并不是可以对不同网站不同网页实现抓取的通用信息抽取模型,并且对数据的抽取也较为粗略。而本文所设计的通用型垂直爬虫设计方法,能够对不同类型的网站实现快速精确的定制化数据爬取。两者的实现方法和目标都不同,因此不适合进行实验比较,并且目前对于通用型数据抽取方法研究的相关文献较少,没有找到合适的对比方法。但是本文发现了目前较为流行的一个数据采集应用产品——八爪鱼数据采集器,该产品的应用目标和实现方法与本文提出的通用型垂直爬虫设计方法较为相似,因此本文选择与该产品进行实验对比,以验证本文方法的可行性和有效性。

本文设计的通用型垂直爬虫GWC原型系统包括3个模块:配置模块——配置基本信息,预爬取模块——在目标网站预先爬取4 000条URL,正式爬取模块——完成定制化数据的正式爬取。该爬虫程序由Java程序语言完成,并应用了HttpClient来模拟浏览器完成页面的下载,使用Jsoup实现页面的数据解析工作,而Redis则用来实现数据的去重处理和数据的存储。实验的软硬件环境为Windows 7操作系统、AMD A8-5600K APU with Radeon(tm)HD Graphics 3.60 GHz处理器、8 GB安装内存(RAM)、64位操作系统。

5.2 初始化阶段实验结果及分析

当配置信息配置完成后,GWC原型系统则开始进行初始化,预下载4 000个页面即4 000条URL,完成URL正则表达式过滤器和通用路径模板的生成。当达到预设的4 000个页面阈值时,系统则会自动停止。GWC原型系统在初始化阶段的爬取情况如图6～图8所示。

图6 预爬取时间对比

图7 页面权值平均值对比

图8 目标页面URL识别准确率

由图6可以看出,预爬取4 000个页面基本可维持在11 min～13 min左右,不会耗费大量时间,偶尔也会因为网速等网络环境原因达到15 min以上。但总体来说,仅需要十几至二十分钟的时间即可完成初始化的工作,为正式爬取阶段做好必要的准备,具有较高的效率。

由图7可以看出,每个网站爬取到相关页面的页面平均权值保持在一个稳定的阈值,不同的网站阈值分布也有差异,由于本文在网页权值计算时将权值设置为整数,因此对页面权值的平均值进行四舍五入取整即可,根据爬取结果以上测试的几个网站在正式爬取阶段均可将网页权值阈值设置为1,在后续实验中也证明了本文阈值的设置是合理的,可以保证程序充分准确的爬取到主题相关目标页面。同时,图8目标页面URL识别准确率的结果也充分证明本文对目标页面URL识别的方法完全可以保证识别的准确率,而且对于目录页面URL的分类和选取也同样可以保证系统对于目标页面的充分爬取(在正式爬取阶段的结果可以体现)。

综上实验结果,本文设计的搜索策略可以保证爬虫系统在短时间内抓取到足够数量的相关目录页面,并且可以自动准确的识别出目标页面URL,完成页面权值阈值的设置,能够准确的生成足够数量的目录页面正则表达式过滤器以及目标爬取数据的通用路径模板,为正式爬取阶段做好准备。

5.3 正式爬取阶段与现有通用爬虫技术实验对比

依据本文的实现策略设计的爬虫系统与八爪鱼数据采集器从爬取效率、数据完整性和数据准确性3个方面进行对比。

5.3.1 爬取效率

八爪鱼仅可以爬取具有分页列表的页面,而且在爬取的过程中是以翻页的方式进行采集,因此其在总爬取时间上是占优势的。而GWC原型系统的批量爬取是采取有监督的广度优先与网页带权搜索策略以全网站搜索的方式进行,因此总的爬取时间要慢一些,但也不是绝对的,有些时候在总的爬取时间上该系统还是会更快一些。一旦程序定位到了目标页面的目录页面,GWC原型系统对于该目录页面的目标页面数据抓取相对更快,而且单位时间内的网页抓取效率也更优。

在爬取众筹网数据时(30 min),GWC原型系统可以爬取2 000～3 000多条数据,而八爪鱼即使是以翻页的方式进行爬取,也只能爬取500～600多条数据。

当爬取新浪股票数据时(5 h),GWC原型系统可以爬取2 300～2 500条数据,虽然在正式爬取时其爬取总时间是15 h左右,而在实际爬取工作中,5 h～6 h即可爬取到近85%的数据量,剩余的10 h时间是为了保证爬取数据的数据量足够多,以保证数据的完整性。而八爪鱼在5 h的时间只抓取到了1 500多条数据,而且随着爬取时间的增长,可以明显观察到其爬取速度在减慢。虽然GWC原型系统有时在总爬取时间上要慢一些,但是全网站搜索可以保证数据的完整性。

5.3.2 数据完整性

在前文提到,八爪鱼仅可以爬取具有分页列表的页面,而一旦要爬取的目标页面没有给出分页列表或者分页列表数据不全时,就无法对数据进行批量采集或者采集的数据有大量的遗漏缺失。

以大众点评网数据为例,爬取川菜专题时,网站显示的总店铺数量有近17 000家(而实际存在的只有14 000～15 000家左右,因为区域重叠和分类重叠的原因造成店铺有重叠),而其分页列表中则一共只给出了1 000多家店铺,用八爪鱼进行爬取只采集到了700多条数据,而GWC原型系统则采集到了14 000多条数据,但是要去掉2 000多条异常数据,在很大程度上保证了数据量的完整。对于八爪鱼遗漏的数据,当然用户可以花费一定时间去寻找其他分页列表再次进行配置和爬取,但是对于其通用性和效率来说是有一定影响的,且进行再次爬取时会爬取到大量已下载的重复数据。即使分页列表中给出了所有的数据量,经过几次抓取测试,八爪鱼也不会将数据爬取完全,仍然有大量数据遗漏丢失。

在爬取众筹网数据(预期约4 400条)时,八爪鱼在进行了1 h后即停止了爬取,但是其只爬到800多条数据,而经过几次测试GWC原型系统则是在2 h后完成了爬取,与预期数据量相比数据误差没有超过20条数据。对于GWC原型系统而言,利用本文设计的搜索策略,采用全网站搜索的方式,因此在充分时间爬取后数据量基本可以达到预期效果,不会大量遗漏数据。

在爬取新浪股票数据(预期约4 400条)时,八爪鱼在近11 h的时间爬取了2 600多条数据,而GWC原型系统则最终能够爬取到近3 050条数据。图9所示为3个例子的数据完整性对比图。

图9 3个例子的数据完整性对比

对于八爪鱼而言,无法完成一个目标页面中的数量不固定标签数据(如评论)的爬取,只能一次爬取其中一条数据,如果强迫一次爬取所有数据则会增加大量无关的杂质数据。有些数据在HTML树中的节点定位也不如GWC原型系统准确,即会造成在爬取数据时增加部分杂质数据。而GWC原型系统利用在初始化阶段生成的目标爬取数据精确解析路径模板,在正式爬取阶段能够准确直接的从目标页面中找到目标数据节点,从而能够准确的抽取出干净的目标数据。因此,本系统的数据爬取相对更加完整干净。

5.3.3 数据准确性

数据准确性是指是否爬取到主题目标页面数据。八爪鱼以翻页的形式下载页面,爬取数据的准确率很高,只要爬取的分页列表中给出的目标页面都是准确的,其准确率都可以达到100%,而对于大众点评网,在川菜列表中同样出现了很多火锅、小吃快餐、西餐等其他类别的店铺,八爪鱼无法对这些非目标页面过滤掉而是全部爬取下来,此时准确率也会降低。

GWC原型系统是采取有监督的广度优先与网页带权搜索策略的形式随机下载页面爬取数据,因此,其数据的准确性对于不同的网站难以全部达到100%的准确性,但是经过大量测试,其也可以达到很高的准确率,有部分网站是可以达到100%。如果该网站的URL格式对于区分不同类别的页面有很好的效果,则可以使系统生成一个非常准确的目标页面正则表达式过滤器,再增加关键词的辅助判断,系统就能保证非常高的准确性。反之,如果该网站的URL格式不能很好地区分不同类别的页面,准确性就会降低。但是关键词如果选取合适,则可以保持或增加准确性。

表4和表5是每个网站爬取2次的结果,且随机抽取20 min的爬取结果作为统计量。因为20 min的爬取时间较短,且每次程序都是随机下载页面,所以每个网站的2次爬取总量会有不定的差距。

表4 八爪鱼数据准确性测试实例

表5 GWC原型系统数据准确性测试实例

从表4、表5可以看出,系统对于新浪股票、搜狐军事、众筹网等网站的爬取效果很好,准确性很高,对于这几个大专题基本是可以达到100%的准确性,因为这些网站都有很好的URL格式,对于区分不同类别的网页有决定性的效果,加上关键词的判断,所以准确率非常高。而对于大众点评网这一类网站,许多类别页面的URL格式是相同或类似的,程序不能生成一个准确的目标页面正则表达式过滤器,对于有些网站,可以通过选择准确合适的关键词来进行辅助定位,也可以维持和提高准确性,例如爬取天涯论坛中的股市谈论,其URL也不能做一个准确的区分,但是辅以“股市”和“股票”的关键词就可以帮助程序较为准确的抓取目标页面。本文对于大众点评网是用了“成都&&川菜”的关键词,但是由于其他类别的店铺页面(如火锅、小吃快餐、西餐和外地的川菜店铺等)也具有目标页面的URL格式,而且在页面的评论区或其他文本位置也都可能会出现这2个关键词,导致程序无法将这些无关页面过滤掉,因此造成了准确性的下降。

6 结束语

研究一种高可移植性的通用型自动化垂直爬虫设计方法具有重要的应用价值。通过分析总结传统垂直爬虫的弊端和实现通用化的难点,本文提出一种高效的有监督的广度优先与网页带权搜索策略和数据解析路径模板自动提取方法。实验结果证明,该方法的通用性效果较好,可以对不同类型的网站实现快速爬取,爬取数据的效率较高,数据完整性很好,且对于大部分网站也能保证很高的准确性。下一步将在本文研究的基础上,继续对搜索策略进行优化,并提升通用型垂直爬虫自动化程度。