基于帶偏好的寬度優先遍歷算法的網頁信息抓取方法研究

◆曾 凱

（天津市醫藥科學研究所聯合辦 天津 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．

[13] 馬永萍．正則表達式及其應用[J]．電腦編程技巧與維護，2012．

[14] 余晟(譯)，(美)Jeffrey E．F．Fried1 著．精通正則表達式．第3 版．北京：電子工業出版社，2007．

[15] 沙金精通正則表達式-基于NET/ASP/PHP/ JSP/JavaScript[M]．北京：人民郵電出版社，2008．

[16] 袁煜．正則表達式在外語教學及研究中的應用[J]．軟件導刊，2011．

[17] 宋鑫坤，陳萬米，朱明等．基于正則表達式的語音識別控制策略研究[J]．計算機技術與發展，2010．

[18] 劉瑞．正則表達式在語料庫與檢索中的應用[J]．中州大學學報，2012．

[19] 宋艷娟．基于XML的HTML和PDF信息抽取技術的研究[D]．福州：福州大學，2012．

[20] 唐皓瑾．一種面向 PDF文件的表格數據抽取方法的研究與實現[D]．北京：中國郵電大學，2012．