網(wǎng)頁(yè)消重中多維布隆過濾器算法的運(yùn)用論文
0 引言。
進(jìn)入 21 世紀(jì)以后，隨著電子計(jì)算機(jī)以及相關(guān)技術(shù)的迅猛發(fā)展和網(wǎng)絡(luò)通信設(shè)備的大量普及，互聯(lián)網(wǎng)的總體規(guī)模日益增大，日新月異的互聯(lián)網(wǎng)技術(shù)以及海量的互聯(lián)網(wǎng)信息也促進(jìn)了社會(huì)、經(jīng)濟(jì)和科技的高速發(fā)展，增加了人們獲取信息的渠道和速度。根據(jù) 2015 年 11月的最新數(shù)據(jù)，互聯(lián)網(wǎng)上活動(dòng)網(wǎng)站的數(shù)量達(dá)到了 902,997,800 個(gè)[1].網(wǎng)站的快速增長(zhǎng)同時(shí)也意味著互聯(lián)網(wǎng)中信息的急速膨脹，這些信息有些是有用的、有些是沒用的、有些甚至完全是一些垃圾頁(yè)面。面對(duì)由于互聯(lián)網(wǎng)信息爆炸帶來(lái)的信息孤島、信息搜集困難等現(xiàn)象，人們發(fā)明了搜索引擎[2-4]以解決人們快速在互聯(lián)網(wǎng)中找到所求的需求。但是，由于搜索引擎的采集器是由程序自動(dòng)運(yùn)行的，所以在抓取網(wǎng)頁(yè)信息的同時(shí)，也會(huì)收集到很多重復(fù)網(wǎng)頁(yè)。因此，如果沒有一個(gè)高效的URL 去重模塊，用以防止系統(tǒng)對(duì)已經(jīng)抓取過的網(wǎng)頁(yè)進(jìn)行重復(fù)抓取，浪費(fèi)寶貴的網(wǎng)絡(luò)帶寬和 CPU 時(shí)間，網(wǎng)絡(luò)爬蟲系統(tǒng)必將不堪重負(fù)。
在眾多的 URL 去重技術(shù)中[5-7] ,布隆過濾器（Bloom Filter）[8]是其中優(yōu)秀的一個(gè)，而其主要缺點(diǎn)在于較高的誤識(shí)別率，但若使用多維布隆過濾器進(jìn)行識(shí)別，可以大大降低誤識(shí)別率。本文充分利用多維布隆過濾器查詢快速、資源占有量少的特點(diǎn)，提出一種基于多維布隆過濾器的網(wǎng)頁(yè)搜索去重方法，并給出程序設(shè)計(jì)方案及偽代碼描述。
1 布隆過濾器。
在互聯(lián)網(wǎng)中，要查找一個(gè) URL 是否己經(jīng)被抓取過，首先會(huì)想到的方法就是建立一個(gè)已抓取 URL 集合，然后查找新的 URL 是否存在已抓取 URL 集合中，如果用普通的順序查找法，效率顯然很低。而另一個(gè)比較簡(jiǎn)單的辦法是采取傳統(tǒng)的 hash 方法，即把每個(gè)URL 看成一個(gè)元素，這就需要把每個(gè)元素存儲(chǔ)在 hash表中。在每次發(fā)現(xiàn)一個(gè)新的元素時(shí)，首先會(huì)通過 hash函數(shù)計(jì)算出這個(gè)元素的對(duì)應(yīng)位置，之后使用這個(gè)位置的元素與這個(gè)新元素進(jìn)行對(duì)比，如果兩者相同，就說(shuō)明這個(gè)新元素是重復(fù)的，反之則說(shuō)明這個(gè)新元素是還未保存過的。傳統(tǒng)的 hash 方法不會(huì)發(fā)生錯(cuò)誤，而且存在于 hash 表中的數(shù)據(jù)也可以隨時(shí)刪除。但是，對(duì)于網(wǎng)頁(yè)去重來(lái)說(shuō)，只需判斷一個(gè)特定的元素是否存在于集合中。因此，使用 hash 表保存下整個(gè) URL 的內(nèi)容會(huì)造成很大的內(nèi)存浪費(fèi)，然而內(nèi)存資源有限，顯然傳統(tǒng)的 hash 方法不能很好的滿足需求。
布隆過濾器[9-11]是由 Howard Bloom 在 1970 年提出的。他僅使用了一系列的 bit 位來(lái)保存數(shù)據(jù)，就可以檢測(cè)一個(gè)元素是否已經(jīng)存在于集合內(nèi)，因此這種算法有著很好的空間利用率。但是為了節(jié)約空間，這種算法也存在著一些問題，它會(huì)對(duì)元素產(chǎn)生錯(cuò)判。不過慶幸的是，這個(gè)算法只會(huì)對(duì)在集合內(nèi)的元素產(chǎn)生錯(cuò)判，但是并不會(huì)對(duì)不在集合內(nèi)的元素產(chǎn)生錯(cuò)判。也就是說(shuō)，如果布隆過濾器返還的結(jié)果如果是 false,說(shuō)明元素確實(shí)不在集合內(nèi)；如果返還的是 ture,只能說(shuō)明元素可能存在于集合中。因此布隆過濾器實(shí)際上是一種犧牲了正確率換取時(shí)間和空間的算法。
1.1 布隆過濾器介紹。
布隆過濾器的原理如下[12]:一個(gè)布隆過濾器由 k個(gè)相互獨(dú)立的哈希函數(shù) h1,h2,…，hk（k 值域?yàn)閇0,1,2,…，m],是整數(shù)）和一個(gè)位向量組成，初始時(shí)，位向量?jī)?nèi)全部為 0.當(dāng)需要插入一個(gè)新數(shù)據(jù)時(shí)，用 k個(gè)哈希函數(shù)對(duì) n 個(gè)數(shù)據(jù)對(duì)象的集合 S={sl,s2,…，sn }（m > n）的某個(gè)數(shù)據(jù)對(duì)象計(jì)算一個(gè)地址序（hi（s1），h2（sl），…，hk（sl）），然后將位向量對(duì)應(yīng)地址序列的位置置為 1,稱該位向量裝入了 s1.
對(duì)于查詢某個(gè)數(shù)據(jù)對(duì)象 s2 是否存在于集合時(shí)，同樣先檢查表示 s2 的位向量對(duì)應(yīng)該數(shù)據(jù)對(duì)象地址序列的位，如果均為 1,則該數(shù)據(jù)對(duì)象屬于位向量集，否則不屬于位向量集。但是，即使是采用均勻的哈希函數(shù)，并且使用了多個(gè)不同的 hash 函數(shù)，地址沖突也是不能避免的，因此布隆過濾器算法可能對(duì)位向量中的同一個(gè)位多次置 1.所以在進(jìn)行數(shù)據(jù)查詢時(shí)可能出現(xiàn)錯(cuò)判。關(guān)于布隆過濾器算法的缺點(diǎn)，會(huì)在 1.3 做詳細(xì)討論。
由以上分析可知，當(dāng)布隆過濾器算法用于 URL去重時(shí)，由于每個(gè)地址不需要存儲(chǔ) URL 內(nèi)容，只需存儲(chǔ) 1 或 0.因此，每個(gè)地址只需要一個(gè) bit 的空間。在每次網(wǎng)絡(luò)爬蟲得到一個(gè)新的 URL 的時(shí)候，會(huì)先判斷這個(gè)元素是否屬于集合，此時(shí)會(huì)對(duì)該元素重新進(jìn)行多次哈希，當(dāng)哈希后所得的對(duì)應(yīng)位置都為 1 時(shí)，就判斷該元素已經(jīng)存在于集合中。那么就拋棄這個(gè) URL,反之，就保存這個(gè) URL,并且更新集合信息。具體原理圖如下圖 1.
1.2 布隆過濾器的優(yōu)點(diǎn)。
布隆過濾器的優(yōu)點(diǎn)是空間效率和查詢時(shí)間都遠(yuǎn)遠(yuǎn)超過一般的算法。在占用空間上，布隆過濾器只需要哈希表 1/8~1/4 的大小就能解決同樣的問題[13];更重要的是，在時(shí)間復(fù)雜度方面，布隆過濾器的查找時(shí)間為常數(shù)，不隨過濾器增大而變慢。
1.3 布隆過濾器的缺點(diǎn)。
由以上分析可知，布隆過濾器算法比起普通算法，在時(shí)間和空間利用率上有著明顯的優(yōu)勢(shì)，但是布隆過濾器算法也并非十全十美的，他存在著以下問題：
�。�1）因?yàn)槔霉潭ǖ? hash 函數(shù)，并且得到的存儲(chǔ)結(jié)果僅僅是某個(gè)槽號(hào)，因此查找的時(shí)間是個(gè)常數(shù)，但是每個(gè)槽中存儲(chǔ)的不是實(shí)際 url,因此，可能會(huì)出現(xiàn)某個(gè) url 映像的幾個(gè)位置都己經(jīng)被其他 url 占據(jù)的情況，產(chǎn)生錯(cuò)判。
�。�2）因?yàn)橐粋�(gè) url 對(duì)應(yīng)多個(gè)槽，而且這些槽是可以重復(fù)利用的，因此不用處理沖突。但是正因?yàn)槿绱嗽撍惴ú荒茈S便刪除某個(gè)已經(jīng)存在的 url,否則會(huì)出錯(cuò)。
2 一種改進(jìn)布隆過濾器算法。
根據(jù)上文提及到的，布隆過濾器的缺點(diǎn)是其誤識(shí)別率，因此，如何在不降低判別性能的前提下降低布隆過濾器的誤識(shí)別率就是研究的主要方向，本文基于此目的提出了一種改進(jìn)的布隆過濾器算法，稱為多維布隆過濾器。
2.1 基本思想。
多維布隆過濾器的基本想法是，通過使用 S 組位向量來(lái)表達(dá)數(shù)據(jù)集合，每組位向量對(duì)應(yīng)k個(gè)hash函數(shù)，每組位向量包含 2 個(gè)位向量，其中一個(gè)是 N 位大小的V1,另一個(gè)是 N/k 位大小的 V2,每組 hash 函數(shù)劃分到兩部分 k1和 d2,用于 V1映射的是 k1,用于 V2映射的是 d2.
插入元素時(shí)，對(duì)于每組位向量，k1把該元素映射到 V1中并在 V1對(duì)應(yīng)位置置 1,k2把數(shù)據(jù)元素映射到V2中并在 V2對(duì)應(yīng)位置置 1.判定元素時(shí)，分別檢查經(jīng)過每組的 hash 函數(shù) k1和 k2的映射后，V1和 V2的相關(guān)位置是否為 1,若有一組位向量全為 1,則認(rèn)為該元素屬于集合。
形式化描述多維布隆過濾器算法就是如下：
其中，（ s ,i , j）V表示第 s 組位向量中第 i 個(gè)向量中的第 j 位。
2.2 性能分析。
分析上述算法，可以看出來(lái)，多維布隆過濾器實(shí)際上是由多組基本的布隆過濾器構(gòu)成的。每個(gè)布隆過濾器都作為多維布隆過濾器的一部分，參加整體運(yùn)算。
因此，這里可以得到每組兩個(gè)位向量的誤識(shí)別率為：
由公式可知，在 s,k,n 這些參數(shù)一致的情況下，多維布隆過濾器同標(biāo)準(zhǔn)布隆過濾器相比，具有較低的誤判率，并且維數(shù)越高，誤判率越低。
不同維度的過濾器在搜索去重中處于并行工作的狀態(tài)，因此，基于此技術(shù)應(yīng)用實(shí)現(xiàn)的多維布隆過濾器引擎查詢時(shí)間和標(biāo)準(zhǔn)布隆過濾器引擎查詢時(shí)間相等。
多維布隆過濾器引擎每一維都使用了 2 個(gè)標(biāo)準(zhǔn)的布隆過濾器引擎，參數(shù)一致的情況下，占用的存儲(chǔ)空間是標(biāo)準(zhǔn)的布隆過濾器引擎的 2S 倍。
但是當(dāng)維數(shù)過多時(shí)，要讓每一個(gè)維度都處于并行工作狀態(tài)對(duì) CPU 要求較高，而且維數(shù)越多，對(duì)存儲(chǔ)空間的需求也就越大。
3 應(yīng)用與評(píng)價(jià)。
對(duì)于上面章節(jié)討論的改進(jìn)布隆過濾器算法-多維布隆過濾器算法的理論研究，我們?nèi)孕枰M(jìn)行大量的實(shí)驗(yàn)對(duì)其進(jìn)行驗(yàn)證。本論文設(shè)計(jì)實(shí)現(xiàn)程序，從而模擬了兩種算法，進(jìn)而通過實(shí)驗(yàn)對(duì)兩種算法的性能進(jìn)行比較。
3.1 實(shí)驗(yàn)評(píng)價(jià)標(biāo)準(zhǔn)。
為了能夠更加直觀的對(duì)比試驗(yàn)結(jié)果，試驗(yàn)根據(jù)重復(fù)網(wǎng)頁(yè)對(duì)搜索引擎的影響制定了以下三個(gè)主要的比較數(shù)據(jù)。他們是：
�。�1）運(yùn)行速度：在一定抓取范圍內(nèi)，每種算法完成所用的時(shí)間。因?yàn)閷?shí)際運(yùn)用中網(wǎng)頁(yè)數(shù)量過于龐大，因此這里設(shè)定一個(gè)固定時(shí)間，在這段時(shí)間內(nèi)抓取到非重復(fù) URL 的數(shù)量越多，則算法運(yùn)行的速度越快。
速度=非重復(fù) URL 數(shù)量/時(shí)間
（2）重復(fù)率：也就是在第二章提到的重要評(píng)價(jià)指標(biāo)。
重復(fù)率=重復(fù)的 URL /抓取到的 URL 總數(shù)
�。�3）空間利用率：用于去重的位向量組所占空間。
用 Bit 為單位。
3.2 實(shí)驗(yàn)步驟。
本實(shí)驗(yàn)使用 Heritrix 作為爬蟲，主要抓取一些時(shí)事新聞。因此，實(shí)驗(yàn)首先抓取幾個(gè)常用的站頁(yè)面做基礎(chǔ)。本論文中是先抓取的新浪，網(wǎng)易，騰訊，搜狐。之后在百度里搜索某個(gè)新聞關(guān)鍵詞做為基礎(chǔ)。
開始抓取搜索到的網(wǎng)頁(yè)。之后分別使用三種不同的算法，在抓取范圍相同的前提下，設(shè)定時(shí)間為 1 小時(shí)。
并且，為了實(shí)驗(yàn)數(shù)據(jù)更加準(zhǔn)確，本實(shí)驗(yàn)為每種算法設(shè)置不同的可選參數(shù)來(lái)驗(yàn)證前面的結(jié)論，具體如下：
●布隆過濾器：hash 函數(shù)個(gè)數(shù) k;向量空間大小 N
●多維布隆過濾器：每組 hash 函數(shù)個(gè)數(shù) k;向量空間大小 N;向量維度 S
3.3 結(jié)果與分析。
對(duì)于實(shí)驗(yàn)結(jié)果，我們首先對(duì)比多維布隆過濾器中，在 k=4,N=150 時(shí)，不同向量維度 S 下的誤識(shí)別率變化，如圖 2 所示。
從圖 4.5 中，我們可以得到結(jié)論，誤識(shí)別率隨著 S值的增加而減小。S 值增加往往意味著，多維布隆過濾器算法所需的空間大小也相應(yīng)提高，所以，在實(shí)際中，我們一般取 S 的值小于 4.
隨后，我們固定 S=4,k=4,對(duì)比標(biāo)準(zhǔn)布隆過濾器和多維布隆過濾器在位向量空間變化時(shí)的誤識(shí)別率，如圖 3 所示。
由上圖可得，多維布隆過濾器和標(biāo)準(zhǔn)布隆過濾器的誤識(shí)別率隨著位向量空間的增加一直降低，而且多維布隆過濾器誤識(shí)別率相比標(biāo)準(zhǔn)過濾器一直都要低。
最后，我們固定 S=4,N=150,對(duì)比標(biāo)準(zhǔn)布隆過濾器和多維布隆過濾器在hash函數(shù)數(shù)量k變化時(shí)的誤識(shí)別率，如圖 4 所示。
從圖 4 中，我們可以得到結(jié)論，誤識(shí)別率隨著 k值的增加而減小。k 值增加往往意味著，hash 算法所需的運(yùn)算時(shí)間也相應(yīng)提高，所以，在實(shí)際中，我們一般取 k 的值小于 4.
綜上，通過實(shí)驗(yàn)可以得到結(jié)論，hash 函數(shù)數(shù)量以及位向量空間大小都可以影響布隆過濾器和多維布隆過濾器的誤識(shí)別率，向量的維度也可以影響多維布隆過濾器的誤識(shí)別率。并且，在相同 hash 函數(shù)數(shù)量或向量空間大小時(shí)，多維布隆過濾器的誤識(shí)別率均低于布隆過濾器。
4 結(jié)語(yǔ)。
本文詳細(xì)闡述了布隆過濾器的原理，通過對(duì)原理、實(shí)現(xiàn)步驟進(jìn)行分析，得出此算法在網(wǎng)頁(yè)消重中的作用以及缺陷。此后，根據(jù)布隆過濾器存在的誤識(shí)別率的缺點(diǎn)，本文提出了一種改進(jìn)的布隆過濾器算法--多維布隆過濾器，降低了傳統(tǒng)布隆過濾器算法的誤識(shí)別率。實(shí)驗(yàn)結(jié)果表明：多維布隆過濾器的誤識(shí)別率要顯著低于傳統(tǒng)的布隆過濾器算法，能夠顯著提高網(wǎng)頁(yè)消重的性能。
參考文獻(xiàn)
[1] Netcraft.November 2015 Web Server Survey [OL].[2015-11-16].
[2] 阮衛(wèi)華。搜索引擎優(yōu)化技術(shù)的研究與實(shí)現(xiàn)[J].軟件，2014,35（7）：72-77
[3] 鄭曉健。面向領(lǐng)域主題的智能搜索引擎設(shè)計(jì)[J].軟件，2014,35（3）：4-5
[4] 郭世龍，王晨升。主題爬蟲設(shè)計(jì)與實(shí)現(xiàn)[J].軟件，2013,34（12）：107-109
[5] Manber U.Finding similar files in a large file system[A].Proceedings of the USENIX winter 1994 technical conference[C].1994,1.
【網(wǎng)頁(yè)消重中多維布隆過濾器算法的運(yùn)用論文】相關(guān)文章：
算法類論文開題報(bào)告11-11
網(wǎng)頁(yè)設(shè)計(jì)論文開題報(bào)告12-28
合作寫作在應(yīng)用文教學(xué)中的策略運(yùn)用論文09-18
民族地區(qū)英語(yǔ)寫作教學(xué)中寫長(zhǎng)法的運(yùn)用論文09-11
“化題為象”在閱讀與寫作教學(xué)中的運(yùn)用論文09-04
情景教學(xué)在初中語(yǔ)文寫作教學(xué)中運(yùn)用的論文07-27
績(jī)效工資的算法10-13
失業(yè)保險(xiǎn)的算法06-10