蜘蛛
抓取策略
在爬蟲系統中，待抓取URL是很關鍵的部分，需要爬蟲抓取的網頁URL在其中排列，形成一個隊列結構，調度程序每次從隊列頭部取出URL，發送給網頁下載器下載頁面內容，每個新下載的網頁包含的URL會追加到待抓取URL隊列的末尾，這樣，形成一個抓取循環，整個爬蟲系統可以說是由這個隊列驅動運轉的。
待抓取URL隊列中的頁面URL順序是如何確定的？上面所述將新下載頁面中包含的鏈接追加到隊列末尾，這雖然是一種確定隊列URL順序的方法，但並非唯一的手段，事實上，還可以採納很多其他的技術，將隊列中待抓取的URL進行排序。而爬蟲的不同抓取策略，就是利用不同的方法來確定待抓取URL隊列中URL優先順序的。
爬蟲的抓取策略有很多種，但不論方法如何，其基本目標一致：優先選擇重要網頁進行抓取。在爬蟲系統中，所謂網頁的重要性，其評判標準可以選擇不同方法，但是大部分都是按照網頁的流行性來定義的。
抓取策略方法雖然有很多，但是這裡只講解已經被證明效果較好或者是比較有代表性的解決方案，包括以下四種：寬度優先遍歷策略、非完全PageRank策略、OPIC策略及大站優先策略。
01 寬度優先遍歷策略
寬度優先遍歷策略是一種非常簡單直觀且歷史也很悠久的遍歷方法，在搜索引擎爬蟲一出現就開始採用，新提出的抓取策略往往會將這種方法作為比較基準。但值得注意的是，這種策略也是一種很強悍的方法，很多新方法實際效果不見得比寬度優先遍歷策略好，所以至今這種方法實際上也是很多爬蟲優先採取的抓取策略。
上文所說的“將新下載的網頁包含的URL會追加到待抓取URL隊列的末尾”，這就是寬度優先遍歷的思想。也就是說，這種方法並沒有明確提出和使用網頁重要性作為衡量標準，只是機械的將新下載的網頁抽取鏈接，並追加到待抓取URL隊列中，以此作為URL的下載順序。下圖是這種策略的示意圖：假設隊列頭部的網頁是1號網頁，從1號網頁中抽取出3個鏈接分別指向2號、3號和4號，於是按照編號順序依次放入待抓取隊列中，圖中網頁的編號就是這個網頁在待抓取隊列的順序編號，之後爬蟲以此順序進行下載。
實驗表明這種策略效果很好，雖然看似機械，但實際上的網頁抓取順序基本是按照網頁的重要性排序的。之所以如此，有研究人員認為：如果某個網頁包含很多入鏈，那麼更有可能被寬度優先遍歷策略早早抓到，而入鏈數量從側面體現了網頁的重要性，即寬度優先遍歷策略實際上也是隱含了一些網頁優先級假設。
寬度優先遍歷策略
02 非完全PageRank策略
PageRank是一種著名的鏈接分析算法，可以用來衡量網頁的重要性。很自然地，可以想到用PageRank的思想來對URL優先級進行排序。但是這裡有個問題，PageRank是個全局性算法，也就是說當所有網頁都下載完畢後，其計算結果才是可靠的，而爬蟲的目的就是去下載網頁，在運行過程中只能看到一部分頁面，所以在抓取階段的網頁是無法獲得可靠的PageRank得分的。
如果我們仍然堅持在這個不完整的互聯網頁面子集內計算PageRank呢？這就是非完全PageRank策略的基本思路：對於已經下載的網頁，加上待抓取URL隊列中的URL一起，形成網頁集合，在此集合內進行PageRank計算，計算完成後，將待抓取URL隊列裡的網頁按照PageRank得分由高到低排序，形成的序列就是爬蟲接下來應該依次抓取的URL列表。這也是為何稱之為“非完全PageRank”的原因。
如果每次新抓取到一個網頁，就將所有已經下載的網頁重新計算新的非完全PageRank值，明顯效率太低，在現實中是不可行的。一個折中的辦法是：每當新下載的網頁攢夠K個，然後將所有下載頁面重新計算一遍新的非完全PageRank。這樣的計算效率還勉強能夠接受，但是又引來了新的問題：在展開下一輪PageRank計算之前，從新下載的網頁抽取出包含的鏈接，很有可能這些鏈接的重要性非常高，理應優先下載，這種情況該如何解決？非完全PageRank賦予這些新抽取出來但是又沒有PageRank值的網頁一個臨時PageRank值，將這個網頁的所有入鏈傳導的PageRank值匯，作為臨時PageRank值，如果這個值比待抓取URL隊列中已經計算出來PageRank值的網頁高，那麼優先下載這個URL。
下圖是非完全PageRank策略的一個簡略示意圖。我們設定每下載3個網頁進行新的PageRank計算，此時已經有{P1,P2,P3}3個網頁下載到本地，這3個網頁包含的鏈接指向{P4,P5,P6},形成了待抓取URL隊列。如何決定下載順序？將這6個網頁形成新的集合，對這個集合計算PageRank值，這樣P4、P5和P6就獲得自己對應的PageRank值，由大到小排序，即可得出其下載順序。這裡可以假設其下載順序為：P5、P4、P6，當下載P5頁面後抽取出鏈接，指向頁面P8，此時賦予P8臨時PageRank值，如果這個值大於P4和P6的PageRank值，則接下來優先下載P8。如此不斷循環，即形成了非完全PageRank策略的計算思路。
非完全PageRank看上去複雜，那麼效果是否一定優於簡單的寬度優先遍歷策略呢？不同的實驗結果存在著爭議，有些結果表明非完全PageRank結果略優，有些實驗結果卻恰恰相反，更有研究人員指出：非完全PageRank計算得出的重要性與完整的PageRank計算結果差異很大，不應作為衡量抓取過程中URL重要性計算的依據。
非完全PageRank策略
03 OPIC策略
OPIC的字面含義是“在線頁面重要性計算”，可以將其看作是一種改進的PageRank算法。在算法開始之前，每個互聯網頁面都給予相同的“現金”，每當下載了某個頁面P後，P將自己擁有的“現金”平均分配給頁面中包含的鏈接頁面，把自己的“現金”清空。而對於待抓取URL隊列中的網頁，則根據其手頭中擁有的現金金額多少排序，優先下載現金最充裕的網頁。OPIC從大的框架上與PageRank思路基本一致，區別在於：PageRank每次需要迭代計算，而OPIC策略不需要迭代過程，所以計算速度遠遠快於PageRank，適合實時計算使用。同時，PageRank在計算時，存在向無鏈接關係網頁的遠程跳轉過程，而OPIC沒有這一計算因子。實驗結果表明，OPIC是種較好的重要性衡量策略，效果略優於寬度優先遍歷策略。
04 大站優先策略
大站優先策略思路很直接：以網站為單位衡量網頁重要性，對於待抓取URL隊列中的網頁，根據所屬網站歸類，如果哪個網站等待下載的頁面最多，則優先下載這些鏈接，其本質思想傾向於優先下載大型網站，因為大型網站往往包含更多的頁面。鑑於大型網站往往是著名企業的內容，其網頁質量一般較高，所以這個思路雖然簡單，但是有一定依據。實驗表明這個算法效果也要略優於寬度優先遍歷策略。
網頁更新策略
互聯網的動態性是其顯著特徵，隨時都有新出現的頁面，頁面內容被更改或者原本存在的頁面被刪除。對於爬蟲來說，並非將網頁抓取到本地就算完成任務，也要體現出互聯網的這種動態性。本地下載的頁面可看作是互聯網頁面的“鏡像”，爬蟲要儘可能保證一致性。可以假設一種情況：某個網頁已被刪除或者內容做出重大改動，而搜索引擎對此擎茫然不知，仍按照舊有內容排序，將其作為搜索結果提供給用戶，其用戶體驗之糟糕不言而喻。所以，對於已經抓取過的網頁，爬蟲還要負責保持其內容和互聯網頁面的同步，這取決於爬蟲所採取的網頁更新策略。
網頁更新策略的任務是要決定何時重新抓取已經下載的網頁，儘可能使得本地下載網頁和互聯網原始頁面內容保持一致。常用的網頁更新策略有3種：歷史參考策略、用戶體驗策略和聚類抽樣策略。
01歷史參考策略
歷史參考策略是最直觀的一種更新策略，它建立於如下假設之上：過去頻繁更新的網頁，那麼將來也會頻繁更新。所以，為了預估某個網頁何時進行更新，可以通過參考歷史更新的情況來做出決定。
這種方法往往利用泊松過程來對網頁的變化進行建模，根據每個網頁過去的變動情況，利用模型預測將來何時內容會再次發生變化，以此來指導爬蟲的抓取過程。不同方法，側重點不同，比如有的研究將一個網頁劃分成不同的區域，抓取策略應該忽略掉廣告欄或者導航欄這種不重要區域的頻繁變化，而集中關注內容的變化探測和建模上。
02用戶體驗策略
一般來說，搜索引擎用戶提交查詢後，相關的搜索結果可能成千上萬，而用戶沒有耐心等待查看排在後面的搜索結果，可能只看前3頁搜索內容。用戶體驗策略就是利用用戶的這個特點來設計更新策略的。
這種更新策略是以用戶體驗為中心，即使本地索引的網頁內容是過時的，但是如果不影響用戶體驗，那麼晚些時候更新這些過時的網頁也未嘗不可。所以判斷一個網頁何時更新為好，，取決於這個網頁內容變化所帶來搜索質量的變化（往往採用搜索結果排名的變化來衡量），影響越大的網頁，則應該越快更新。
用戶體驗策略保存網頁的多個歷史版本，並根據過去每次內容變化對搜索質量的影響，得出一個平均值，以此作為判斷爬蟲重新抓取該網頁時機的參考依據，對於影響越厲害的網頁，則越優先調度重新抓取。
03聚類抽樣策略
上面介紹的兩種網頁更新策略嚴重依賴網頁的歷史更新信息，因為這是能夠進行後續計算的基礎。但是在現實中，為每個網頁保存其歷史信息，搜索系統會大量增加額外負擔。從另外一個角度考慮，如果是首次抓取到的網頁，因為沒有歷史信息，所以也就無法按照這兩種思路去預估更新週期。聚類抽樣策略正是為了解決上述缺點而提出的。
聚類抽樣策略認為：網頁具有一些屬性，根據這些屬性可以預測其更新週期，具有相似屬性的網頁，其更新週期也是類似的。於是，可以根據這些屬性將網頁歸類，同一類別內的網頁具有相同的更新頻率。為了計算某個類別的更新週期，只需對類別內網頁進行採樣，以這些採樣網頁的更新週期作為該類別內所有網頁的更新週期。與之前敘述的兩種方法比較，這種策略一方面無須為每個網頁保存歷史信息；另一方面，對於新網頁，即使沒有歷史信息，也可以根據其所屬類別來對其進行更新。
下面這張圖描述了聚類抽樣策略的基本流程，首先根據網頁表現出的特徵，將其聚合成不同的類別，每個類別內的網頁具有相似的更新週期。從類別中抽取出一部分最有代表性的網頁（一般抽取最靠近類中心的那些網頁），對這些網頁計算更新週期，那麼這個更新週期使用於該類別內的所有網頁，之後可根據網頁所屬類別來決定其更新週期。
聚類抽樣策略
網頁更新週期的屬性特徵劃分為兩大類：靜態特徵和動態特徵。靜態特徵包括：頁面的內容、圖片數量，頁面大小、鏈接深度、PageRank值等十幾種；而動態特徵體現了靜態特徵隨時間變化的情況，比如圖片數量的變化、入鏈出鏈的變化情況等。根據這兩類特徵，即可對網頁進行聚類。
上圖是一個較為通用的流程，不同算法在一些細節上有差異。比如有些研究直接省略聚類這個步驟，而是以網站作為聚類單位，即假設屬於同一個網站的網頁具有相同的更新週期，對網站內頁面進行抽樣，計算更新週期，之後網站內所有網頁以這個更新週期為準。這個假設雖然粗糙，因為很明顯同一網站內網頁更新週期差異很大，但是可以省略掉聚類這個步驟，在計算效率方面會更高。
相關實驗表明，聚類抽樣策略效果好於前兩種更新策略，但是對以億計的網頁進行聚類，其難度也是非常巨大的。
閱讀更多 努力拼搏的80後 的文章
