在爬蟲系統中，在內存中維護著兩個關于URL的隊列，ToDo隊列和Visited隊列，ToDo隊列存放的是爬蟲從已經爬取的網頁中解析出來的即將爬取的URL，但是網頁是互聯的，很可能解析出來的URL是已經爬取到的，因此需要VIsited隊列來存放已經爬取過的URL。當爬蟲從ToDo隊列中取出一個URL的時候，先和Visited隊列中的URL進行對比，確認此URL沒有被爬取后就可以下載分析來。否則舍棄此URL，從Todo隊列取出下一個URL繼續工作。

然后，我們知道爬蟲在爬取網頁時，網頁的量是比較大的，直接將所有的URL直接放入Visited隊列是很浪費空間的。因此引入bloom filter！

(關于使用bloomfilter的原因：

visited隊列中url過多，消耗內存空間是一方面。還有一個重要的原因，在從todo隊列中取出一個新的URL時，必須和 visited中所有URL比較，確保沒有處理過。那么如果直接比較的話，是要比較N(visited中所有url個數)次的，而且這個N相當大，效率明 顯不夠。采用bloom filter，最多只要比較K(我在文章中寫的，相互獨立的散列函數的個數)次，因為只要一個散列函數的散列值對應的位是0，就可以確定這個URL沒有處 理過。

)

我們把bloom filer設置為m個bit，全部初始為0。

對每一個URL，進行K(K

經過上述處理的bloom filter實際上構成了我們所說的Visited隊列，當我們從ToDo隊列中取出一個新的URL時，同樣，進行相同的K次哈希，每進行一次哈希，查看bloom filter中對應位，只要發現某位是0，就可以確定這個URL是沒有處理過的，可以繼續下載處理。

那么，原理清楚之后，還有幾個問題沒有解決。

1、bloom filter是有可能發生錯誤的，因為不處理碰撞，也就是說，有可能把不屬于這個集合的元素誤認為屬于這個集合

錯誤率的計算：

在n個URL都進行k次散列加入之后，bloomfilter中某位是0的概率

錯誤率(即一個新的URL恰好k次散列的值對應的位都已經是1的概率)

2、哈希函數個數K的確定

k = ln2· (m/n)時(具體數學分析見http://blog.csdn.net/jiaomeng/article/details/1495500)

3、bloomfilter位數M的確定

我們可以想到，M的大小越大，錯誤率就會越小，但是數學證明給出了一個下界。即M = log2eN = 1.44N。

附上java代碼

1 /**屈永泉 布隆過濾器 快速確定哪些網頁已經被下載過*/

2

3 package crawler;4

5 import java.util.BitSet;6

7 public classBloomFilter {8 private int defaultSize = 5000 << 10000;9 private int basic = defaultSize - 1;10 private BitSet bits = newBitSet(defaultSize);11

12 private int[] lrandom(String key) { //產生八個隨機數并返回

13 int[] randomsum = new int[8];14 for (int i = 0; i < 8; i++)15 randomsum[0] = hashCode(key, i + 1);16 returnrandomsum;17 }18

19 //將一個URL加入

20 public synchronized voidadd(String key) {21 int keyCode[] =lrandom(key);22 for (int i = 0; i < 8; i++)23 bits.set(keyCode[i]); //將指定索引處的位設置為 true

24 }25 }26

27 //判斷一個URL是否存在

28 publicboolean exist(String key) {29 int keyCode[] =lrandom(key);30 if (bits.get(keyCode[0])31 && bits.get(keyCode[1]) //返回指定索引處的位值。

32 && bits.get(keyCode[2]) && bits.get(keyCode[3])33 && bits.get(keyCode[4]) && bits.get(keyCode[5])34 && bits.get(keyCode[6]) && bits.get(keyCode[7])) {35 return true;36 }37 return false;38 }39

40

41 private int hashCode(String key, intQ) {42 int h = 0;43 int off = 0;44 char val[] = key.toCharArray(); //將此URl轉換為一個新的字符數組

45 int len =key.length();46 for (int i = 0; i < len; i++) {47 h = (30 + Q) * h + val[off++];48 }49 return basic &h;50 }51

52

53 /*public static void main(String[] args) { // TODO Auto-generated method54 long pre = 0;55 long post = 0;56 pre = System.nanoTime();57 BloomFilter f = new BloomFilter(); //初始化58 f.add("http://www.agrilink.cn/"); f.add("http://www.baidu.com/");59 System.out.println(f.exist("http://www.baidu.com/"));60 System.out.println(f.exist("http://www.baidud.com/"));61 post = System.nanoTime();62 System.out.println("Time: " + (post - pre));63

64 }65 */

66

67 }

View Code

總結

以上是生活随笔為你收集整理的java bloomfilter_爬虫技术之——bloom filter（含java代码）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。