基于Bloom-Filter算法的URL过滤器的实现

一、 Bloom-Filter算法简介。
Bloom-Filter，即布隆过滤器，1970年由Bloom中提出。它可以用于检索一个元素是否在一个集合中，其优点是空间效率和查询时间都远远超过其他算法，其不足在于Bloom-Filter存在着误判。

二、 Bloom-Filter的基本思想。
Bloom-Filter算法的核心思想就是利用多个不同的Hash函数来解决“冲突”。

计算某元素x是否在一个集合中，首先能想到的方法就是将所有的已知元素保存起来构成一个集合R，然后用元素x跟这些R中的元素一一比较来判断是否存在于集合R中；我们可以采用链表等数据结构来实现。但是，随着集合R中元素的增加，其占用的内存将越来越大。试想，如果有几千万个不同网页需要下载，所需的内存将足以占用掉整个进程的内存地址空间。即使用MD5，UUID这些方法将URL转成固定的短小的字符串，内存占用也是相当巨大的。

于是，我们会想到用Hash table的数据结构，运用一个足够好的Hash函数将一个URL映射到二进制位数组（位图数组）中的某一位。如果该位已经被置为1，那么表示该URL已经存在。如图1所示。

（图1）

Hash存在一个冲突（碰撞）的问题，用同一个Hash得到的两个URL的值有可能相同。为了减少冲突，我们可以多引入几个Hash，如果通过其中的一个Hash值我们得出某元素不在集合中，那么该元素肯定不在集合中。只有在所有的Hash函数告诉我们该元素在集合中时，才能确定该元素存在于集合中。这便是Bloom-Filter的基本思想。

正如前面提及的，Bloom-Filter有可能会误判，也就是说会将一个并不存在于集合中的元素误认为已存在于集合中。但是另一方面，它绝对不可能会将一个已经存在于集合中的元素误认为是不存在于集合中。正所谓“宁可错杀一千，也不放过一个”。实验证明，位图数组长度越大，元素的数量越小，则Bloom-Filter误判的概率越小。

三、 Bloom-Filter的应用。
Bloom-Filter一般用于在大数据量的集合中判定某元素是否存在。例如邮件服务器中的垃圾邮件过滤器。在搜索引擎领域，Bloom-Filter最常用于网络蜘蛛(Spider)的URL过滤，网络蜘蛛通常有一个URL列表，保存着将要下载和已经下载的网页的URL，网络蜘蛛下载了一个网页，从网页中提取到新的URL后，需要判断该URL是否已经存在于列表中。此时，Bloom-Filter算法是最好的选择。

四、 Bloom-Filter的具体实现（C语言，提供源程序下载）。
这里的实现使用两个hash函数。
1. 数据结构。
/** bitmap array of bloom-filter */
struct bitmap_bloomfilter_t
{
u32_t * bitmap1; /* 第一个hash可映射到这里 */
u32_t * bitmap2; /* 第二个hash可映射到这里 */
long max_size; /*
};

2.函数。
bitmap_bloomfilter_t结构用于保存元素是否存在的位数组，我们需要相关的函数分别创建和释放它。
(1)bitmap_bloomfilter_t * create_bitmap_bloomfilter( long max_size )，创建bitmap_bloomfilter_t对象,参数max_size表示位图数组中最大容纳的元素数。
(2)void free_bitmap_bloomfilter( bitmap_bloomfilter_t ** bbf ),释放一个bitmap_bloomfilter_t对象，该对象同时被销毁。
bloom-filter过滤函数，判断一个元素是否在集合中。
(3)int bloomfilter_filter( const bitmap_bloomfilter_t * bbf, const void * data, long len )
以下是几个内部函数。我们还需要两个函数，一个用来来判断位图数组中某一位的值是否为1，另一个用于将位图数组中的某一位设置为1。
(4)static __INLINE__ BOOL get_bitmap_bit( const u32_t * bitmap, u32_t offset ), 判断位图数组中某一位的值是否为1。
(5)static __INLINE__ void set_bitmap_bit( const u32_t * bitmap, u32_t offset )，将位图数组中的某一位设置为1。
我们使用的两个hash函数。
(6)static u32_t hash_f1( const void * data, long len )
(7)static u32_t hash_f2( const void * data, long len )

2. 示例程序。

long * url[10] = {
“http://”,
“http://”,
“http://”,
“http://”,
“http://”,
“http://”,
“http://”,
“http://”,
“http://index.html”,
 "http://”
};

int main( int argc, char ** argv )
{
  int i;
  bitmap_bloomfilter_t * bbf =

     create_bitmap_bloomfilter( 10000 );/*创建位图数组结构*/
  for ( i=0; i<10;>分别对url中的10元素进行过滤操作*/
  {
    fprintf( stdout, “%ld->filtered(%d).\n”, data[i], 

     bloomfilter_filter(bbf, (void*)(data+i), strlen(url[i])) );
  }
  free_bitmap_bloomfilter( &bbf );/*释放位图数组结构*/
  return 0;
}