数据结构思维笔记（十六）爬取百度百科

1.基于Redis的索引器

在我的解决方案中，我们在 Redis 中存储两种结构：

对于每个检索词，我们有一个URLSet，它是一个 Redis 集合，包含检索词的 URL。
对于每个网址，我们有一个TermCounter，这是一个 Redis 哈希表，将每个检索词映射到它出现的次数。

在JedisIndex中，我提供了一个方法，它可以接受一个检索词并返回 Redis 中它的URLSet的键：

 private String urlSetKey(String url) {
        return "URLSet:"+url;
 }

以及一个方法，接受 URL 并返回 Redis 中它的TermCounter的键：

private String termCounterKey(String term) {
        return "TermCounter:"+term;
}

这里是indexPage的实现（索引化一个界面）:

	public void indexPage(String url, Elements elements) {
        System.out.println("Indexing..." + url);

        TermCounter tc = new TermCounter(url);
        tc.processElements(elements);

        pushTermCounterToRedis(tc);
    }

为了索引页面，我们：

为页面内容创建一个 Java 的TermCounter，使用上一个练习中的代码。
将TermCounter的内容推送到 Redis。

以下是将TermCounter的内容推送到 Redis 的新代码：

    public List<Object> pushTermCounterToRedis(TermCounter tc) {
        Transaction t = jedis.multi();

        String url = tc.getLabel();
        String redisKey = urlSetKey(url);
        t.del(redisKey);

        for (String term: tc.keySet()) {
            Integer count = tc.get(term);
            t.hset(redisKey, term, count.toString());
            t.sadd(termCounterKey(term),url);
        }
        List<Object> res = t.exec();
        return res;
    }

该方法使用Transaction来收集操作，并将它们一次性发送到服务器，这比发送一系列较小操作要快得多。

它遍历TermCounter中的检索词。对于每一个，它：

在 Redis 上寻找或者创建TermCounter，然后为新的检索词添加字段。
在 Redis 上寻找或创建URLSet，然后添加当前的 URL。

如果页面已被索引，则TermCounter在推送新内容之前删除旧页面。

这里还需要getCounts，它需要一个检索词，并从该词出现的每个网址返回一个映射。这是我的解决方案：

    public Map<String, Integer> getCounts(String term) {
        Map<String, Integer> map = new HashMap<String, Integer>();
        Set<String> urls = getURLs(term);
        for (String url: urls) {
            Integer count = getCount(url, term);
            map.put(url, count);
        }
        return map;
    }

此方法使用两种辅助方法：

getURLs接受检索词并返回该字词出现的网址集合。
getCount接受 URL 和检索词，并返回该检索词在给定 URL 处显示的次数。

以下是实现：

    public Set<String> getURLs(String term) {
        Set<String> set = jedis.smembers(termCounterKey(term));
        return set;
    }

    public Integer getCount(String url, String term) {
        String redisKey = urlSetKey(url);
        String count = jedis.hget(redisKey, term);
        return new Integer(count);
    }

2.查找的分析

假设我们索引了N个页面，并发现了M个唯一的检索词。检索词的查询需要多长时间？在继续之前，先考虑一下你的答案。

要查找一个检索词，我们调用getCounts，其中：

创建映射。
调用getURLs来获取 URL 的集合。
对于集合中的每个 URL，调用getCount并将条目添加到HashMap。

getURLs所需时间与包含检索词的网址数成正比。对于罕见的检索词，这可能是一个很小的数字，但是对于常见检索词，它可能和N一样大。

在循环中，我们调用了getCount，它在 Redis 上寻找TermCounter，查找一个检索词，并向HashMap添加一个条目。那些都是常数时间的操作，所以在最坏的情况下，getCounts的整体复杂度是O(N)。然而实际上，运行时间正比于包含检索词的页面数量，通常比N小得多。

这个算法根据复杂性是有效的，但是它非常慢，因为它向 Redis 发送了许多较小的操作。

解决办法：利用事务，解决这个问题：

    public Map<String,Integer> getCountsFaster(String term) {
        //将set集合转换为list,以便每次都有相同的遍历顺序
        List<String> urls = new ArrayList<String>();
        urls.addAll(getUrls(term));

        // 创建一个事务执行所有查询
        Transaction t = jedis.multi();
        for (String url: urls) {
            String redisKey = urlSetKey(url);
            t.hget(redisKey,term);
        }
        List<Object> res = t.exec();

        //遍历结果，制造出map
        Map<String,Integer> map = new HashMap<String, Integer>();
        int i=0;
        for (String url: urls) {
            System.out.println(url);
            Integer count = new Integer((String)res.get(i++));
            map.put(url,count);
        }
        return map;
    }

3.索引的分析

使用我们设计的数据结构，页面的索引需要多长时间？再次考虑你的答案，然后再继续。

为了索引页面，我们遍历其 DOM 树，找到所有TextNode对象，并将字符串拆分成检索词。这一切都与页面上的单词数成正比。

对于每个检索词，我们在HashMap中增加一个计数器，这是一个常数时间的操作。所以创建TermCounter的所需时间与页面上的单词数成正比。

将TermCounter推送到 Redis ，需要删除TermCounter，对于唯一检索词的数量是线性的。那么对于每个检索词，我们必须：

向URLSet添加元素，并且
向 RedisTermCounter添加元素。

这两个都是常数时间的操作，所以推送TermCounter的总时间对于唯一检索词的数量是线性的。

总之，TermCounter的创建与页面上的单词数成正比。向 Redis 推送TermCounter与唯一检索词的数量成正比。

由于页面上的单词数量通常超过唯一检索词的数量，因此整体复杂度与页面上的单词数成正比。理论上，一个页面可能包含索引中的所有检索词，因此最坏的情况是O(M)，但实际上我们并不期待看到更糟糕的情况。

这个分析提出了一种提高效率的方法：我们应该避免索引很常见的词语（停止词）。首先，他们占用了大量的时间和空间，因为它们出现在几乎每一个URLSet和TermCounter中。此外，它们不是很有用，因为它们不能帮助识别相关页面。

4.图的遍历

如果你在第七章中完成了“到达哲学”练习，你已经有了一个程序，它读取页面，找到第一个链接，使用链接加载下一页，然后重复。这个程序是一种专用的爬虫，但是当人们说“网络爬虫”时，他们通常意味着一个程序：

加载起始页面并对内容进行索引，查找页面上的所有链接，并将链接的 URL 添加到集合中通过收集，加载和索引页面，以及添加新的 URL，来按照它的方式工作。如果它找到已经被索引的 URL，会跳过它。

你可以将 Web 视为图，其中每个页面都是一个节点，每个链接都是从一个节点到另一个节点的有向边。

从源节点开始，爬虫程序遍历该图，访问每个可达节点一次。

我们用于存储 URL 的集合决定了爬虫程序执行哪种遍历：

如果它是先进先出（FIFO）的队列，则爬虫程序将执行广度优先遍历。
如果它是后进先出（LIFO）的栈，则爬虫程序将执行深度优先遍历。
更通常来说，集合中的条目可能具有优先级。例如，我们可能希望对尚未编入索引的页面给予较高的优先级。

5.构建WikiCrawler

构建这个类的主要目的为爬取百度百科，并将爬取过的数据持久化，方便日后查询

需要使用到的类：

JedisMaker.java
WikiFetcher.java
TermCounter.java
WikiNodeIterable.java

这里提供WikiCrawler的起始代码：

public class WikiCrawler {

    public final String source;
    private JedisIndex index;
    private Queue<String> queue = new LinkedList<String>();
    final static WikiFetcher wf = new WikiFetcher();

    public WikiCrawler(String source, JedisIndex index) {
        this.source = source;
        this.index = index;
        queue.offer(source);
    }

    public int queueSize() {
        return queue.size();
    }

这里边的变量代表为：

source是我们开始抓取的网址。
index是JedisIndex，连接Redis做数据持久化，结果应该放进这里。
queue是LinkedList，这里面我们跟踪已发现但尚未编入索引的网址。
wf是WikiFetcher，我们用来读取和解析网页。

下面是crawl()方法：

   public String crawl(boolean testing) throws IOException {
        if (queue.isEmpty()) {
            return null;
        }
        String url = queue.poll();
        System.out.println("Crawling..."+ url);

        if (testing==false && index.isIndexed(url)) {
            System.out.println("Already indexed.");
            return null;
        }

        Elements para;
        if (testing) {
            para = wf.readWikiPedia(url);
        } else {
            para = wf.fetchWikiPedia(url);
        }
        index.indexPage(url,para);
        queueInternalLinks(para);
        return url;
    }

该方法主要用来获取队列中的Url地址并索引化

当传递参数 testing为true时:

以 FIFO 的顺序从队列中选择并移除一个 URL。
使用WikiFetcher.readWikipedia读取页面的内容
它应该索引页面，而不管它们是否已经被编入索引。
它应该找到页面上的所有内部链接，并按他们出现的顺序将它们添加到队列中。
它应该返回其索引的页面的 URL

当传递参数为false时

以 FIFO 的顺序从队列中选择并移除一个 URL。
如果 URL 已经被编入索引，它不应该再次索引，并应该返回null。
否则它应该使用WikiFetcher.fetchWikipedia读取页面内容，从 Web 中读取当前内容。
然后，它应该对页面进行索引，将链接添加到队列，并返回其索引的页面的 URL。

下面提供一下其中用到的queueInternalLinks()

该方法的主要作用为解析para,并将内部链接添加到队列

下面是该方法的具体实现：

    /**
     * @Author Ragty
     * @Description 解析para,并将内部链接添加到队列
     * @Date 11:38 2019/5/22
     **/
    public void queueInternalLinks(Elements paras) {
        for (Element para: paras) {
            queueInternalLinks(para);
        }
    }


    /**
     * @Author Ragty
     * @Description 单个段落解析并添加
     * @Date 11:39 2019/5/22
     **/
    private void queueInternalLinks(Element para) {
        Elements elts = para.select("a[href]");
        for (Element element: elts) {
            String relURL = element.attr("href");

            // need to fix
            if (relURL.startsWith("/item/")) {
                String absURL = "https://baike.baidu.com" + relURL;
                queue.offer(absURL);
            }
        }
    }