數(shù)學(xué)之美--關(guān)于圖論引申出來的爬蟲構(gòu)想

轉(zhuǎn)載請注明出處：http://www.cnblogs.com/codefish/p/4971664.html

在了解爬蟲之前，我一直認為是簡單的對單一網(wǎng)站的采集，無非就是對于一個域名內(nèi)定點的數(shù)據(jù)抓取而已，2012年買了《數(shù)學(xué)之美》后，就一直沒有正兒八經(jīng)的看，或者當(dāng)時看了之后，由于自己的水平有限，壓根就沒有留下深刻的印象，以至于現(xiàn)在開始系統(tǒng)的研究一個框架的時候，總是粗淺的了解它的技術(shù)實現(xiàn)和API的調(diào)用一些方法，從來沒有深入的去了解它背后的設(shè)計思想。這就造成了用了千百種工具，還是自己寫不出一個好工具的尷尬，人最怕的就是洋洋得意與自我欺騙，前者讓自己停止了前進的腳步，滿足于當(dāng)前的現(xiàn)狀，后者是讓自己固執(zhí)，固步自封。

現(xiàn)在重新拿起原先的書開始看，感覺里面的東西通俗易懂，而且包含的思想深刻。

這里記錄了關(guān)于爬蟲的構(gòu)建的一些要點：

1，是BFS(Breadth-First Search) 還是 DFS(Depth-First Search)

雖然在理論，這兩個算法（在不考慮時間因素的前提下）都能免在大致相同的里爬下整個的“靜態(tài)”互聯(lián)網(wǎng)的內(nèi)容，但是工程上的假設(shè)-都是在現(xiàn)實的世界里面做不到的

搜索引擎的網(wǎng)絡(luò)爬蟲問題更應(yīng)該定義為“如何在有限的時間內(nèi)最多的爬下最重要的網(wǎng)頁”。顯然各個網(wǎng)站最重要的內(nèi)容應(yīng)該是它的首頁，在極端的情況下，如果爬蟲非常的小，只能下載非常有限的網(wǎng)頁。那么應(yīng)該下載的是所有網(wǎng)站的首頁，如果在爬蟲在大一點，就應(yīng)該下載和首頁相關(guān)的直屬鏈接，因為這些網(wǎng)頁是網(wǎng)站設(shè)計者自己認為相當(dāng)重要的內(nèi)容。在這個前提下，顯然BFS要明顯優(yōu)于DFS。事實在搜索引擎的爬蟲里，雖然并不是簡單的采用BFS，但是先爬哪一個網(wǎng)頁，后爬哪一個網(wǎng)頁，原理上基本都是BFS.

那DFS就不要使用了呢？也不是這樣，這是和爬蟲的分布式結(jié)構(gòu)以及網(wǎng)絡(luò)通信的握手成本相關(guān)的。所謂的“握手”是指下載服務(wù)器和網(wǎng)站的服務(wù)器建立通信的過程。這個過程是需要額外的時間，如果握手的次數(shù)太多，下載的效率就降低了。實際的網(wǎng)絡(luò)爬蟲都是一個由成百上千甚至上千成的服務(wù)器組成的分布式系統(tǒng)。對于某個網(wǎng)站，一般是由特定的一臺或者幾臺服務(wù)器專門下載的。這些服務(wù)器下載完一個網(wǎng)站 ，然后再進入下一個網(wǎng)站，而不是每個網(wǎng)站先輪流下載5%,然后再回頭下載第二批。這樣就可以避免握手次數(shù)太多。如果是下載完成第一個網(wǎng)站再下載第二個，那么這有點像DPS了，雖然下載同一個網(wǎng)站還是需要BFS。

總結(jié)來說，網(wǎng)絡(luò)爬蟲對網(wǎng)頁的遍歷次序不是簡單的BFS或者DFS，而是有一個相對復(fù)雜的下載優(yōu)先級排序方法。管理這個優(yōu)先級排序的子系統(tǒng)稱為調(diào)度系統(tǒng)(Scheduler)。

這里，我們可以參考scrpay的核心組件，scheduler :

https://github.com/scrapy/scrapy/blob/master/scrapy/core/scheduler.py

由它來決定當(dāng)一個網(wǎng)頁下載完成后然后在下載哪一個。當(dāng)然在調(diào)度系統(tǒng)里需要存儲哪些已經(jīng)發(fā)現(xiàn)的尚未下載的網(wǎng)頁URL，它們一般存在一個優(yōu)先級隊列(Priority Queue)里，而用這種方式遍歷的整個互聯(lián)網(wǎng)，在工程上和BFS更相似。因此，在爬蟲中，BFS的成分多一些。

這里引申另外一個內(nèi)容，如果去重和共享隊列。

我們知道，去重一般使用hash算法，由于hash集合的方便操作性，在數(shù)據(jù)量不大時，我們用hash集合來判斷一個元素是否在一個集合中相當(dāng)?shù)姆奖悖侨绻麛?shù)據(jù)量相當(dāng)大，我們都知道一個搜索引擎的爬蟲決不可能只用一臺機器的內(nèi)容來存儲這些已知的列表。這個時候就要介紹引入布隆過濾器了，關(guān)于bloom filter ，我在上一個文章里面已經(jīng)提到了一些。請參考：

http://www.cnblogs.com/codefish/p/4962164.html

另外一個，一般使用scrapy的分布式的核心，就是關(guān)于url的隊列操作引入到redis

參考：

https://github.com/rolando/scrapy-redis

我將在下一篇文章里面詳細的介紹如何結(jié)合以及代碼的分析。

第二，頁面的分析以及URL的提取

早期的爬蟲都很容易的運行，因為網(wǎng)頁都是直接使用HTML語言寫的，這些URL的內(nèi)容都是以文本或者DOM node存放在節(jié)點之中，我們可以很容易的使用正則表達式或者xpath語法來規(guī)則的解析這些數(shù)據(jù)。不過，現(xiàn)在很多的網(wǎng)頁偏向于Javascript 或者ajax來生成數(shù)據(jù)，你打開網(wǎng)頁查看源代碼之后，發(fā)現(xiàn)是需要運行一段腳本才來解決問題。所以，網(wǎng)頁的分析就相對以前來說復(fù)雜的多了，這個里面需要js的引擎來渲染頁面，才能得到那些隱藏的內(nèi)容。

第三，記錄哪些網(wǎng)頁已經(jīng)下載過的小本本–URL表

為了防止重復(fù)抓取，需要在一個hash表中記錄哪些網(wǎng)頁被下載過，再遇到它，我們就可以直接跳過它。采用哈希表的好處是，判斷一個網(wǎng)頁的URL是否存在表中，平均只需要一次（或者略多的）查找，效率上有巨大的優(yōu)勢。當(dāng)然，如果遇到?jīng)]有下載的網(wǎng)頁，還需要在下載完成后，將這個網(wǎng)頁的URL存到哈希表中，這個操作對哈希表來講也是非常簡單的。在一臺下載服務(wù)器上建立下和維護一張哈希表并不是難事。但是如果同時有上千臺服務(wù)器一起下載網(wǎng)頁，維護一張統(tǒng)一的哈希表就不是一件容易的事情。首先，這張哈希表大到一臺服務(wù)器存不下。其次，由于每個下載服務(wù)器在開始下載前和完成下載后都要訪問和維護這張表，以免不同的服務(wù)器做重復(fù)的工作，這個存儲哈希表的服務(wù)器的通信就成個整個爬蟲系統(tǒng)的瓶頸。那如何解決呢？

首先，明天每臺下載服務(wù)器的分工，也就是說在調(diào)度時看到某個URL就要知道交給哪臺服務(wù)器去下載，這樣就可以避免很多服務(wù)器對同一個URL做出是否需要下載的判斷了

另外，在明確分工的基礎(chǔ)上，判斷URL是否下載就可以批處理了，比如每次向哈希表(一組獨立的服務(wù)器)發(fā)送一大批話外音，或者每次更新一大批哈希表的內(nèi)容(下載器的緩存更新機制與同步機制)這樣通信的次數(shù)就大大減少了。

https://brucedone.com/2015/11/17/數(shù)學(xué)之美-關(guān)于圖論引申出來的爬蟲構(gòu)想/

網(wǎng)站

版權(quán)聲明：本文內(nèi)容由網(wǎng)絡(luò)用戶投稿，版權(quán)歸原作者所有，本站不擁有其著作權(quán)，亦不承擔(dān)相應(yīng)法律責(zé)任。如果您發(fā)現(xiàn)本站中有涉嫌抄襲或描述失實的內(nèi)容，請聯(lián)系我們jiasou666@gmail.com 處理，核實后本網(wǎng)站將在24小時內(nèi)刪除侵權(quán)內(nèi)容。

版權(quán)聲明：本文內(nèi)容由網(wǎng)絡(luò)用戶投稿，版權(quán)歸原作者所有，本站不擁有其著作權(quán)，亦不承擔(dān)相應(yīng)法律責(zé)任。如果您發(fā)現(xiàn)本站中有涉嫌抄襲或描述失實的內(nèi)容，請聯(lián)系我們jiasou666@gmail.com 處理，核實后本網(wǎng)站將在24小時內(nèi)刪除侵權(quán)內(nèi)容。