第十五章爬取维基百科

原文：Chapter 15 Crawling Wikipedia

译者：飞龙

协议：CC BY-NC-SA 4.0

自豪地采用谷歌翻译

在本章中，我展示了上一个练习的解决方案，并分析了 Web 索引算法的性能。然后我们构建一个简单的 Web 爬虫。

15.1 基于 Redis 的索引器

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

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

我们在上一章讨论了这些数据类型。你还可以在 http://thinkdast.com/redistypes 上阅读 Redis Set和Hash`的信息

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

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

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

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

这里是indexPage的实现。

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

    // make a TermCounter and count the terms in the paragraphs
    TermCounter tc = new TermCounter(url);
    tc.processElements(paragraphs);

    // push the contents of the TermCounter to Redis
    pushTermCounterToRedis(tc);
}

为了索引页面，我们：

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

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

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

    String url = tc.getLabel();
    String hashname = termCounterKey(url);

    // if this page has already been indexed, delete the old hash
    t.del(hashname);

    // for each term, add an entry in the TermCounter and a new
    // member of the index
    for (String term: tc.keySet()) {
        Integer count = tc.get(term);
        t.hset(hashname, term, count.toString());
        t.sadd(urlSetKey(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(urlSetKey(term));
        return set;
    }

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

由于我们设计索引的方式，这些方法简单而高效。

15.2 查找的分析

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

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

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

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

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

这个算法根据复杂性是有效的，但是它非常慢，因为它向 Redis 发送了许多较小的操作。你可以使用Transaction来加快速度。你可能留作一个练习，或者你可以在RedisIndex.java中查看我的解决方案。

15.3 索引的分析

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

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

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

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

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

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

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

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

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

大多数搜索引擎避免索引常用单词，这在本文中称为停止词（http://thinkdast.com/stopword）。

15.4 图的遍历

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

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

你可以将 Web 视为图，其中每个页面都是一个节点，每个链接都是从一个节点到另一个节点的有向边。如果你不熟悉图，可以阅读 http://thinkdast.com/graph。

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

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

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

你可以在 http://thinkdast.com/graphtrav 上阅读图的遍历的更多信息。

15.5 练习 12

现在是时候写爬虫了。在本书的仓库中，你将找到此练习的源文件：

WikiCrawler.java，包含你的爬虫的其实代码。
WikiCrawlerTest.java，包含WikiCrawler的测试代码。
JedisIndex.java，这是我以前的练习的解决方案。

你还需要一些我们以前练习中使用过的辅助类：

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

在运行JedisMaker之前，你必须提供一个文件，关于你的 Redis 服务器信息。如果你在上一个练习中这样做，你应该全部配置好了。否则，你可以在 14.3 节中找到说明。

运行ant build来编译源文件，然后运行ant JedisMaker来确保它配置为连接到你的 Redis 服务器。

现在运行ant WikiCrawlerTest。它应该失败，因为你有工作要做！

这是我提供的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，结果应该放进这里。
queue是LinkedList，这里面我们跟踪已发现但尚未编入索引的网址。
wf是WikiFetcher，我们用来读取和解析网页。

你的工作是填写crawl。这是原型：

public String crawl(boolean testing) throws IOException {}

当这个方法在WikiCrawlerTest中调用时，testing参数为true，否则为false。

如果testing是true，crawl方法应该：

以 FIFO 的顺序从队列中选择并移除一个 URL。
使用WikiFetcher.readWikipedia读取页面的内容，它读取仓库中包含的，页面的缓存副本来进行测试（如果维基百科的版本更改，则避免出现问题）。
它应该索引页面，而不管它们是否已经被编入索引。
它应该找到页面上的所有内部链接，并按他们出现的顺序将它们添加到队列中。“内部链接”是指其他维基百科页面的链接。
它应该返回其索引的页面的 URL。

如果testing是false，这个方法应该：

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

WikiCrawlerTest加载具有大约200个链接的队列，然后调用crawl三次。每次调用后，它将检查队列的返回值和新长度。

当你的爬虫按规定工作时，此测试应通过。祝你好运！

第十五章爬取维基百科

第十五章爬取维基百科

15.1 基于 Redis 的索引器

15.2 查找的分析

15.3 索引的分析

15.4 图的遍历

15.5 练习 12

results matching ""

No results matching ""

第十五章 爬取维基百科

15.1 基于 Redis 的索引器

15.2 查找的分析

15.3 索引的分析

15.4 图的遍历

15.5 练习 12

results matching ""

No results matching ""

第十五章爬取维基百科