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