第十五章 爬取維基百科

原文：Chapter 15 Crawling Wikipedia

譯者：飛龍

協(xié)議：CC BY-NC-SA 4.0

自豪地采用谷歌翻譯

在本章中万矾，我展示了上一個(gè)練習(xí)的解決方案谤民，并分析了 Web 索引算法的性能。然后我們構(gòu)建一個(gè)簡單的 Web 爬蟲膜毁。

15.1 基于 Redis 的索引器

在我的解決方案中昭卓，我們?cè)?Redis 中存儲(chǔ)兩種結(jié)構(gòu)：

• 對(duì)于每個(gè)檢索詞，我們有一個(gè)URLSet瘟滨，它是一個(gè) Redis 集合候醒，包含檢索詞的 URL。
• 對(duì)于每個(gè)網(wǎng)址杂瘸，我們有一個(gè)TermCounter倒淫，這是一個(gè) Redis 哈希表，將每個(gè)檢索詞映射到它出現(xiàn)的次數(shù)败玉。

我們?cè)谏弦徽掠懻摿诉@些數(shù)據(jù)類型敌土。你還可以在 http://thinkdast.com/redistypes 上閱讀 Redis Set和Hash`的信息

在JedisIndex中，我提供了一個(gè)方法运翼，它可以接受一個(gè)檢索詞并返回 Redis 中它的URLSet的鍵：

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

以及一個(gè)方法返干，接受 URL 并返回 Redis 中它的TermCounter的鍵。

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

這里是indexPage的實(shí)現(xiàn)血淌。

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);
}

為了索引頁面矩欠，我們：

• 為頁面內(nèi)容創(chuàng)建一個(gè) Java 的TermCounter，使用上一個(gè)練習(xí)中的代碼悠夯。
• 將TermCounter的內(nèi)容推送到 Redis癌淮。

以下是將TermCounter的內(nèi)容推送到 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來收集操作，并將它們一次性發(fā)送到服務(wù)器疗疟，這比發(fā)送一系列較小操作要快得多该默。

它遍歷TermCounter中的檢索詞。對(duì)于每一個(gè)策彤，它：

• 在 Redis 上尋找或者創(chuàng)建TermCounter栓袖，然后為新的檢索詞添加字段。
• 在 Redis 上尋找或創(chuàng)建URLSet店诗，然后添加當(dāng)前的 URL裹刮。

如果頁面已被索引，則TermCounter在推送新內(nèi)容之前刪除舊頁面 庞瘸。

新的頁面的索引就是這樣捧弃。

練習(xí)的第二部分要求你編寫getCounts，它需要一個(gè)檢索詞，并從該詞出現(xiàn)的每個(gè)網(wǎng)址返回一個(gè)映射违霞。這是我的解決方案：

    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接受檢索詞并返回該字詞出現(xiàn)的網(wǎng)址集合嘴办。
• getCount接受 URL 和檢索詞，并返回該術(shù)語在給定 URL 處顯示的次數(shù)买鸽。

以下是實(shí)現(xiàn)：

    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);
    }

由于我們?cè)O(shè)計(jì)索引的方式涧郊，這些方法簡單而高效。

15.2 查找的分析

假設(shè)我們索引了N個(gè)頁面眼五，并發(fā)現(xiàn)了M個(gè)唯一的檢索詞妆艘。檢索詞的查詢需要多長時(shí)間？在繼續(xù)之前看幼，先考慮一下你的答案批旺。

要查找一個(gè)檢索詞，我們調(diào)用getCounts诵姜，其中：

• 創(chuàng)建映射汽煮。
• 調(diào)用getURLs來獲取 URL 的集合。
• 對(duì)于集合中的每個(gè) URL茅诱，調(diào)用getCount并將條目添加到HashMap逗物。

getURLs所需時(shí)間與包含檢索詞的網(wǎng)址數(shù)成正比。對(duì)于罕見的檢索詞瑟俭，這可能是一個(gè)很小的數(shù)字翎卓，但是對(duì)于常見檢索詞，它可能和N一樣大摆寄。

在循環(huán)中失暴，我們調(diào)用了getCount，它在 Redis 上尋找TermCounter微饥，查找一個(gè)檢索詞逗扒，并向HashMap添加一個(gè)條目。那些都是常數(shù)時(shí)間的操作欠橘，所以在最壞的情況下矩肩，getCounts的整體復(fù)雜度是O(N)。然而實(shí)際上肃续，運(yùn)行時(shí)間正比于包含檢索詞的頁面數(shù)量黍檩，通常比N小得多。

這個(gè)算法根據(jù)復(fù)雜性是有效的始锚，但是它非常慢刽酱，因?yàn)樗?Redis 發(fā)送了許多較小的操作。你可以使用Transaction來加快速度 瞧捌。你可能留作一個(gè)練習(xí)棵里，或者你可以在RedisIndex.java中查看我的解決方案润文。

15.3 索引的分析

使用我們?cè)O(shè)計(jì)的數(shù)據(jù)結(jié)構(gòu)，頁面的索引需要多長時(shí)間殿怜？再次考慮你的答案典蝌，然后再繼續(xù)。

為了索引頁面稳捆，我們遍歷其 DOM 樹赠法，找到所有TextNode對(duì)象，并將字符串拆分成檢索詞乔夯。這一切都與頁面上的單詞數(shù)成正比。

對(duì)于每個(gè)檢索詞款侵，我們?cè)?code>HashMap中增加一個(gè)計(jì)數(shù)器末荐，這是一個(gè)常數(shù)時(shí)間的操作。所以創(chuàng)建TermCounter的所需時(shí)間與頁面上的單詞數(shù)成正比新锈。

將TermCounter推送到 Redis 甲脏，需要?jiǎng)h除TermCounter，對(duì)于唯一檢索詞的數(shù)量是線性的妹笆。那么對(duì)于每個(gè)檢索詞块请，我們必須：

• 向URLSet添加元素，并且
• 向 RedisTermCounter添加元素拳缠。

這兩個(gè)都是常數(shù)時(shí)間的操作墩新，所以推送TermCounter的總時(shí)間對(duì)于唯一檢索詞的數(shù)量是線性的。

總之窟坐，TermCounter的創(chuàng)建與頁面上的單詞數(shù)成正比海渊。向 Redis 推送TermCounter與唯一檢索詞的數(shù)量成正比。

由于頁面上的單詞數(shù)量通常超過唯一檢索詞的數(shù)量哲鸳，因此整體復(fù)雜度與頁面上的單詞數(shù)成正比臣疑。理論上，一個(gè)頁面可能包含索引中的所有檢索詞徙菠，因此最壞的情況是O(M)讯沈，但實(shí)際上我們并不期待看到更糟糕的情況。

這個(gè)分析提出了一種提高效率的方法：我們應(yīng)該避免索引很常見的詞語婿奔。首先缺狠，他們占用了大量的時(shí)間和空間，因?yàn)樗鼈兂霈F(xiàn)在幾乎每一個(gè)URLSet和TermCounter中脸秽。此外儒老，它們不是很有用，因?yàn)樗鼈儾荒軒椭R(shí)別相關(guān)頁面记餐。

大多數(shù)搜索引擎避免索引常用單詞驮樊，這在本文中稱為停止詞（http://thinkdast.com/stopword）。

15.4 圖的遍歷

如果你在第七章中完成了“到達(dá)哲學(xué)”練習(xí)，你已經(jīng)有了一個(gè)程序囚衔，它讀取維基百科頁面挖腰，找到第一個(gè)鏈接，使用鏈接加載下一頁练湿，然后重復(fù)猴仑。這個(gè)程序是一種專用的爬蟲，但是當(dāng)人們說“網(wǎng)絡(luò)爬蟲”時(shí)肥哎，他們通常意味著一個(gè)程序：

加載起始頁面并對(duì)內(nèi)容進(jìn)行索引辽俗，
查找頁面上的所有鏈接，并將鏈接的 URL 添加到集合中
通過收集篡诽，加載和索引頁面崖飘，以及添加新的 URL，來按照它的方式工作杈女。
如果它找到已經(jīng)被索引的 URL朱浴，會(huì)跳過它。

你可以將 Web 視為圖达椰，其中每個(gè)頁面都是一個(gè)節(jié)點(diǎn)翰蠢，每個(gè)鏈接都是從一個(gè)節(jié)點(diǎn)到另一個(gè)節(jié)點(diǎn)的有向邊。如果你不熟悉圖啰劲，可以閱讀 http://thinkdast.com/graph梁沧。

從源節(jié)點(diǎn)開始摹闽，爬蟲程序遍歷該圖拜姿，訪問每個(gè)可達(dá)節(jié)點(diǎn)一次评抚。

我們用于存儲(chǔ) URL 的集合決定了爬蟲程序執(zhí)行哪種遍歷：

• 如果它是先進(jìn)先出（FIFO）的隊(duì)列沃斤，則爬蟲程序?qū)?zhí)行廣度優(yōu)先遍歷喂窟。
• 如果它是后進(jìn)先出（LIFO）的棧踢关，則爬蟲程序?qū)?zhí)行深度優(yōu)先遍歷育特。
• 更通常來說芽死，集合中的條目可能具有優(yōu)先級(jí)啃憎。例如芝囤，我們可能希望對(duì)尚未編入索引的頁面給予較高的優(yōu)先級(jí)。

你可以在 http://thinkdast.com/graphtrav 上閱讀圖的遍歷的更多信息 辛萍。

15.5 練習(xí) 12

現(xiàn)在是時(shí)候?qū)懪老x了悯姊。在本書的倉庫中，你將找到此練習(xí)的源文件：

• WikiCrawler.java贩毕，包含你的爬蟲的其實(shí)代碼悯许。
• WikiCrawlerTest.java，包含WikiCrawler的測(cè)試代碼辉阶。
• JedisIndex.java先壕，這是我以前的練習(xí)的解決方案瘩扼。

你還需要一些我們以前練習(xí)中使用過的輔助類：

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

在運(yùn)行JedisMaker之前，你必須提供一個(gè)文件垃僚，關(guān)于你的 Redis 服務(wù)器信息集绰。如果你在上一個(gè)練習(xí)中這樣做，你應(yīng)該全部配置好了谆棺。否則栽燕，你可以在 14.3 節(jié)中找到說明。

運(yùn)行ant build來編譯源文件改淑，然后運(yùn)行ant JedisMaker來確保它配置為連接到你的 Redis 服務(wù)器碍岔。

現(xiàn)在運(yùn)行ant WikiCrawlerTest。它應(yīng)該失敗朵夏，因?yàn)槟阌泄ぷ饕觯?/p>

這是我提供的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();
    }

實(shí)例變量是：

• source是我們開始抓取的網(wǎng)址付秕。
• index是JedisIndex，結(jié)果應(yīng)該放進(jìn)這里侍郭。
• queue是LinkedList，這里面我們跟蹤已發(fā)現(xiàn)但尚未編入索引的網(wǎng)址掠河。
• wf是WikiFetcher亮元，我們用來讀取和解析網(wǎng)頁。

你的工作是填寫crawl唠摹。這是原型：

public String crawl(boolean testing) throws IOException {}

當(dāng)這個(gè)方法在WikiCrawlerTest中調(diào)用時(shí)爆捞，testing參數(shù)為true，否則為false勾拉。

如果testing是true煮甥，crawl方法應(yīng)該：

• 以 FIFO 的順序從隊(duì)列中選擇并移除一個(gè) URL。
• 使用WikiFetcher.readWikipedia讀取頁面的內(nèi)容藕赞，它讀取倉庫中包含的成肘，頁面的緩存副本來進(jìn)行測(cè)試（如果維基百科的版本更改，則避免出現(xiàn)問題）斧蜕。
• 它應(yīng)該索引頁面双霍，而不管它們是否已經(jīng)被編入索引。
• 它應(yīng)該找到頁面上的所有內(nèi)部鏈接批销，并按他們出現(xiàn)的順序?qū)⑺鼈兲砑拥疥?duì)列中洒闸。“內(nèi)部鏈接”是指其他維基百科頁面的鏈接均芽。
• 它應(yīng)該返回其索引的頁面的 URL丘逸。

如果testing是false，這個(gè)方法應(yīng)該：

• 以 FIFO 的順序從隊(duì)列中選擇并移除一個(gè) URL掀宋。
• 如果 URL 已經(jīng)被編入索引深纲，它不應(yīng)該再次索引仲锄，并應(yīng)該返回null。
• 否則它應(yīng)該使用WikiFetcher.fetchWikipedia讀取頁面內(nèi)容囤萤，從 Web 中讀取當(dāng)前內(nèi)容昼窗。
• 然后，它應(yīng)該對(duì)頁面進(jìn)行索引涛舍，將鏈接添加到隊(duì)列澄惊，并返回其索引的頁面的 URL。

WikiCrawlerTest加載具有大約200個(gè)鏈接的隊(duì)列富雅，然后調(diào)用crawl三次掸驱。每次調(diào)用后，它將檢查隊(duì)列的返回值和新長度没佑。

當(dāng)你的爬蟲按規(guī)定工作時(shí)毕贼，此測(cè)試應(yīng)通過。祝你好運(yùn)蛤奢！