一種網(wǎng)絡(luò)爬蟲系統(tǒng)中URL去重方法的研究

成 功 李小正 趙全軍

（北京網(wǎng)博視界科技有限公司，北京 100000）

近些年來，伴隨著科學(xué)技術(shù)的不斷進步，互聯(lián)網(wǎng)技術(shù)也不斷發(fā)展，通過互聯(lián)網(wǎng)這個平臺傳遞的信息越來越多，但是想要在這浩渺煙海的信息中找到對自己有用到的信息，只有借助于搜索引擎這一網(wǎng)絡(luò)利器，通過搜索引擎可以很容易的搜索出需要的信息，但是現(xiàn)今的搜索引擎還存在著一些缺陷， 們需要對采取一些方式來使網(wǎng)絡(luò)爬蟲優(yōu)先選取那些符合搜索要求的網(wǎng)頁，在這種情況下，如何對網(wǎng)絡(luò)爬蟲系統(tǒng)中進行設(shè)置來提高URL去重的能力將會對網(wǎng)絡(luò)爬蟲的運行效率產(chǎn)生不小的影響.下文將就如何簡單的對URL去重進行闡述.

1 網(wǎng)絡(luò)爬蟲系統(tǒng)簡介

網(wǎng)絡(luò)爬蟲是一種按照一定的規(guī)則，自動的抓取萬維網(wǎng)信息的程序或者腳本。另外一些不常使用的名字還有螞蟻，自動索引，模擬程序或者蠕蟲。 網(wǎng)絡(luò)爬蟲是捜索引擎抓取系統(tǒng)的重要組成部分。爬蟲的主要目的是將互聯(lián)網(wǎng)上的網(wǎng)頁下載到本地形成一個或聯(lián)網(wǎng)內(nèi)容的鏡像備份。

1.1 網(wǎng)絡(luò)爬蟲的基本原理。網(wǎng)絡(luò)爬蟲是一個自動提取網(wǎng)頁的程序，它為搜索引擎從萬維網(wǎng)上下載網(wǎng)頁，是搜索引擎的重要組成，傳統(tǒng)爬蟲從一個或若干初始網(wǎng)頁的URL開始，獲得初始網(wǎng)頁上的URL，在抓取網(wǎng)頁的過程中，不斷從當(dāng)前頁面上抽取新的URL放入隊列，知道滿足系統(tǒng)的一定的初始條件.

1.2 網(wǎng)絡(luò)爬蟲的基本工作流程。網(wǎng)絡(luò)爬蟲的基本工作流程如下：（1）首先選取一部分精心挑選的種子URL，（2）將這些URL放入待抓取URL隊列，（3）從待抓取URL隊列中提取出待抓取在URL，解析DNS，并且得到主機的ip，并將URL對應(yīng)的網(wǎng)頁下載下來，存儲進已下載網(wǎng)頁庫中，此外，將這些URL放進已抓取URL隊列。（4）分析已抓取URL隊列中的URL，分析其中的其他的URL，并且將URL放入待抓取URL隊列，從而進入下一個循環(huán)。

1.3 網(wǎng)絡(luò)爬蟲面臨的缺陷。網(wǎng)絡(luò)信息中數(shù)量龐大，種類繁多，各種各樣的鏈接數(shù)不勝數(shù)，當(dāng)使用網(wǎng)絡(luò)爬蟲進行搜索時，相同的 URL的鏈接很有可能會被加入到隊列中，從而會使網(wǎng)絡(luò)爬蟲進行了大量的重復(fù)無用的工作，使網(wǎng)絡(luò)爬蟲的工作效率大打折扣。將重復(fù)相同的URL剔除出隊列，提升網(wǎng)絡(luò)爬蟲的的效率，這種方式就是URL 去重。網(wǎng)絡(luò)爬蟲的URL去重是一項復(fù)雜的工作，因為即使是最小的URL庫所包含的數(shù)據(jù)也是一個天文數(shù)字。如果沒有URL去重或者是去重的速度無法達(dá)到要求，這將會對下載造成極大的影響。

2 網(wǎng)絡(luò)爬蟲URL去重的方案

在爬蟲啟動工作的過程中，我們不希望同一個網(wǎng)頁被多次下載，如果無法忽略已經(jīng)爬過的網(wǎng)頁。多次爬取同一個網(wǎng)頁浪費cpu資源，還極有可能陷入死循環(huán)中。而想要控制這種重復(fù)性下載問題，就要考慮下載所依據(jù)的超鏈接，只要能夠控制待下載的URL不重復(fù)，基本可以解決同一個網(wǎng)頁重復(fù)下載的問題。非常容易想到，在搜索引擎系統(tǒng)中建立一個全局的專門用來檢測，是否某一個URL對應(yīng)的網(wǎng)頁文件曾經(jīng)被下載過的URL存儲庫，這就是方案。而后為了能夠使網(wǎng)絡(luò)爬蟲更好的進行工作，更加高效的工作，根據(jù)上文的敘述，建立一個URL存儲庫，將下載后的URL通過內(nèi)存要比從磁盤上進行檢測要高效很多。在搜索引擎中建立url檢測機制，如果一個url被爬取過就記錄下來，在爬取新的url之前先和url庫中的資源進行對比，如果沒有該記錄，則正常解析爬取資源，如果有則忽略該url。接下來考慮的就是如何讓這個去重的過程更高效的問題。下面將就URL去重的方案進行介紹：

2.1 建立數(shù)據(jù)庫對下載的URL進行對比

這里，就是指把每個已經(jīng)下載過的URL進行順序存儲。你可以把全部已經(jīng)下載完成的URL存放到磁盤記事本文件中。每次有一個爬蟲線程得到一個任務(wù)URL開始下載之前，通過到磁盤上的該文件中檢索，如果沒有出現(xiàn)過，則將這個新的URL寫入記事本的最后一行，否則就放棄該URL的下載。這種方式幾乎沒有人考慮使用了，但是這種檢查的思想是非常直觀的。試想，如果已經(jīng)下載了100億網(wǎng)頁，那么對應(yīng)著100億個鏈接，也就是這個檢查URL是否重復(fù)的記事本文件就要存儲這100億URL，況且，很多URL字符串的長度也不小，占用存儲空間不說，查找效率超級低下，因此這個方案行不通。

2.2 對url進行hash運算映射到某個地址，將該url和hash值當(dāng)做鍵值對存放到hash表中，只需要對需要檢測的URL的hash的映射進行比對，從而就可以對URL是否存在進行判斷。因此，原來的URL庫就可以簡化為hash庫，這要比URL簡便很多，但是需要考慮hash碰撞的問題，在設(shè)計中需要對hash函數(shù)進行考慮，避免因考慮不周造成hash碰撞。

2.3URL采用MD5加密，md5也是采用了基于hash算法，MD5算法能夠?qū)⑷魏巫址畨嚎s為128位整數(shù)，并映射為物理地址，MD5也是經(jīng)過時間驗證的，MD5進行Hash映射碰撞概率很低。

2.4 采用布隆過濾器，它是一種space efficient的概率型數(shù)據(jù)結(jié)構(gòu)，用于判斷一個元素是否在集合中。在垃圾郵件過濾的黑白名單方法、爬蟲（Crawler）的網(wǎng)址判重模塊中等等經(jīng)常被用到。哈希表也能用于判斷元素是否在集合中，但是布隆過濾器只需要哈希表的1/8或1/4的空間復(fù)雜度就能完成同樣的問題。布隆過濾器可以插入元素，但不可以刪除已有元素。其中的元素越多，false positive rate（誤報率）越大，但是false negative（漏報）是不可能的。

結(jié)語

本文介紹了網(wǎng)絡(luò)爬蟲URL去重的意義，并就網(wǎng)絡(luò)爬蟲中URL的去重方案進行了介紹。

[1]周立柱 ，林 玲. 聚焦爬蟲技術(shù)研究綜述 [J ]. 計算機應(yīng)用，2005，23 （9）.