首页 我的文章
关于BloomFilter的简易探索

>>摘要:

有时,我们需要判断一个元素是否在一个集合中,而这个集合的数据量有时会非常庞大。比如判断某个邮件地址是否在黑名单中,网络爬虫时对网址进行判重等等。 如果将所有数据存入内存,则可能在大数据量时爆栈,且查询效率低。如果应用hashmap则会造成大量空间的浪费。 而布隆过滤器则可以解决这个问题,接下来将对布隆过滤器原理与应用进行研究与实践。

>>全文:

实验问题

    有时,我们需要判断一个元素是否在一个集合中,而这个集合的数据量有时会非常庞大。比如判断某个邮件地址是否在黑名单中,网络爬虫时对网址进行判重等等。
    如果将所有数据存入内存,则可能在大数据量时爆栈,且查询效率低。如果应用hashmap则会造成大量空间的浪费。
    而布隆过滤器则可以解决这个问题,接下来将对布隆过滤器原理与应用进行研究与实践。

实验算法

一、算法简介
    在大多应用中,当业务系统中发送一个请求时,会先从缓存中查询;若缓存中存在,则直接返回;若返回中不存在,则查询数据库。
    缓存穿透:当请求数据库中不存在的数据,这时候所有查询都会直接请求数据库,这种情况就是缓存穿透。
	
    为了解决这种情况,最先想到的算法是HashMap,通过映射Key值实现在O(1)的时间复杂度实现,但是哈希表通常不能满载,当数据量增大的时候,哈希表占据的空间也很可观。
在哈希表基础上结合位向量进行改进,就是布隆过滤器Bloom Filter。布隆过滤器是一种有失误率但时间空间效率更高的算法。
    一个空的布隆过滤器有M bit,初始置0。通过建立K个不同的映射函数,将元素映射到K个不同的位置,并将这些位置置1。
	

当建立布隆过滤器后,出现新的数据查询请求时,对查询数据进行映射,如果K个位置全为1,则查询数据可能存在(因为不同的元素映射结果可能相同), 但如果不全为1,则其一定不在数据库中。
二、控制误判率
    根据输入对象数量n和我们想要达到的误判率为p计算出布隆过滤器的大小m和哈希函数的个数k。
		

举例说明,如果要控制1亿email地址,期望误判率为0.01%,则所需布隆过滤器大小m约为24亿Bit,约为0.28G,而所需哈希函数为17个。
三、选择哈希函数
    当K值较小时,可以人工创建出不相关的K个函数。但当K值比较大时,难以人工创建完全不相关的K个函数能使得映射结果均匀分布。
	但注意到MD5、SHA1等算法创建的字符串各位是不相关的,也就是说可以将映射函数设置为对字符串不同位进行截取后mod M,即可快速得到不同的映射函数,或者给 Hash函数传入K个不同的salt值。
四、缺点与解决方案
缺点一:有误判
布隆过滤器真实失误率P公式如下:

当布隆过滤器的所有位均被置1时,此时布隆过滤器将起不到过滤功能。当提高M时,布隆过滤器的失误率将会下降,但占用空间也会提升。 因此可以考虑建一个占用较小的“白名单”,将每次失误的字符串存入白名单。而当白名单长度显著增长时,则说明此时的K与M不能满足实际需求,应该考虑重新计算K与M的值。 缺点二:无法删除 一旦将某个元素添加入布隆过滤器则无法删除,因为其对应位置的‘1’不只对应着这一个元素。(如右图绿色框中1)

解决方式为,初始化时将映射对应位+1,而删除某个元素时,则将对应位-1。但是这样每一个映射值对应的将不再是一个bit,根据可能重复的数量,布隆过滤器的长度可能会几何级增长。 因此不妨将删去的元素加入白名单,这样被删去的元素就可以通过过滤器。同样,当白名单过长时应考虑重新建立布隆过滤器。
五、算法研究
    1、随机生成200万个15-20位长度字符串模拟黑名单中的Email地址。
2、输入10万在黑名单中的字符串与10万不在名单中的字符串,观察失误率。
3、建立白名单,再次输入,观察失误率。

    
void HashK(char s[],int k[]){ //不同的哈希函数
	k[0]=SDBMHash(s)%M;
	k[1]=RSHash(s)%M;
	k[2]=JSHash(s)%M;
	k[3]=PJWHash(s)%M;
	k[4]=ELFHash(s)%M;
	k[5]=BKDRHash(s)%M;
	k[6]=DJBHash(s)%M;
	k[7]=APHash(s)%M;
	k[8]=(k[0]+k[1]*2)%M;
	k[9]=(k[3]+k[4]*2)%M;
	k[10]=(k[4]+k[5]*2)%M;
	k[11]=(k[6]+k[7]*2)%M;
	k[12]=(k[0]+k[1]*3+k[2]*16%M)%M;
	k[13]=(k[2]+k[4]+k[6])%M;
}

void createBF(){ //创建布隆过滤器
	FILE *fin,*fout;
	fin=fopen("Email.txt","r+");
	fout=fopen("BF.txt","w+");
	char s[20];
	int k[14];
	for(int n=0;n< M;n++){
		fscanf(fin,"%s",s);
		HashK(s,k);
		for(int i=0;i<14;i++)BF[k[i]]=1;
	}
	for(int i=0;i< N;i++)
		fprintf(fout,"%d ",BF[i]);
	fclose(fin);
	fclose(fout);
}

int ifInWhite(char s[]){  //是否在白名单中
	for(int i=0;i<20;i++)
		if(strcmp(s,White[i])==0) return 1;
	return 0;
}
int testInList(){ //测试集合内的元素
	FILE *fin2,*fout2;
	int count = 0;
	fin2=fopen("inList.txt","r+");
	char s[20];
	int k[14];
		for(int n=0;n<100000;n++){
		fscanf(fin2,"%s",s);
		if(ifInWhite(s)) {count++;continue;}
		HashK(s,k);
		if(BF[k[0]]&&BF[k[1]]&&BF[k[2]]&&BF[k[3]]&&BF[k[4]]&&BF[k[5]]&&
		BF[k[6]]&&BF[k[7]]&&BF[k[8]]&&BF[k[9]]&&BF[k[10]]&&BF[k[11]]&&
		BF[k[12]]&&BF[k[13]]);
		else{
			count ++;
		}
	}
	fclose(fin2);
return count;
}

int testOutList(){  //测试集合外的元素
	FILE *fin3;
	int count = 0;
	fin3=fopen("outList.txt","r+");
	char s[20];
	int k[14];
		for(int n=0;n<100000;n++){
		fscanf(fin3,"%s",s);
		if(ifInWhite(s)) continue;
		HashK(s,k);
		if(BF[k[0]]&&BF[k[1]]&&BF[k[2]]&&BF[k[3]]&&BF[k[4]]&&BF[k[5]]&&
		BF[k[6]]&&BF[k[7]]&&BF[k[8]]&&BF[k[9]]&&BF[k[10]]&&BF[k[11]]&&
		BF[k[12]]&&BF[k[13]]){
		count++;
		}
	}
	fclose(fin3);
	return count;
}

void add2White(){ //将失误元素和集合内元素的前两个加入到白名单
	FILE *fin4;
	int count = 0;
	fin4=fopen("White.txt","r+");
	while(fscanf(fin4,"%s",White[count++])!=EOF);
	fclose(fin4);
}
int main(){
	FILE *fout=fopen("result.txt","w+");
	memset(BF,0,sizeof(BF));
	memset(White,0,sizeof(White));
	createBF();
	fprintf(fout,"测试集合内元素,失误个数为:%d\n",testInList());
	fprintf(fout,"测试集合外元素,失误个数为:%d\n",testOutList());
	fprintf(fout,"将失误元素添加进白名单,再次测试。\n");
	add2White();
	fprintf(fout,"测试集合内元素,查找出已删除的元素个数为:%d\n",testInList());
    fprintf(fout,"测试集合外元素,失误个数为:%d\n",testOutList());
	system("pause");
return 0;
}
    

总结

集合内元素查找无失误,全部识别。
集合外随机生成的元素有17个查找失误,失误率为 P=17/100000=0.017%;
而添加白名单后,测试集合外元素无失误。
将集合内前两个元素加入白名单表示删除元素,成功识别。