自己动手写网络爬虫（修订版）
上QQ阅读APP看书，第一时间看更新
上一章目录下一章

1.2 宽度优先爬虫和带偏好的爬虫

1.1节介绍了如何获取单个网页内容。在实际项目中，则使用爬虫程序遍历互联网，把网络中相关的网页全部抓取过来，这也体现了爬虫程序“爬”的概念。爬虫程序是如何遍历互联网，把网页全部抓取下来的呢？互联网可以看成是一个超级大的“图”，而每个页面可以看作是一个节点。页面中的链接可以看成是图的“有向边”。因此，能够通过图的遍历的方式来对互联网这个超级大“图”进行访问。图的遍历通常可分为宽度优先遍历和深度优先遍历两种方式。深度优先遍历可能会在深度上过“深”地遍历或者陷入“黑洞”，因此大多数爬虫都不采用这种方式。另一方面，在爬取的时候，有时候也不能完全按照宽度优先遍历的方式，而是给待遍历的网页赋予一定的优先级，然后根据这个优先级进行遍历，这种方法称为带偏好的遍历。本小节会分别介绍宽度优先遍历和带偏好的遍历。

1.2.1 图的宽度优先遍历

下面先来看看图的宽度优先遍历过程。图的宽度优先遍历（BFS）算法是一个分层搜索的过程，和树的层序遍历算法相同。在图中选中一个节点，作为起始节点，然后按照层次遍历的方式，一层一层地进行访问。

图的宽度优先遍历需要一个队列来保存当前节点的子节点。具体的算法如下。

（1）顶点V入队列。

（2）当队列非空时继续执行，否则算法为空。

（3）出队列，获得队头节点V，访问顶点V并标记V已经被访问。

（4）查找顶点V的第一个邻接顶点col。

（5）若V的邻接顶点col未被访问过，则col进队列。

（6）继续查找V的其他邻接顶点col，转到步骤（5），若V的所有邻接顶点都已经被访问过，则转到步骤（2）。

下面，我们以图示的方式介绍宽度优先遍历的过程，如图1.3所示。

图1.3 宽度优先遍历过程

选择A作为种子节点，则宽度优先遍历的过程如表1.2所示。

表1.2 宽度优先遍历过程

在表1.2所示的遍历过程中，出队列的节点顺序即是图的宽度优先遍历的访问顺序。由此可以看出，图1.3所示的宽度优先遍历的访问顺序如下：

A→B→C→D→E→F→H→G->I

本节讲述了宽度优先遍历的理论基础，把互联网看成一个“超图”，则对这张图也可以采用宽度优先遍历的方式进行访问。下面将着重讲解如何对互联网进行宽度优先遍历。

1.2.2 宽度优先遍历互联网

1.2.1节介绍的宽度优先遍历是从一个种子节点开始的，而实际的爬虫项目是从一系列的种子链接开始的。所谓种子链接，就好比宽度优先遍历中的种子节点（图1.3中的A节点）一样。实际的爬虫项目中种子链接可以有多个，而宽度优先遍历中的种子节点只有一个。比如，我们可以指定www.lietu.com和www.sina.com两个种子链接。

如何定义一个链接的子节点？每个链接对应一个HTML页面或者其他文件（Word、Excel、PDF、JPG等），在这些文件中，只有HTML页面有相应的子节点，这些子节点就是HTML页面上对应的超链接。例如在www.lietu.com页面中（见图1.4），“招聘”“网址”“更多”还有页面下方的“搜索产品”“技术文档”“成功案例”“猎兔新闻”“联系猎兔”“关于我们”以及ENGLISH等都是www.lietu.com的子节点。这些子节点本身又是一个链接。对于非HTML文档，比如Excel文件等，则不能从中提取超链接，因此，可以看作是图的“终端”节点，就好像图1.3中的B、C、D、I、G等节点一样。

图1.4 猎兔搜索主页

整个的宽度优先爬虫过程就是从一系列的种子节点开始，把这些网页中的子节点（也就是超链接）提取出来，放入队列中依次进行抓取。被处理过的链接需要放入一张表（通常称为Visited表）中。每次新处理一个链接之前，需要查看这个链接是否已经存在于Visited表中。如果存在，证明链接已经处理过，跳过，不做处理，否则进行下一步处理。实际的过程如图1.5所示。

图1.5 宽度优先爬虫过程

图1.5中，初始的URL地址是爬虫系统中提供的种子URL（一般在系统的配置文件中指定）。当解析这些种子URL所表示的网页时，会产生新的URL（比如从页面中的<a href="http://www.admin.com"中提取出http://www.admin.com这个链接）。然后进行以下工作。

（1）把解析出的链接和Visited表中的链接进行比较，若Visited表中不存在此链接，表示其未被访问过。

（2）把链接放入TODO表中。

（3）处理完毕后，再次从TODO表中取得一条链接，直接放入Visited表中。

（4）针对这个链接所表示的网页，继续上述过程。如此循环往复。

表1.3显示了对图1.3所示的页面的爬取过程。

表1.3 网络爬取

宽度优先遍历是爬虫中使用最广泛的一种爬虫策略，之所以使用宽度优先搜索策略，主要原因有以下三点。

● 重要的网页往往离种子比较近，例如我们打开新闻网站的时候常常是最热门的新闻，随着不断地深入冲浪，所看到网页的重要性越来越低。

● 万维网的实际深度最多能达到17层，到达某个网页总存在一条很短的路径。宽度优先遍历会以最快的速度到达这个网页。

● 宽度优先有利于多爬虫的合作抓取，多爬虫合作通常先抓取站内链接，抓取的封闭性很强。

这一小节详细讲述了宽度优先遍历互联网的方法。下一节将给出一个详细的例子来说明如何实现这种方法。

1.2.3 Java宽度优先爬虫示例

本节使用Java实现一个简易的爬虫。其中用到了HttpClient和JSoup两个开源工具包。HttpClient的内容我们之前已经做过详细阐述。为了便于读者理解，这里给出示例程序的结构，如图1.6所示。

图1.6 爬虫示例程序结构

首先，需要定义图1.6中所描述的“URL队列”。这里使用一个LinkedList来实现这个队列。

Queue类：

/**
 * 队列，保存将要访问的URL
 */
public class Queue {
    //使用链表实现队列
    private LinkedList queue = new LinkedList();
       //入队列
    public void enQueue(Object t) {
        queue.addLast(t);
    }
       //出队列
    public Object deQueue() {
        return queue.removeFirst();
    }
    //判断队列是否为空
    public boolean isQueueEmpty() {
        return queue.isEmpty();
    }
    //判断队列是否包含t
    public boolean contians(Object t) {
        return queue.contains(t);
    }

    public boolean empty() {
        return queue.isEmpty();
    }

}

除了URL队列之外，在爬虫过程中还需要一个数据结构来记录已经访问过的URL。每当要访问一个URL的时候，首先在这个数据结构中进行查找，如果当前的URL已经存在，则丢弃它。这个数据结构要有以下两个特点。

● 结构中保存的URL不能重复。

● 能够快速地查找（实际系统中URL的数目非常多，因此要考虑查找性能）。

针对以上两点，我们选择HashSet作为存储结构。

LinkQueue类：

public class LinkQueue {
    //已访问的URL 集合
    private static Set visitedUrl = new HashSet();
    //待访问的URL 集合
    private static Queue unVisitedUrl = new Queue();
    //获得URL队列
    public static Queue getUnVisitedUrl() {
        return unVisitedUrl;
    }
    //添加到访问过的URL队列中
    public static void addVisitedUrl(String url) {
        visitedUrl.add(url);
    }
    //移除访问过的URL
    public static void removeVisitedUrl(String url) {
        visitedUrl.remove(url);
    }
    //未访问的URL出队列
    public static Object unVisitedUrlDeQueue() {
        return unVisitedUrl.deQueue();
    }
    // 保证每个 URL 只被访问一次
    public static void addUnvisitedUrl(String url) {
        if (url != null && !url.trim().equals("")
          && !visitedUrl.contains(url)
                && !unVisitedUrl.contians(url))
            unVisitedUrl.enQueue(url);
    }
    //获得已经访问的URL数目
    public static int getVisitedUrlNum() {
        return visitedUrl.size();
    }
    //判断未访问的URL队列是否为空
    public static boolean unVisitedUrlsEmpty() {
        return unVisitedUrl.empty();
    }

}

下面的代码详细说明了网页下载并处理的过程。和1.1节讲述的内容相比，它考虑了更多的方面，比如如何存储网页、设置请求超时策略等。

DownLoadFile类：

public class DownLoadFile {
    /**
     * 根据 URL 和网页类型生成需要保存的网页的文件名，去除 URL 中的非文件名字符
     */
    public String getFileNameByUrl(String url,String contentType)
    {
        //移除HTTP
        url=url.substring(7);
        //text/html类型
        if(contentType.indexOf("html")!=-1)
        {
            url= url.replaceAll("[\\?/:*|<>\"]", "_")+".html";
            return url;
        }
        //如application/pdf类型
        else
        {
          return url.replaceAll("[\\?/:*|<>\"]", "_")+"."+
              contentType.substring(contentType.lastIndexOf("/")+1);
        }
    }
     /**
     * 保存网页字节数组到本地文件，filePath 为要保存的文件的相对地址
     */
    private void saveToLocal(byte[] data, String filePath) {
        try {
            DataOutputStream out = new DataOutputStream(new
             FileOutputStream(new File(filePath)));
            for (int i = 0; i < data.length; i++)
                out.write(data[i]);
            out.flush();
            out.close();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }
    //下载 URL 指向的网页
    public String downloadFile(String url) {
        String filePath = null;
        //1.生成 HttpClinet 对象并设置参数
        HttpClient httpClient = new HttpClient();
        // 设置 HTTP 连接超时 5s
        httpClient.getHttpConnectionManager().getParams()
         .setConnectionTimeout(5000);
        //2.生成 GetMethod 对象并设置参数
        GetMethod getMethod = new GetMethod(url);
        // 设置 get 请求超时 5s
        getMethod.getParams().setParameter(HttpMethodParams.SO_TIMEOUT, 5000);
        // 设置请求重试处理
    getMethod.getParams().setParameter(HttpMethodParams.RETRY_HANDLER,
            new DefaultHttpMethodRetryHandler());

        // 3.执行 HTTP GET 请求
        try {
            int statusCode = httpClient.executeMethod(getMethod);
            // 判断访问的状态码
            if (statusCode != HttpStatus.SC_OK) {
                System.err.println("Method failed: " + getMethod.getStatusLine());
                filePath = null;
            }

            // 4.处理 HTTP 响应内容
            byte[] responseBody = getMethod.getResponseBody();// 读取为字节数组
            // 根据网页 URL 生成保存时的文件名
            filePath = "temp\\"
                    + getFileNameByUrl(url, getMethod.getResponseHeader(
                        "Content-Type").getValue());
            saveToLocal(responseBody, filePath);
        } catch (HttpException e) {
            // 发生致命的异常，可能是协议不对或者返回的内容有问题
            System.out.println("Please check your provided http address!");
            e.printStackTrace();
        } catch (IOException e) {
            // 发生网络异常
            e.printStackTrace();
        } finally {
            // 释放连接
            getMethod.releaseConnection();
        }
        return filePath;
    }
}

接下来，演示如何从获得的网页中提取URL。Java有一个非常实用的开源工具包Html-Parser，它专门针对HTML页面进行处理，不仅能提取URL，还能提取文本以及你想要的任何内容。

HtmlParserTool类：

public class HtmlParserTool {
    // 获取一个网站上的链接，filter 用来过滤链接
    public static Set<String> extracLinks(String url, LinkFilter filter) {
        Set<String> links = new HashSet<String>();
        try {
            Parser parser = new Parser(url);
            parser.setEncoding("gb2312");
            // 过滤 <frame>标签的filter，用来提取 frame 标签里的src 属性            NodeFilter frameFilter = new NodeFilter() {
                public boolean accept(Node node) {
                    if (node.getText().startsWith("frame src=")) {
                        return true;
                    } else {
                        return false;
                }
            };
            // OrFilter 用来设置过滤 <a> 标签和 <frame> 标签
            OrFilter linkFilter = new OrFilter(new NodeClassFilter(
                LinkTag.class), frameFilter);
            // 得到所有经过过滤的标签
            NodeList list = parser.extractAllNodesThatMatch(linkFilter);
            for (int i = 0; i < list.size(); i++) {
                Node tag = list.elementAt(i);
                if (tag instanceof LinkTag)// <a> 标签
                {
                    LinkTag link = (LinkTag) tag;
                    String linkUrl = link.getLink();// URL
                    if (filter.accept(linkUrl))
                        links.add(linkUrl);
                } else// <frame> 标签
                {
                    // 提取 frame 里 src 属性的链接，如 <frame src="test.html">
                    String frame = tag.getText();
                    int start = frame.indexOf("src=");
                    frame = frame.substring(start);
                    int end = frame.indexOf(" ");
                    if (end == -1)
                        end = frame.indexOf(">");
                    String frameUrl = frame.substring(5, end - 1);
                    if (filter.accept(frameUrl))
                        links.add(frameUrl);
                }
            }
        } catch (ParserException e) {
            e.printStackTrace();
        }
        return links;
    }
}

最后来看看宽度爬虫的主程序。

MyCrawler类：

public class MyCrawler {
    /**
     * 使用种子初始化 URL 队列
     * @return
     * @param seeds 种子URL
     */
    private void initCrawlerWithSeeds(String[] seeds)
    {
        for(int i=0;i<seeds.length;i++)
            LinkQueue.addUnvisitedUrl(seeds[i]);
    }
    /**
     * 抓取过程
     * @return
     * @param seeds
     */
    public void crawling(String[] seeds)
    {   //定义过滤器，提取以http://www.lietu.com开头的链接
        LinkFilter filter = new LinkFilter(){
            public boolean accept(String url) {
                if(url.startsWith("http://www.lietu.com"))
                    return true;
                else
                    return false;
            }
        };
        //初始化 URL 队列
        initCrawlerWithSeeds(seeds);
        //循环条件：待抓取的链接不空且抓取的网页不多于1000
        while(!LinkQueue.unVisitedUrlsEmpty()
         &&LinkQueue.getVisitedUrlNum()<=1000)
        {
            //队头URL出队列
            String visitUrl=(String)LinkQueue.unVisitedUrlDeQueue();
            if(visitUrl==null)
                continue;
            DownLoadFile downLoader=new DownLoadFile();
            //下载网页
            downLoader.downloadFile(visitUrl);
            //该 URL 放入已访问的URL 中
            LinkQueue.addVisitedUrl(visitUrl);
            //提取出下载网页中的URL
             Set<String> links=HtmlParserTool.extracLinks(visitUrl,filter);
            //新的未访问的URL 入队
            for(String link:links)
            {
                LinkQueue.addUnvisitedUrl(link);
            }
        }
    }
    //main 方法入口
    public static void main(String[]args)
    {
        MyCrawler crawler = new MyCrawler();
        crawler.crawling(new String[]{"http://www.lietu.com"});
    }

}

上面的主程序使用了一个LinkFilter接口，并且实现为一个内部类。这个接口的目的是为了过滤提取出来的URL，使得程序中提取出来的URL只会和猎兔网站相关，而不会提取其他无关的网站。代码如下：

public interface LinkFilter {
    public boolean accept(String url);
}

1.2.4 带偏好的爬虫

有时，在URL队列中选择需要抓取的URL时，不一定按照队列“先进先出”的方式进行选择，而是把重要的URL先从队列中“挑”出来进行抓取。这种策略也称作“页面选择”（Page Selection）。这可以使有限的网络资源照顾到重要性高的网页。

那么哪些网页是重要性高的网页呢？

判断网页重要性的因素很多，主要有链接的欢迎度（知道链接的重要性了吧）、链接的重要度和平均链接深度、网站质量、历史权重等主要因素。

链接的欢迎度主要是由反向链接（backlinks，即指向当前URL的链接）的数量和质量决定的，我们定义为IB（P）。

链接的重要度是一个关于URL字符串的函数，仅仅考察字符串本身，比如认为“.com”和“home”的URL重要度比“.cc”和“map”高，我们定义为IL（P）。

平均链接深度，根据上面所分析的宽度优先的原则计算出全站的平均链接深度，然后认为距离种子站点越近的重要性越高，我们定义为ID（P）。

如果我们定义网页的重要性为I（P），那么，页面的重要度由下面的公式决定：

I（P）=X×IB（P）+Y×IL（P） （1.1）

其中，X和Y两个参数用来调整IB（P）和IL（P）所占比例的大小。ID（P）由宽度优先的遍历规则保证，因此不作为重要的指标函数。

如何实现最佳优先爬虫呢？最简单的方法是可以使用优先级队列来实现TODO表，并且把每个URL的重要性作为队列元素的优先级。这样，每次选出来扩展的URL就是具有最高重要性的网页。有关优先级队列的介绍，请参考1.2.5节的内容。

例如，假设图1.3中节点的重要性为D>B>C>A>E>F>I>G>H，则整个遍历过程如表1.4所示。

表1.4 带偏好的爬虫

1.2.5 Java带偏好的爬虫示例

在1.2.4节中我们已经指出，可以使用优先级队列（Priority Queue）来实现带偏好的爬虫。在深入讲解之前，我们首先介绍优先级队列。

优先级队列是一种特殊的队列，普通队列中的元素是先进先出的，而优先级队列则是根据进入队列中元素的优先级进行出队列操作。例如，操作系统的一些优先级进程管理等，都可以使用优先级队列。优先级队列有最小优先级队列和最大优先级队列两种。

理论上，优先级队列可以是任何一种数据结构，比如线性的或非线性的，也可以是有序的或无序的。针对有序的优先级队列而言，获取最小或最大的值是非常容易的，但是插入却非常困难；而对于无序的有衔接队列而言，插入是很容易的，但是获取最大或最小值是很麻烦的。根据以上的分析，可以使用“堆”这种折中的数据结构来实现优先级队列。

从JDK 1.5开始，Java提供了内置的支持优先级队列的数据结构——java.util.PriorityQueue。在前面的代码中，只要稍微修改一下就可以支持从URL队列中选择优先级高的URL。

LinkQueue类：

public class LinkQueue {
    //已访问的URL 集合
    private static Set visitedUrl = new HashSet();
    //待访问的URL 集合
    private static Queue unVisitedUrl = new PriorityQueue();

    //获得URL队列
    public static Queue getUnVisitedUrl() {
        return unVisitedUrl;
    }
    //添加到访问过的URL队列中
    public static void addVisitedUrl(String url) {
        visitedUrl.add(url);
    }
    //移除访问过的URL
    public static void removeVisitedUrl(String url) {
        visitedUrl.remove(url);
    }
    //未访问的URL出队列
    public static Object unVisitedUrlDeQueue() {
        return unVisitedUrl.poll();
    }

    // 保证每个 URL 只被访问一次
    public static void addUnvisitedUrl(String url) {
        if (url != null && !url.trim().equals("")
                && !visitedUrl.contains(url)
                && !unVisitedUrl.contains(url))
            unVisitedUrl.add(url);
    }
    //获得已经访问的URL数目
    public static int getVisitedUrlNum() {
        return visitedUrl.size();
    }
    //判断未访问的URL队列中是否为空
    public static boolean unVisitedUrlsEmpty() {
        return unVisitedUrl.isEmpty();
    }

}

在带偏好的爬虫里，队列元素的优先级是由URL的优先级确定的。关于如何确定URL的优先级，有一些专用的链接分析的方法，比如Google的PageRank和HITS算法。有关这些算法的内容，将在第8章详细介绍。

上一章目录下一章