? 莊子曾說：“吾生也有涯，而知也無涯，以有涯隨無涯，殆已”。當然，我們不能拿老祖宗這句話作為消極怠工的借口，不過在學習和工作的時候，的確需要要分辨事情的輕重緩急，否則一味蠻干，最終結果只能是--“殆已”。
? 突然發現這句話對于網絡爬蟲也是很有啟發意義的，對于浩瀚無邊的互聯網而言，網絡爬蟲涉及到頁面確實只是冰山一角。因此，如何確定一個頁面的重要性，從而在抓取過程中進行合理的調度，以最小的代價（硬件、帶寬）獲取到最大的利益（數量最多的重要的網頁）是設計網絡爬蟲過程中的一個核心問題。
? 一個頁面是否重要本來是一個比較主觀的問題，見仁見智。但是如果大部分人都認為一個頁面是重要的，那么我們大都會相信眾人的判斷，認為這個頁面的確“重要”的——這就是Google的PageRank算法的核心思想。不過在具體PageRank中，這個判斷的過程是采用網頁間的超鏈接來實現的。PageRank成就了Google的輝煌，自然有它的過人之處，不過PageRank計算對象是所有“已經抓取下來”的網頁，該算法通過這些網頁的相互連接關系以迭代的方式計算出各個網頁的重要性——頁面的PageRank。也就是說，我們在計算PageRank的過程中，是不會有新的頁面加入的，我們將這種計算方式稱為“離線”（off-line）的計算方式。PageRank能夠很好地反應出已有頁面間的相對重要性，因此十分適合于查詢結果的排序。但是，PageRank是一種離線的計算方式，在一次計算過程中不能加入新的頁面，而且計算過程是一個迭代過程，需要較長的計算時間，因此并不適合于網絡爬蟲的URL調度，動態決定URL的抓取順序。
? 針對這個問題，大家提出了很多解決方案[1]。其中，Abiteboul (Abiteboul et al., 2003)[2] 提出了一種基于OPIC (On-line Page Importance Computation)算法的抓取策略.在OPIC中，每一個頁面都有一個初始的"cash” 。在抓取的過程中，這些"cash"將會平均地分配給該頁面指向的頁面，這個分配過程是一次完成的。基于OPIC的網絡爬蟲在抓取過程中將以待抓取頁面累積的"cash"的多少為依據，優先抓取"cash"數量最多的頁面。OPIC算法如下所示，其中C[i]表示頁面i當前的Cash，H[i]表示在計算過程中頁面i累計收到的cash的總數。
??
?
OPIC:
On-line Page Importance Computation
for each i let C[i] := 1/n ;
for each i let H[i] := 0 ;
let G:=0 ;
do forever
begin
choose some node i ;
%% each node is selected
%% infinitely often
H[i] += C[i];
%% single disk access per page
for each child j of i,
do C[j] += C[i]/out[i];
%% Distribution of cash
%% depends on L
G += C[i];
C[i] := 0 ;
end
?
? Nutch使用了OPIC作為默認的URL調度策略，但是當前版本（0.9）的OPIC實現與Abiteboul在論文提出的OPIC并不完全相同，具體表現為：
? 1. Nutch中并沒有區分C[i]和H[i]，使用score一個變量記錄頁面累積的分數，在分配過程中也是將這個累積的分數全部平均分配給子頁面，分配完畢后分數也并不清零。
? 2. Nutch中并沒有virtual root page，也就是說葉子頁面（即沒有outlink的頁面）的分數將會丟失。?
?
? Nutch分數計算功能是通過插件的形式提供的，用戶可以通過新增插件的方式改變Nutch積分方式。Nutch提供了一個計算分數的接口 ScoringFilter，完成計算分數功能的類通過實現該接口以影響Nutch分數的計算方式，其默認的OPIC分數計算方法由類 OPICScoringFilter 提供。此外，參與計算分數的類還有 ScoringFilters，ParseOutputFormat。其中 ScoringFilters 負責將各個計分插件加載到系統中，并實現鏈式計分的過程；而ParseOutputFormat 在解析結果輸出之前，將頁面的分數分配到該頁面的各個子頁面中，使得Nutch的更新模塊可以使用這些數據更新CrawlDB數據庫。
? 為了能夠形象地展示Nutch的URL調度過程，我構建了一個微型的站點，站點只包含了五張網頁，其拓撲結構如下圖所示。
?
?
?
? 下面表格展示了Nutch的抓取流程，表格中，每一行中被粗體標注數字對應的URL為被調度器選中的URL，將在下一輪被抓取；“*”表示該網頁已被抓取；“--”表示該網頁尚未被系統獲知。
?
|
? |
A |
B |
C |
D |
E |
|
0 （ injected ） |
1.0 |
-- |
-- |
-- |
-- |
|
1 |
1.0* |
0.5 |
0.5 |
-- |
-- |
|
2 |
1.0* |
0.5* |
0.5 |
0.25 |
0.25 |
|
3 |
1.0* |
0.5* |
0.5* |
0.25 |
0.75 |
|
4 |
1.0* |
1.25* |
0.5* |
0.25 |
0.75* |
|
5 |
1.0* |
1.25* |
0.5* |
0.25* |
0.75* |
?
? 其實社區中也注意到Nutch在實現OPIC上的問題，也提出了自己的解決方案，具體的內容可以參考Nutch官方wiki上FixingOpicScoring[3]一文。
?
[2] Baeza-Yates, R., Castillo, C., Marin, M. and Rodriguez, A. (2005). Crawling a Country: Better Strategies than Breadth-First for Web Page Ordering . In Proceedings of the Industrial and Practical Experience track of the 14th conference on World Wide Web, pages 864–872, Chiba, Japan. ACM Press.
?
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
