一種網絡爬蟲系統中URL去重方法的研究

成 功 李小正 趙全軍

（北京網博視界科技有限公司，北京 100000）

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

1 網絡爬蟲系統簡介

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

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

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

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

2 網絡爬蟲URL去重的方案

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

2.1 建立數據庫對下載的URL進行對比

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

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

2.3URL采用MD5加密，md5也是采用了基于hash算法，MD5算法能夠將任何字符串壓縮為128位整數，并映射為物理地址，MD5也是經過時間驗證的，MD5進行Hash映射碰撞概率很低。

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

結語

本文介紹了網絡爬蟲URL去重的意義，并就網絡爬蟲中URL的去重方案進行了介紹。

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