基于带偏好的宽度优先遍历算法的网页信息抓取方法研究

2017-11-17◆曾凯

网络安全技术与应用 2017年11期

关键词：爬虫队列优先

◆曾凯

（天津市医药科学研究所联合办天津 300020）

基于带偏好的宽度优先遍历算法的网页信息抓取方法研究

◆曾凯

（天津市医药科学研究所联合办天津 300020）

本文介绍了网上医药科研信息的抓取方法。为了高效地抓取网页内容，本系统采用带偏好的宽度优先遍历算法，将待访问的网址存放于高效的内存数据库BerKeley DB中，用正则表达式抽取指定内容，用Java提供的PDFBox技术识别电子文件内容。以详实的代码深入浅出的介绍了实现过程，结果表明，本系统能有效方便地应用于医药科研信息的采集。

网页内容识别；宽度优先遍历算法；内存数据库；正则表达式；PDF文件识别

0 引言

在医药科研领域工作，经常需要从互联网上查阅大量的医学、医药方面的信息，还需要查找大量的文献，用于服务科研工作。如果用浏览器搜索所需信息或文献，会显示出成千上万条信息，包含很多无用的信息，需要自己筛选出有用信息，而这种操作需要经常重复，费时费力。如果利用网络爬虫，根据带偏好的宽度优先遍历算法，从上千条信息中找出更有价值的信息，存入数据库，进行加工处理，所得数据成为服务医药科研工作的“数据平台”，为科研工作者利用信息资源进行科学管理提供了有力帮助。本文详细阐述带偏好的宽度优先遍历算法的工作原理、内存数据库BerKeley DB和正则表达式的使用方法、电子文件内容的获取方法。以详实的代码深入浅出地展现出以上功能的实现过程。

1 用带偏好的宽度优先遍历方法访问网站

宽度优先遍历是使用最广泛的一种网页抓取策略[1-3]，有三个优点：重要的网页离种子比较近；互联网的深度最多能达到 17层，使用宽度优先遍历能通过一条很短的路径以最快的速度到达所需网页；宽度优先遍历有利于多爬虫的合作抓取，多爬虫合作经常先抓取站内链接，抓取的封闭性很强[4-6]。

采用宽度优先遍历算法的爬虫抽取网站资源的过程就是从一系列的初始网址开始，把这些网页的子节点（即子网页的链接地址）提取出来，放入队列中依次进行抓取。被处理过的链接需要放入一张Visited表中。每次新处理一个链接之前，需要查看这个链接是否已经存在于Visited表中。如果存在，证明链接已经处理过，舍去，否则存入TODO表，追加进URL队列中，进行下一步处理。见图1。

图1 爬虫程序结构

本系统采用的是带偏好的宽度优先遍历算法的爬虫[7]。用优先级队列来实现带偏好的爬虫。优先级队列是一种特殊的队列，普通队列中的元素是先进先出的，而优先级队列是根据进入队列中元素的优先级进行出队操作。所以选择需要抓取的Url时，把重要的Url先从队列中选出来。为了确定哪些网页是重要的，应该考虑的因素比较多，有链接的欢迎度、链接的重要度、网站质量等[8]。本系统依据以下公式作判断：

IB(P)：链接的欢迎度，由指向当前Url的链接数量和质量决定。

IL(P)：链接的重要度，是关于Url字符串的函数，例如“.com”的重要度比“.cc”高。

X，Y：用来调整IB(P)和IL(P)所占比例的大小。

为了实现优先级队列，本系统采用Java提供的支持优先级队列的数据结构——java.util.PriorityQueue。部分代码如下：

在抓取过程中需要一个HashSet存储结构记录已经访问过的URL。HashSet有3个优点：能够存储海量数据；存取数据速度非常快；能够支持多线程访问。

//定义MyVisitedUrl，用于存储已访问的URL集合

Private static Set MyVisitedUrl = new HashSet();

//定义MyUnVisitedUr为支持优先级队列的数据结构，用于存储待访问的URL集合

Private static queue MyUnVisitedUrl = new PriorityQueue();

//获取URL队列

Public static Queue getMyUnVisitedUrl(){

Return MyUnVisitedUrl;

//进入Visited表，在访问过的队列中追加进新的Url

Public static void addMyVisitedUrl(String url){

MyVisitedUrl.add(url);}

//移除访问过的Url

Public static void removeMyVisitedUrl(String url){

MyVisitedUrl.remove(url);

//未访问的Url出队列

Public static Object MyUnVisitedUrlDeQueue(){

Return MyUnVisitedUrl.poll();}

//确保每个Url仅被访问一次

Public static void addMyUnVisitedUrl(string url){

If (url != null && !url.trim().equals(“”)

&& !MyVisitedUrl.contains(url)

&& !MyUnVisitedUrl.contains(url))

MyUnVisitedurl.add(url);}

//得到已经访问的Url个数

Public static int getMyVisitedUrlNum(){

Return MyVisitedUrl.size();}

2 用内存数据库BerKeley DB存储URL队列

本系统搜索网站信息时经常需要抓取上百条链接，显然内存数据结构并不适合这种应用。而合适的方法是使用内存数据库，目前非常流行的内存数据库是BerKeley DB[9]，适合存储成千上万条链接。它是一个嵌入式数据库，适合于管理海量的简单数据，当数据超出内存限制时，能把它固化在硬盘上。Key/value（即关键字/数据）是 BerKeley DB用来进行数据库管理的基础。每个Key/value对组成一条记录，而整个数据库由这样的结构单元构成。使用BerKeley DB构建URL队列的部分代码如下：

Private Environment MyEnv;

Private static final String CLASS_CATALOG =“java_class_catalog”;

Protected StoredClassCatalog javaCatalog;

Protected Database catalogDatabase;

Protected Database database;

Public String homeDirectory;

Private StoredMap pendingurisDB = null;

//BerKeley DB通过环境对象EnvironmentConfig对数据进行管理

EnvironmentConfig envConfig = new EnvironmentConfig();

envConfig.setTransactional(true);

envConfig.setAllowCreate(true);

//homeDirectory是用于存放由EnvironmentConfig指定数据库的数据文件和日志文件的目录

MyEnv = new Environment(new file(homeDirectory)， envConfig);

//设置 DatabaseConfig，指定数据库的属性

DatabaseConfig dbConfig = new DatabaseConfig();

dbConfig.setTransactional(true);

dbConfig.setAllowCreate(true);

//用于存储类信息的数据库要求关键字是唯一的

dbConfig.setSortedDuplicates(false);

//打开用来存储类信息的数据库

catalogDatabase= MyEnv.openDatabase(null ，CLASS_CATALOG ，dbConfig);

//初始化用于存储序列化对象的catalog类

javaCatalog = new StoredClassCatalog(catalogDatabase);……

//定义类CrawlUrl实现序列化接口

Public class Crawlurl implements Serializable{

……}

//实现TODO表

Super(homeDirectory);

// SerialBinding 使Key、value能够序列化到磁盘上

EntryBinding keyBinding = new SerialBinding(javaCatalog，string.class);

EntryBinding valueBinding = new SerialBinding(javaCatalog，CrawlUrl.class);

//创建数据存储的映射视图

pendingurisDB = new StoredMap(database，KeyBinding，valueBinding，true);

3 网页源文件内容获取

网页上包含着大量的信息，有文本、图片、视频、声音等等内容，我们需要的信息主要是文本内容。本系统采用正则表达式[10-11]和Jsoup抽取工具，能准确快速地抽取特定的文本内容。

4 下载网页内容并解析

HttpClient 是Apache Jakarta Common 下的子项目，提供了大量丰富的客户端编程工具包用来支持 HTTP 协议。

jsoup 是一个用来解析HTML文件的Java包，可以实现文本抽取、链接抽取、资源（如图像和声音）抽取、链接检查、站点检查。可通过DOM，CSS以及类似于jQuery的操作方法来取出和操作数据[12]。

用HttpClient下载网页，用Jsoup解析网页[13-15]。

举例说明，在政府网上获取从元旦到国庆节的放假日期和上班日期，见图2。

图2 放假通知

String url=”http://www.gov.cn/zhengce/content/2016-12/01/content_5141603.htm”;

String Fhtml=HttpUtil.getContent(url);

Document doc=Jsoup.parse(Fhtml);

//将网页正文内容存入FhtmlText变量中

String FhtmlText=Doc.body().text();

5 用正则表达式抽取指定内容

Java.util.regex包提供了对正则表达式的支持。通过 Matcher类根据给定的模式查找输入字符串。通过调用 pattern对象的Matcher方法得到一个Matcher对象[16-18]。

String regex=” 元旦.*(月d+日)*( *)(.*)春节.*(月d+日)*( *)(.*)清明节.*(月d+日)*( *)(.*)劳动节.*(月d+日)*( *)(.*)端午节.*(月d+日)*( *)(.*)中秋节.*(月d+日)*( *)(.*)国庆节.+月d+日”;

//如果网页上的放假通知书写规范，正则表达式可简化写成“元旦*([Ss]*?)国庆节.*月d+日”

Pattern p = Pattern.compile(regex);

Matcher m = p.matcher(FhtmlText);

If (m.find())

String Fstr = m.group(1);

If (Fstr.idexOf(“元旦”)＞0)

{ Int f1= Fstr.idexOf(“元旦”);

……

将各节日的放假日期和上班日期抽取出来，存入相应的数组中。

6 抽取PDF文件

本系统从网站中获取信息时经常会遇到重要的信息存放在PDF格式的电子文件中，该文件以独立于操作系统和硬件的方式来表示二维文档格式。为了从 PDF文件中提取文字，本系统采用了PDFBox[19]，它是专门用来解析PDF文件的Java项目[20]。提取PDF文件的部分代码如下：

File pdfFile = new File(“q.sohu.com/newpdf/2017282515 94.pdf”;

//装载pdf文件

PDDocument doc =PDDocument.load(pdfFile);

//用PDFTextStripper提取文本

PDFTextStripper stripper =new PDFTextStripper();

//设置文本是否按位置排序

Stripper.setSortByPosition(sort);

String content = stripper.getText(doc);

7 结语

本文提出了一种基于带偏好的宽度优先遍历算法，可以利用有限资源抓取重要性高的网页；利用Berkeley DB数据库可以更好地应对海量数据；正则表达式是高级检索和批量处理的关键技术，可以更好地抽取网页信息；使用PDFBox技术为识别电子文件内容提供了支持。应用结果表明，本系统能有效从互联网大量的信息中找到所需信息收集起来以供研究。当然，本方法还有可以进一步采用一种基于MapReduce框架的并行PageRank算法，应用于分布式网络爬虫。

[1] 郭涛，黄铭钧．社区网络爬虫的设计与实现[J]．智能计算机与应用，2012．

[2] 罗刚，王振东．自己动手写网络爬虫[M]．北京：清华大学出版社，2010．

[3] 李浩．网络蜘蛛的研究与实现[J]．科技信息，2012．

[4] 孙宏．搜索引擎技术与发展综述[J]．计算机光盘软件与应用，2012．

[5] 李勇，韩亮．主题搜索引擎中网络爬虫的搜索策略研究[J]．计算机与数字工程，2008．

[6] 李国成．网络搜索引擎的现状及发展探析[J]．企业科技与发展，2009．

[7] 吴信东，库玛尔．李文波，吴素研译．数据挖掘十大算法[M]．北京：清华大学出版社，2013．

[8] 杨爱民．并行广度优先搜索算法研究[D]．西安：西安电子科技大学，2012．

[9] 李明月．基于嵌入式数据库的分布式应用与实现[D]．长春：吉林大学，2011．

[10] 郭耀译．正则表达式经典实例[M]．北京：人民邮电出版社，2010．

[11] 瓦特．李松峰译．正则表达式入门经典[M]．北京：清华大学出版社，2008．

[12] 李刚．Java核心技术精讲[M]．清华大学出版社，2013．