? 莊子曾說：“吾生也有涯，而知也無涯，以有涯隨無涯，殆已”。當(dāng)然，我們不能拿老祖宗這句話作為消極怠工的借口，不過在學(xué)習(xí)和工作的時(shí)候，的確需要要分辨事情的輕重緩急，否則一味蠻干，最終結(jié)果只能是--“殆已”。
? 突然發(fā)現(xiàn)這句話對(duì)于網(wǎng)絡(luò)爬蟲也是很有啟發(fā)意義的，對(duì)于浩瀚無邊的互聯(lián)網(wǎng)而言，網(wǎng)絡(luò)爬蟲涉及到頁面確實(shí)只是冰山一角。因此，如何確定一個(gè)頁面的重要性，從而在抓取過程中進(jìn)行合理的調(diào)度，以最小的代價(jià)（硬件、帶寬）獲取到最大的利益（數(shù)量最多的重要的網(wǎng)頁）是設(shè)計(jì)網(wǎng)絡(luò)爬蟲過程中的一個(gè)核心問題。
? 一個(gè)頁面是否重要本來是一個(gè)比較主觀的問題，見仁見智。但是如果大部分人都認(rèn)為一個(gè)頁面是重要的，那么我們大都會(huì)相信眾人的判斷，認(rèn)為這個(gè)頁面的確“重要”的——這就是Google的PageRank算法的核心思想。不過在具體PageRank中，這個(gè)判斷的過程是采用網(wǎng)頁間的超鏈接來實(shí)現(xiàn)的。PageRank成就了Google的輝煌，自然有它的過人之處，不過PageRank計(jì)算對(duì)象是所有“已經(jīng)抓取下來”的網(wǎng)頁，該算法通過這些網(wǎng)頁的相互連接關(guān)系以迭代的方式計(jì)算出各個(gè)網(wǎng)頁的重要性——頁面的PageRank。也就是說，我們?cè)谟?jì)算PageRank的過程中，是不會(huì)有新的頁面加入的，我們將這種計(jì)算方式稱為“離線”（off-line）的計(jì)算方式。PageRank能夠很好地反應(yīng)出已有頁面間的相對(duì)重要性，因此十分適合于查詢結(jié)果的排序。但是，PageRank是一種離線的計(jì)算方式，在一次計(jì)算過程中不能加入新的頁面，而且計(jì)算過程是一個(gè)迭代過程，需要較長的計(jì)算時(shí)間，因此并不適合于網(wǎng)絡(luò)爬蟲的URL調(diào)度，動(dòng)態(tài)決定URL的抓取順序。
? 針對(duì)這個(gè)問題，大家提出了很多解決方案[1]。其中，Abiteboul (Abiteboul et al., 2003)[2] 提出了一種基于OPIC (On-line Page Importance Computation)算法的抓取策略.在OPIC中，每一個(gè)頁面都有一個(gè)初始的"cash” 。在抓取的過程中，這些"cash"將會(huì)平均地分配給該頁面指向的頁面，這個(gè)分配過程是一次完成的。基于OPIC的網(wǎng)絡(luò)爬蟲在抓取過程中將以待抓取頁面累積的"cash"的多少為依據(jù)，優(yōu)先抓取"cash"數(shù)量最多的頁面。OPIC算法如下所示，其中C[i]表示頁面i當(dāng)前的Cash，H[i]表示在計(jì)算過程中頁面i累計(jì)收到的cash的總數(shù)。
??
?
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作為默認(rèn)的URL調(diào)度策略，但是當(dāng)前版本（0.9）的OPIC實(shí)現(xiàn)與Abiteboul在論文提出的OPIC并不完全相同，具體表現(xiàn)為：
? 1. Nutch中并沒有區(qū)分C[i]和H[i]，使用score一個(gè)變量記錄頁面累積的分?jǐn)?shù)，在分配過程中也是將這個(gè)累積的分?jǐn)?shù)全部平均分配給子頁面，分配完畢后分?jǐn)?shù)也并不清零。
? 2. Nutch中并沒有virtual root page，也就是說葉子頁面（即沒有outlink的頁面）的分?jǐn)?shù)將會(huì)丟失。?
?
? Nutch分?jǐn)?shù)計(jì)算功能是通過插件的形式提供的，用戶可以通過新增插件的方式改變Nutch積分方式。Nutch提供了一個(gè)計(jì)算分?jǐn)?shù)的接口 ScoringFilter，完成計(jì)算分?jǐn)?shù)功能的類通過實(shí)現(xiàn)該接口以影響Nutch分?jǐn)?shù)的計(jì)算方式，其默認(rèn)的OPIC分?jǐn)?shù)計(jì)算方法由類 OPICScoringFilter 提供。此外，參與計(jì)算分?jǐn)?shù)的類還有 ScoringFilters，ParseOutputFormat。其中 ScoringFilters 負(fù)責(zé)將各個(gè)計(jì)分插件加載到系統(tǒng)中，并實(shí)現(xiàn)鏈?zhǔn)接?jì)分的過程；而ParseOutputFormat 在解析結(jié)果輸出之前，將頁面的分?jǐn)?shù)分配到該頁面的各個(gè)子頁面中，使得Nutch的更新模塊可以使用這些數(shù)據(jù)更新CrawlDB數(shù)據(jù)庫。
? 為了能夠形象地展示Nutch的URL調(diào)度過程，我構(gòu)建了一個(gè)微型的站點(diǎn)，站點(diǎn)只包含了五張網(wǎng)頁，其拓?fù)浣Y(jié)構(gòu)如下圖所示。
?
?
?
? 下面表格展示了Nutch的抓取流程，表格中，每一行中被粗體標(biāo)注數(shù)字對(duì)應(yīng)的URL為被調(diào)度器選中的URL，將在下一輪被抓取；“*”表示該網(wǎng)頁已被抓取；“--”表示該網(wǎng)頁尚未被系統(tǒng)獲知。
?
|
? |
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* |
?
? 其實(shí)社區(qū)中也注意到Nutch在實(shí)現(xiàn)OPIC上的問題，也提出了自己的解決方案，具體的內(nèi)容可以參考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.
?
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號(hào)聯(lián)系： 360901061
您的支持是博主寫作最大的動(dòng)力，如果您喜歡我的文章，感覺我的文章對(duì)您有幫助，請(qǐng)用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點(diǎn)擊下面給點(diǎn)支持吧，站長非常感激您！手機(jī)微信長按不能支付解決辦法：請(qǐng)將微信支付二維碼保存到相冊(cè)，切換到微信，然后點(diǎn)擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對(duì)您有幫助就好】元
