資料結構思維 第十五章 爬取維基百科

第十五章 爬取維基百科

原文： 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

  添加元素，并且
• 向 Redis

  TermCounter

  添加元素。

這兩個都是常數時間的操作，是以推送

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

，這個方法應該：

• 如果 URL 已經被編入索引，它不應該再次索引，并應該傳回

  null

• 否則它應該使用

  WikiFetcher.fetchWikipedia

  讀取頁面内容，從 Web 中讀取目前内容。
• 然後，它應該對頁面進行索引，将連結添加到隊列，并傳回其索引的頁面的 URL。

WikiCrawlerTest

加載具有大約

200

個連結的隊列，然後調用

crawl

三次。每次調用後，它将檢查隊列的傳回值和新長度。

當你的爬蟲按規定工作時，此測試應通過。祝你好運！