網(wǎng)絡(luò)爬蟲(chóng)基本原理

網(wǎng)絡(luò)爬蟲(chóng)基本原理ACM201311/10/20231目錄基本描述1需要理解的算法2數(shù)據(jù)分類(lèi)3抓取策略4更新策略5Reference6ACM201311/10/20232網(wǎng)絡(luò)爬蟲(chóng)網(wǎng)絡(luò)爬蟲(chóng)（又被稱(chēng)為網(wǎng)頁(yè)蜘蛛，網(wǎng)絡(luò)機(jī)器人），是一種按照一定的規(guī)則，自動(dòng)的抓取萬(wàn)維網(wǎng)信息的程序或者腳本，是搜索引擎的重要組成。傳統(tǒng)爬蟲(chóng)從一個(gè)或若干初始網(wǎng)頁(yè)的URL開(kāi)始，獲得初始網(wǎng)頁(yè)上的URL，在抓取網(wǎng)頁(yè)的過(guò)程中，不斷從當(dāng)前頁(yè)面上抽取新的URL放入隊(duì)列，直到滿(mǎn)足系統(tǒng)的一定停止條件。ACM201311/10/20233聚焦爬蟲(chóng)傳統(tǒng)爬蟲(chóng)從一個(gè)或若干初始網(wǎng)頁(yè)的URL開(kāi)始，獲得初始網(wǎng)頁(yè)上的URL，在抓取網(wǎng)頁(yè)的過(guò)程中，不斷從當(dāng)前頁(yè)面上抽取新的URL放入隊(duì)列,直到滿(mǎn)足系統(tǒng)的一定停止條件。聚焦爬蟲(chóng)的工作流程較為復(fù)雜，需要根據(jù)一定的網(wǎng)頁(yè)分析算法過(guò)濾與主題無(wú)關(guān)的鏈接，保留有用的鏈接并將其放入等待抓取的URL隊(duì)列。然后，它將根據(jù)一定的搜索策略從隊(duì)列中選擇下一步要抓取的網(wǎng)頁(yè)URL，并重復(fù)上述過(guò)程，直到達(dá)到系統(tǒng)的某一條件時(shí)停止。另外，所有被爬蟲(chóng)抓取的網(wǎng)頁(yè)將會(huì)被系統(tǒng)存貯，進(jìn)行一定的分析、過(guò)濾，并建立索引，以便之后的查詢(xún)和檢索；對(duì)于聚焦爬蟲(chóng)來(lái)說(shuō)，這一過(guò)程所得到的分析結(jié)果還可能對(duì)以后的抓取過(guò)程給出反饋和指導(dǎo)。ACM201311/10/20234簡(jiǎn)單流程::BFSACM201311/10/2023下載網(wǎng)頁(yè)庫(kù)種子URL已抓取URL待抓取URLDNS解析&&網(wǎng)頁(yè)數(shù)據(jù)分析下載網(wǎng)頁(yè)進(jìn)入已抓取隊(duì)列從隊(duì)列信息中抽取新的URL作為初始URL5需要理解的算法1.關(guān)鍵字匹配::字符串匹配KNUTH-MORRIS-PRATT算法（KMP算法）有限自動(dòng)機(jī)算法*BOYER-MOORE算法2.網(wǎng)頁(yè)內(nèi)容冗余::卡時(shí)3.大數(shù)量網(wǎng)頁(yè)處理::*分布式4.防止重復(fù)遍歷::字符串HashACM201311/10/20236數(shù)據(jù)分類(lèi)1.已下載未過(guò)期網(wǎng)頁(yè)2.已下載已過(guò)期網(wǎng)頁(yè)：抓取到的網(wǎng)頁(yè)實(shí)際上是互聯(lián)網(wǎng)內(nèi)容的一個(gè)鏡像與備份，互聯(lián)網(wǎng)是動(dòng)態(tài)變化的，一部分互聯(lián)網(wǎng)上的內(nèi)容已經(jīng)發(fā)生了變化，這時(shí)，這部分抓取到的網(wǎng)頁(yè)就過(guò)期了。3.待下載網(wǎng)頁(yè)：也就是待抓取URL隊(duì)列中的那些頁(yè)面。4.可知網(wǎng)頁(yè)：還沒(méi)有抓取下來(lái)，也沒(méi)有在待抓取URL隊(duì)列中，但是可以通過(guò)對(duì)已抓取頁(yè)面或者待抓取URL對(duì)應(yīng)頁(yè)面進(jìn)行分析獲取到的URL，認(rèn)為是可知網(wǎng)頁(yè)。5.不可知網(wǎng)頁(yè)：還有一部分網(wǎng)頁(yè)，爬蟲(chóng)是無(wú)法直接抓取下載的ACM201311/10/20237數(shù)據(jù)分類(lèi)::BaiduACM201311/10/2023已抓取未過(guò)期已抓取已過(guò)期已知網(wǎng)頁(yè)8數(shù)據(jù)分類(lèi)::BaiduACM201311/10/2023不可知網(wǎng)頁(yè)9抓取策略::暴力1.深度優(yōu)先搜索2.廣度優(yōu)先搜索3.大站優(yōu)先策略對(duì)于待抓取URL隊(duì)列中的所有網(wǎng)頁(yè)，根據(jù)所屬的網(wǎng)站進(jìn)行分類(lèi)。對(duì)于待下載頁(yè)面數(shù)多的網(wǎng)站，優(yōu)先下載。這個(gè)策略也因此叫做大站優(yōu)先策略。ACM201311/10/202310抓取策略::技巧4.反向鏈接數(shù)策略反向鏈接數(shù)是指一個(gè)網(wǎng)頁(yè)被其他網(wǎng)頁(yè)鏈接指向的數(shù)量。反向鏈接數(shù)表示的是一個(gè)網(wǎng)頁(yè)的內(nèi)容受到其他人的推薦的程度。因此，很多時(shí)候搜索引擎的抓取系統(tǒng)會(huì)使用這個(gè)指標(biāo)來(lái)評(píng)價(jià)網(wǎng)頁(yè)的重要程度，從而決定不同網(wǎng)頁(yè)的抓取先后順序。在真實(shí)的網(wǎng)絡(luò)環(huán)境中，由于廣告鏈接、作弊鏈接的存在，反向鏈接數(shù)不能完全準(zhǔn)確評(píng)價(jià)網(wǎng)頁(yè)的重要程度。因此，搜索引擎往往考慮一些可靠的反向鏈接數(shù)。

ACM201311/10/202311抓取策略::技巧5.PartialPageRank策略PartialPageRank算法借鑒了PageRank算法的思想。對(duì)于已經(jīng)下載的網(wǎng)頁(yè)，連同待抓取URL隊(duì)列中的URL，形成網(wǎng)頁(yè)集合，計(jì)算每個(gè)頁(yè)面的PageRank值，計(jì)算完之后，將待抓取URL隊(duì)列中的URL按照PageRank值的大小排列，并按照該順序抓取頁(yè)面。6.OPIC策略策略該算法實(shí)際上也是對(duì)頁(yè)面進(jìn)行一個(gè)重要性打分。在算法開(kāi)始前，給所有頁(yè)面一個(gè)相同的初始現(xiàn)金（Cash）。當(dāng)下載了某個(gè)頁(yè)面P之后，將P的現(xiàn)金分?jǐn)偨o所有從P中分析出的鏈接，并且將P的現(xiàn)金清空。對(duì)于待抓取URL隊(duì)列中的所有頁(yè)面按照現(xiàn)金數(shù)進(jìn)行排序。ACM201311/10/202312更新策略::可持久化數(shù)據(jù)結(jié)構(gòu)1.歷史參考策略顧名思義，根據(jù)頁(yè)面以往的歷史更新數(shù)據(jù)，預(yù)測(cè)該頁(yè)面未來(lái)何時(shí)會(huì)發(fā)生變化。一般來(lái)說(shuō)，是通過(guò)泊松過(guò)程進(jìn)行建模進(jìn)行預(yù)測(cè)。2.用戶(hù)體驗(yàn)策略盡管搜索引擎針對(duì)于某個(gè)查詢(xún)條件能夠返回?cái)?shù)量巨大的結(jié)果，但是用戶(hù)往往只關(guān)注前幾頁(yè)結(jié)果。因此，抓取系統(tǒng)可以?xún)?yōu)先更新那些現(xiàn)實(shí)在查詢(xún)結(jié)果前幾頁(yè)中的網(wǎng)頁(yè)，而后再更新那些后面的網(wǎng)頁(yè)。這種更新策略也是需要用到歷史信息的。用戶(hù)體驗(yàn)策略保留網(wǎng)頁(yè)的多個(gè)歷史版本，并且根據(jù)過(guò)去每次內(nèi)容變化對(duì)搜索質(zhì)量的影響，得出一個(gè)平均值，用這個(gè)值作為決定何時(shí)重新抓取的依據(jù)。

ACM201311/10/202313更新策略::統(tǒng)計(jì)學(xué)改進(jìn)3.聚類(lèi)抽樣策略前面提到的兩種更新策略都有一個(gè)前提：需要網(wǎng)頁(yè)的歷史信息。這樣就存在兩個(gè)問(wèn)題：第一，系統(tǒng)要是為每個(gè)系統(tǒng)保存多個(gè)版本的歷史信息，無(wú)疑增加了很多的系統(tǒng)負(fù)擔(dān)；第二，要是新的網(wǎng)頁(yè)完全沒(méi)有歷史信息，就無(wú)法確定更新策略。

而聚類(lèi)抽樣策略認(rèn)為，網(wǎng)頁(yè)具有很多屬性，類(lèi)似屬性的網(wǎng)頁(yè)，可以認(rèn)為其更新頻率也是類(lèi)似的。要計(jì)算某一個(gè)類(lèi)別網(wǎng)頁(yè)的更新頻率，只需要對(duì)這一類(lèi)網(wǎng)頁(yè)抽樣，以他們的更新周期作為整個(gè)類(lèi)別的更新周期。

ACM201311/10/202314Referencewawl