網(wǎng)絡(luò)爬蟲基本原理課件

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

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

ACM20139/27/2023更新策略::可持久化數(shù)據(jù)結(jié)構(gòu)1.歷史參考策略ACM2013更新策略::統(tǒng)計學改進3.聚類抽樣策略前面提到的兩種更新策略都有一個前提：需要網(wǎng)頁的歷史信息。這樣就存在兩個問題：第一，系統(tǒng)要是為每個系統(tǒng)保存多個版本的歷史信息，無疑增加了很多的系統(tǒng)負擔；第二，要是新的網(wǎng)頁完全沒有歷史信息，就無法確定更新策略。

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

ACM20139/27/2023更新策略::統(tǒng)計學改進3.聚類抽樣策略ACM2013814Referencewawlian的個人博客/wawlian/archive/2012/06/18/2554072.html《這就是搜索引擎