# 第十五章 爬取維基百科
> 原文：[Chapter 15 Crawling Wikipedia](http://greenteapress.com/thinkdast/html/thinkdast016.html)
> 譯者：[飛龍](https://github.com/wizardforcel)
> 協議：[CC BY-NC-SA 4.0](http://creativecommons.org/licenses/by-nc-sa/4.0/)
> 自豪地采用[谷歌翻譯](https://translate.google.cn/)
在本章中，我展示了上一個練習的解決方案，并分析了 Web 索引算法的性能。然后我們構建一個簡單的 Web 爬蟲。
## 15.1 基于 Redis 的索引器
在我的解決方案中，我們在 Redis 中存儲兩種結構：
+ 對于每個檢索詞，我們有一個`URLSet`，它是一個 Redis 集合，包含檢索詞的 URL。
+ 對于每個網址，我們有一個`TermCounter`，這是一個 Redis 哈希表，將每個檢索詞映射到它出現的次數。
我們在上一章討論了這些數據類型。你還可以在 <http://thinkdast.com/redistypes> 上閱讀 Redis `Set和`Hash`的信息
在`JedisIndex`中，我提供了一個方法，它可以接受一個檢索詞并返回 Redis 中它的`URLSet`的鍵：
```java
private String urlSetKey(String term) {
return "URLSet:" + term;
}
```
以及一個方法，接受 URL 并返回 Redis 中它的`TermCounter`的鍵。
```java
private String termCounterKey(String url) {
return "TermCounter:" + url;
}
```
這里是`indexPage`的實現。
```java
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 的新代碼：
```java
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`，它需要一個檢索詞，并從該詞出現的每個網址返回一個映射。這是我的解決方案：
```java
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 處顯示的次數。
以下是實現：
```java
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`類的起始：
```java
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`。這是原型：
```java
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`三次。每次調用后，它將檢查隊列的返回值和新長度。
當你的爬蟲按規定工作時，此測試應通過。祝你好運！
