網(wǎng)絡(luò)爬蟲有哪些爬行策略？網(wǎng)絡(luò)爬蟲（web crawler）爬行策略如下：

　　下述的三種網(wǎng)絡(luò)特征，造成了設(shè)計(jì)網(wǎng)頁爬蟲抓取策略變得很難：

　　它巨大的數(shù)據(jù)量;

　　它快速的更新頻率;

　　動(dòng)態(tài)頁面的產(chǎn)生

　　它們?nèi)齻�(gè)特征一起產(chǎn)生了很多種類的爬蟲抓取鏈接。

　　巨大的數(shù)據(jù)量暗示了爬蟲，在給定的時(shí)間內(nèi)，只可以抓取所下載網(wǎng)絡(luò)的一部分，所以，它需要對(duì)它的抓取頁面設(shè)置優(yōu)先級(jí);快速的更新頻率說明在爬蟲抓取下載某網(wǎng)站一個(gè)網(wǎng)頁的時(shí)候，很有可能在這個(gè)站點(diǎn)又有新的網(wǎng)頁被添加進(jìn)來，或者這個(gè)頁面被更新或者刪除了。

　　最近新增的很多頁面都是通過服務(wù)器端腳本語言產(chǎn)生的，無窮的參數(shù)組合也增加了爬蟲抓取的難度，只有一小部分這種組合會(huì)返回一些獨(dú)特的內(nèi)容。例如，一個(gè)很小照片存儲(chǔ)庫僅僅通過get方式可能提供就給用戶三種操作方式。如果這里存著四種分類方式，三種縮略圖方式，兩種文件格式，和一個(gè)禁止用戶提供內(nèi)容的選項(xiàng)，那么，同樣的內(nèi)容就可以通過48種方式訪問。這種數(shù)學(xué)組合給網(wǎng)絡(luò)爬蟲創(chuàng)造的難處就是，為了獲取不同的內(nèi)容，他們必須篩選無窮僅有微小變化的組合。

　　正如愛德華等人所說的：“用于檢索的帶寬不是無限的，也不是免費(fèi)的;所以，如果引入衡量爬蟲抓取質(zhì)量或者新鮮度的有效指標(biāo)的話，不但伸縮性，連有效性都將變得十分必要”(愛德華等人，2001年)。一個(gè)爬蟲就必須小心的選擇下一步要訪問什么頁面。網(wǎng)頁爬蟲的行為通常是四種策略組合的結(jié)果。

　　♦ 選擇策略，決定所要下載的頁面;

　　♦ 重新訪問策略，決定什么時(shí)候檢查頁面的更新變化;

　　♦ 平衡禮貌策略，指出怎樣避免站點(diǎn)超載;

　　♦ 并行策略，指出怎么協(xié)同達(dá)到分布式抓取的效果;

　　1.1 選擇策略：

　　就現(xiàn)在網(wǎng)絡(luò)資源的大小而言，即使很大的搜索引擎也只能獲取網(wǎng)絡(luò)上可得到資源的一小部分。由勞倫斯河蓋爾斯共同做的一項(xiàng)研究指出，沒有一個(gè)搜索引擎抓取的內(nèi)容達(dá)到網(wǎng)絡(luò)的16%(勞倫斯河蓋爾斯，2001)。網(wǎng)絡(luò)爬蟲通常僅僅下載網(wǎng)頁內(nèi)容的一部分，但是大家都還是強(qiáng)烈要求下載的部分包括最多的相關(guān)頁面，而不僅僅是一個(gè)隨機(jī)的簡單的站點(diǎn)。

　　這就要求一個(gè)公共標(biāo)準(zhǔn)來區(qū)分網(wǎng)頁的重要程度，一個(gè)頁面的重要程度與他自身的質(zhì)量有關(guān)，與按照鏈接數(shù)、訪問數(shù)得出的受歡迎程度有關(guān)，甚至與他本身的網(wǎng)址(后來出現(xiàn)的把搜索放在一個(gè)頂級(jí)域名或者一個(gè)固定頁面上的垂直搜索)有關(guān)。設(shè)計(jì)一個(gè)好的搜索策略還有額外的困難，它必須在不完全信息下工作，因?yàn)檎麄�(gè)頁面的集合在抓取時(shí)是未知的。

　　Cho等人(Cho et al，1998)做了第一份抓取策略的研究。他們的數(shù)據(jù)是斯坦福大學(xué)網(wǎng)站中的18萬個(gè)頁面，使用不同的策略分別模仿抓取。排序的方法使用了廣度優(yōu)先，后鏈計(jì)數(shù)，和部分pagerank算法。計(jì)算顯示，如果你想要優(yōu)先下載pagerank高的頁面，那么，部分PageRank策略是比較好的，其次是廣度優(yōu)先和后鏈計(jì)數(shù)。并且，這樣的結(jié)果僅僅是針對(duì)一個(gè)站點(diǎn)的。

　　Najork和Wiener (Najork and Wiener, 2001)采用實(shí)際的爬蟲，對(duì)3.28億個(gè)網(wǎng)頁，采用廣度優(yōu)先研究。他們發(fā)現(xiàn)廣度優(yōu)先會(huì)較早的抓到PageRank高的頁面(但是他們沒有采用其他策略進(jìn)行研究)。作者給出的解釋是：“最重要的頁面會(huì)有很多的主機(jī)連接到他們，并且那些鏈接會(huì)較早的發(fā)現(xiàn)，而不用考慮從哪一個(gè)主機(jī)開始�！�

　　Abiteboul (Abiteboul 等人, 2003)，設(shè)計(jì)了一種基于OPIC(在線頁面重要指數(shù))的抓取戰(zhàn)略。在OPIC中，每一個(gè)頁面都有一個(gè)相等的初始權(quán)值，并把這些權(quán)值平均分給它所指向的頁面。這種算法與Pagerank相似，但是他的速度很快，并且可以一次完成。OPIC的程序首先抓取獲取權(quán)值最大的頁面，實(shí)驗(yàn)在10萬個(gè)冪指分布的模擬頁面中進(jìn)行。并且，實(shí)驗(yàn)沒有和其它策略進(jìn)行比較，也沒有在真正的WEB頁面測試。

　　Boldi等人(Boldi et al., 2004)的模擬檢索實(shí)驗(yàn)進(jìn)行在 從.it網(wǎng)絡(luò)上取下的4000萬個(gè)頁面和從webbase得到的1億個(gè)頁面上，測試廣度優(yōu)先和深度優(yōu)先，隨機(jī)序列和有序序列。比較的基礎(chǔ)是真實(shí)頁面pageRank值和計(jì)算出來的pageRank值的接近程度。令人驚奇的是，一些計(jì)算pageRank很快的頁面(特別明顯的是廣度優(yōu)先策略和有序序列)僅僅可以達(dá)到很小的接近程度。

　　Baeza-Yates等人(Baeza-Yates et al., 2005) 在從.gr域名和.cl域名子網(wǎng)站上獲取的300萬個(gè)頁面上模擬實(shí)驗(yàn)，比較若干個(gè)抓取策略。結(jié)果顯示OPIC策略和站點(diǎn)隊(duì)列長度，都比廣度優(yōu)先要好;并且如果可行的話，使用之前的爬行抓取結(jié)果來指導(dǎo)這次抓取，總是十分有效的。

　　Daneshpajouh等人(Daneshpajouh et al., 2008)設(shè)計(jì)了一個(gè)用于尋找好種子的社區(qū)。它們從來自不同社區(qū)的高PageRank頁面開始檢索的方法，迭代次數(shù)明顯小于使用隨機(jī)種子的檢索。使用這種方式，可以從以前抓取頁面之中找到好的種子，使用這些種子是十分有效的。

　　1.1.1 限定訪問鏈接

　　一個(gè)爬蟲可能僅僅想找到html頁面的種子而避免其他的文件類型。為了僅僅得到html的資源，一個(gè)爬蟲可以首先做一個(gè)http head的請(qǐng)求，以在使用request方法獲取所有的資源之前，決定這個(gè)網(wǎng)絡(luò)文件的類型。為了避免要發(fā)送過多的head請(qǐng)求，爬蟲可以交替的檢查url并且僅僅對(duì)以html，htm和反斜杠結(jié)尾的文件發(fā)送資源請(qǐng)求。這種策略會(huì)導(dǎo)致很多的html資源在無意中錯(cuò)過，一種相似的策略是將網(wǎng)絡(luò)資源的擴(kuò)展名同已知是html文件類型的一組擴(kuò)展名(如.html,.htm,.asp,.php,.aspx,反斜杠)進(jìn)行比較。

　　一些爬蟲也會(huì)限制對(duì)任何含有“?”的資源(這些是動(dòng)態(tài)生成的)進(jìn)行獲取請(qǐng)求，以避免蜘蛛爬行在某一個(gè)站點(diǎn)中陷入下載無窮無盡的URL的困境。

　　1.1.2 路徑檢索

　　一些爬蟲會(huì)盡可能多的嘗試下載一個(gè)特定站點(diǎn)的資源。Cothey(Cothey,2004)引入了一種路徑檢索的爬蟲，它會(huì)嘗試抓取需要檢索資源的所有URL。例如，給定一個(gè)種子地址：它將會(huì)嘗試檢索/hamster/menkey/,/hamster/和/ 。Cothey發(fā)現(xiàn)路徑檢索對(duì)發(fā)現(xiàn)獨(dú)立資源，或者一些通常爬蟲檢索不到的的連接是非常有效的。

　　一些路徑檢索的爬蟲也被稱為收割機(jī)軟件，因?yàn)樗麄兺ǔＳ糜谑崭罨蛘呤占�所有的�?nèi)容，可能是從特定的頁面或者主機(jī)收集相冊的照片。

　　1.1.3 聚焦抓取

　　爬蟲所抓取頁面的重要程度也可以表述成它與給定查詢之間相似程度的函數(shù)。網(wǎng)絡(luò)爬蟲嘗試下載相似頁面，可以稱為聚焦檢索或者主題檢索。關(guān)于主題檢索和聚焦檢索的概念，最早是由Menczer(Menczer 1997; Menczer and Belew, 1998)和Chakrabarti等人首先提出來的(Chakrabarti et al., 1999)。

　　聚焦檢索的主要問題是網(wǎng)頁爬蟲的使用環(huán)境，我們希望在實(shí)際下載頁面之前，就可以知道給定頁面和查詢之間的相似度。一個(gè)可能的方法就是在鏈接之中設(shè)置錨點(diǎn)，這就是在早期時(shí)候，Pinkerton(Pinkerton，1994)曾經(jīng)在一個(gè)爬蟲中采用的策略。Diligenti等人(Diligenti等人，2000)建議使用已經(jīng)抓取頁面的內(nèi)容去推測查詢和未訪問頁的相似度。一個(gè)聚焦查詢的表現(xiàn)的好壞主要依賴于查詢主題內(nèi)容的豐富程度，通常還會(huì)依賴頁面查詢引擎提供的查詢起點(diǎn)。

　　1.1.4 抓取深層的網(wǎng)頁

　　很多的頁面隱藏的很深或隱藏在在看不到的網(wǎng)絡(luò)之中。這些頁面通常只有在向數(shù)據(jù)庫提交查詢的時(shí)候才可以訪問到，如果沒有鏈接指向他們的話，一般的爬蟲是不能訪問到這些頁面的。谷歌站點(diǎn)地圖協(xié)議和mod oai(Nelson等人，2005)嘗試允許發(fā)現(xiàn)這些深層次的資源。

　　深層頁面抓取器增加了抓取網(wǎng)頁的鏈接數(shù)。一些爬蟲僅僅抓取形如

　　1.1.5 WEB3.0檢索

　　Web3.0為下一代搜索技術(shù)定義了更先進(jìn)的技術(shù)和新的準(zhǔn)則，可以概括為語義網(wǎng)絡(luò)和網(wǎng)站模板解析的概念。第三代檢索技術(shù)將建立在人機(jī)巧妙的聯(lián)系的基礎(chǔ)上。

　　1.2重新訪問策略

　　網(wǎng)絡(luò)具有動(dòng)態(tài)性很強(qiáng)的特性。抓取網(wǎng)絡(luò)上的一小部分內(nèi)容可能會(huì)花費(fèi)真的很長的時(shí)間，通常用周或者月來衡量。當(dāng)爬蟲完成它的抓取的任務(wù)以后，很多操作是可能會(huì)發(fā)生的，這些操作包括新建，更新和刪除。

　　從搜索引擎的角度來看，不檢測這些事件是有成本的，成本就是我們僅僅擁有一份過時(shí)的資源。最常使用的成本函數(shù)，是新鮮度和過時(shí)性(2000年，Cho 和Garcia-Molina)

　　新鮮度：這是一個(gè)衡量抓取內(nèi)容是不是準(zhǔn)確的二元值。在時(shí)間t內(nèi)，倉庫中頁面p的新鮮度是這樣定義的：

　　新鮮度 過時(shí)性:這是一個(gè)衡量本地已抓取的內(nèi)容過時(shí)程度的指標(biāo)。在時(shí)間t時(shí)，倉庫中頁面p的時(shí)效性的定義如下：

　　過時(shí)性 在頁面抓取中，新鮮度和過時(shí)性的發(fā)展

　　Coffman等人(Edward G. Coffman，1998)是從事爬蟲對(duì)象定義的，他們提出了一個(gè)相當(dāng)于新鮮度的概念，但是使用了不同的措詞：他們建議爬蟲必須最小化過時(shí)頁面部分。他們指出網(wǎng)絡(luò)爬行的問題就相當(dāng)于多個(gè)隊(duì)列，一個(gè)投票系統(tǒng);這里，爬蟲是服務(wù)器，不同的站點(diǎn)是隊(duì)列。頁面修改是到達(dá)的顧客，頁面切換的時(shí)間是頁面進(jìn)入一個(gè)單一站點(diǎn)的間隔。在這個(gè)模型下，每一個(gè)顧客在投票系統(tǒng)的平均時(shí)間，相當(dāng)于爬蟲的平均過時(shí)性。

　　爬蟲的目標(biāo)是盡可能高的提高頁面的新鮮度，同時(shí)降低頁面的過時(shí)性。這一目標(biāo)并不是完全一樣的，第一種情況，爬蟲關(guān)心的是有多少頁面時(shí)過時(shí)的;在第二種情況，爬蟲關(guān)心的頁面過時(shí)了多少。

　　兩種最簡單的重新訪問策略是由Cho和Garcia-Molina研究的(Cho 和Garcia-Molina，2003)：

　　統(tǒng)一策略：使用相同的頻率，重新訪問收藏中的所有的鏈接，而不考慮他們更新頻率。

　　正比策略：對(duì)變化越多的網(wǎng)頁，重新訪問的頻率也越高。網(wǎng)頁訪問的頻率和網(wǎng)頁變化的頻率直接相關(guān)。

　　(兩種情況下，爬蟲的重新抓取都可以采用隨機(jī)方式，或者固定的順序)

　　Cho和Garcia-Molina證明了一個(gè)出人意料的結(jié)果。以平均新鮮度方式衡量，統(tǒng)一策略在模擬頁面和真實(shí)的網(wǎng)絡(luò)抓取中都比正比策略出色。對(duì)于這種結(jié)果的解釋是：當(dāng)一個(gè)頁面變化太快的時(shí)候，爬蟲將會(huì)將會(huì)在不斷的嘗試重新抓取而浪費(fèi)很多時(shí)間，但是卻還是不能保證頁面的新鮮度。

　　為了提高頁面的新鮮度，我們應(yīng)該宣判變化太快的頁面死罪(Cho和Garcia-Molina, 2003a)。最佳的重新訪問策略既不是統(tǒng)一策略，也不是正比策略;保持平均頁面新鮮度高的最佳方法策略包括忽略那些變化太快的頁面，而保持頁面平均過時(shí)性低的方法則是對(duì)每一頁按照頁面變化率單調(diào)變化的策略訪問。兩種情況下，最佳的策略較正比策略，都更接近統(tǒng)一策略。正如Coffman等人(Edward G.Coffman，1998)所注意到的：“為了最小化頁面過時(shí)的時(shí)間，對(duì)任一個(gè)頁面的訪問都應(yīng)該盡可能的均勻間隔地訪問�！睂�(duì)于重新訪問的詳盡的策略在大體上是不可以達(dá)到的，但是他們可以從數(shù)學(xué)上得到，因?yàn)樗麄円蕾囉陧撁娴淖兓��?Cho和Garcia-Molina,2003a)指出指數(shù)變化是描述頁面變化的好方法，同時(shí)(Ipeirotis等人，2005)指出了怎么使用統(tǒng)計(jì)工具去發(fā)現(xiàn)適合這些變化的參數(shù)。注意在這里的重新訪問策略認(rèn)為每一個(gè)頁面都是相同的(網(wǎng)絡(luò)上所有的頁面價(jià)值都是一樣的)這不是現(xiàn)實(shí)的情況，所以，為了獲取更好的抓取策略，更多有關(guān)網(wǎng)頁質(zhì)量的信息應(yīng)該考慮進(jìn)去。

　　1.3 平衡禮貌策略

　　爬蟲相比于人，可以有更快的檢索速度和更深的層次，所以，他們可能使一個(gè)站點(diǎn)癱瘓。不需要說一個(gè)單獨(dú)的爬蟲一秒鐘要執(zhí)行多條請(qǐng)求，下載大的文件。一個(gè)服務(wù)器也會(huì)很難響應(yīng)多線程爬蟲的請(qǐng)求。

　　就像Koster(Koster，1995)所注意的那樣，爬蟲的使用對(duì)很多工作都是很有用的，但是對(duì)一般的社區(qū)，也需要付出代價(jià)。使用爬蟲的代價(jià)包括：

　　 網(wǎng)絡(luò)資源：在很長一段時(shí)間，爬蟲使用相當(dāng)?shù)膸�寬高度并行地工作�?/P>

　　 服務(wù)器超載：尤其是對(duì)給定服務(wù)器的訪問過高時(shí)。

　　 質(zhì)量糟糕的爬蟲，可能導(dǎo)致服務(wù)器或者路由器癱瘓，或者會(huì)嘗試下載自己無法處理的頁面。

　　 個(gè)人爬蟲，如果過多的人使用，可能導(dǎo)致網(wǎng)絡(luò)或者服務(wù)器阻塞。

　　對(duì)這些問題的一個(gè)部分解決方法是漫游器排除協(xié)議(Robots exclusion protocol)，也被稱為robots.txt議定書(Koster，1996)，這份協(xié)議對(duì)于管理員指明網(wǎng)絡(luò)服務(wù)器的那一部分不能到達(dá)是一個(gè)標(biāo)準(zhǔn)。這個(gè)標(biāo)準(zhǔn)沒有包括重新訪問一臺(tái)服務(wù)器的間隔的建議，雖然訪問間隔是避免服務(wù)器超載的最有效的辦法。最近的商業(yè)搜索軟件，如Ask Jeeves，MSN和Yahoo可以在robots.txt中使用一個(gè)額外的 “Crawl-delay”參數(shù)來指明請(qǐng)求之間的延遲。

　　對(duì)連接間隔時(shí)間的第一個(gè)建議由Koster 1993年給出，時(shí)間是60秒。按照這個(gè)速度，如果一個(gè)站點(diǎn)有超過10萬的頁面，即使我們擁有零延遲和無窮帶寬的完美連接，它也會(huì)需要兩個(gè)月的時(shí)間來下載整個(gè)站點(diǎn)，并且，這個(gè)服務(wù)器中的資源，只有一小部分可以使用。這似乎是不可以接受的。

　　Cho(Cho和Garcia-Molina, 2003)使用10秒作為訪問的間隔時(shí)間，WIRE爬蟲(Baeza-Yates and Castillo, 2002)使用15秒作為默認(rèn)間隔。MercatorWeb(Heydon 和Najork, 1999)爬蟲使用了一種自適應(yīng)的平衡策略：如果從某一服務(wù)器下載一個(gè)文檔需要t秒鐘，爬蟲就等待10t秒的時(shí)間，然后開始下一個(gè)頁面。Dill等人 (Dill et al., 2002) 使用1秒。

　　對(duì)于那些使用爬蟲用于研究目的的，一個(gè)更詳細(xì)的成本-效益分析是必要的，當(dāng)決定去哪一個(gè)站點(diǎn)抓取，使用多快的速度抓取的時(shí)候，倫理的因素也需要考慮進(jìn)來。

　　訪問記錄顯示已知爬蟲的訪問間隔從20秒鐘到3-4分鐘不等。需要注意的是即使很禮貌，采取了所有的安全措施來避免服務(wù)器超載，還是會(huì)引來一些網(wǎng)絡(luò)服務(wù)器管理員的抱怨的。Brin和Page注意到：運(yùn)行一個(gè)針對(duì)超過50萬服務(wù)器的爬蟲，會(huì)產(chǎn)生很多的郵件和電話。這是因?yàn)橛袩o數(shù)的人在上網(wǎng)，而這些人不知道爬蟲是什么，因?yàn)檫@是他們第一次見到。(Brin和Page，1998)

　　1.4 并行策略

　　一個(gè)并行爬蟲是并行運(yùn)行多個(gè)進(jìn)程的爬蟲。它的目標(biāo)是最大化下載的速度，同時(shí)盡量減少并行的開銷和下載重復(fù)的頁面。為了避免下載一個(gè)頁面兩次，爬蟲系統(tǒng)需要策略來處理爬蟲運(yùn)行時(shí)新發(fā)現(xiàn)的URL，因?yàn)橥�一個(gè)URL地址，可能被不同的爬蟲進(jìn)程抓到。