文档章节

一个简单的布隆过滤器

a
 alex_wei
发布于 2013/07/03 02:39
字数 880
阅读 255
收藏 11

布隆过滤器(Bloom Filter)是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法,缺点是有一定的误识别率和删除困难。

——摘自维基百科

因为查找别的资料,偶尔发现这一利器。兴趣所致,写了一个简单的C实现。当然很多问题没有考虑在内,仅就核心概念给出了一个缩略版实现,做为一个提醒,加深一下印象。

simple_bf.h:

#ifndef _SIMPLE_BF_H_
#define _SIMPLE_BF_H_

#include <stdint.h>
#include <stdbool.h>

#define VEC_LEN (1024 * 1024 * 64 + 1)

#ifdef __cplusplus
extern "C" {
#endif

typedef struct _bf_vec {
        uint64_t part[VEC_LEN];
} bf_vec_t;

extern bool bf_add(bf_vec_t *vec, const char *str);

extern bool bf_is_contains(bf_vec_t *vec, const char *str);

#ifndef likely
#define likely(x) __builtin_expect((x),1)
#endif

#ifndef unlikely
#define unlikely(x) __builtin_expect((x),0)
#endif

#ifdef __cplusplus
}
#endif

#endif
simple_bf.c:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "simple_bf.h"

/* return false means the arg bit is over the bit length of the arg vec,
 * otherwise return true means successfully set the right bit.
 * for simple, only consider about these two conditions */
static inline __attribute__((always_inline)) bool bf_set_bit(bf_vec_t *vec, uint64_t bit)
{
	uint64_t part_cnt = bit / 64;
	if (unlikely(part_cnt > VEC_LEN))
		return false;
	uint8_t mod = bit % 64;
	vec->part[part_cnt] |= (1ULL << mod);
	return true;	
}

static inline __attribute__((always_inline)) bool bf_test_bit(bf_vec_t *vec, uint64_t bit)
{
	uint64_t part_cnt = bit / 64;
	if (unlikely(part_cnt > VEC_LEN))
		return false;
	uint8_t mod = bit % 64;
	return ((vec->part[part_cnt] & (1ULL << mod)) != 0);	
}

/* the seed vector and the BKDR hash function */
static uint32_t seeds[8] = {31, 131, 1313, 13131, 131313, 1313131, 13131313, 131313131};
static uint32_t bkdr_hash_modified(const char *str, uint32_t seed)
{
	register uint32_t hash = 0;
	uint32_t ch;
	while ((ch = (uint32_t)*str++)) {
		hash = hash * seed + ch;
	}
	return hash;
}

bool bf_add(bf_vec_t *vec, const char *str)
{
	int i;
	for (i = 0; i < 8; ++i) {
		uint32_t val = bkdr_hash_modified(str, seeds[i]);
		if (!bf_set_bit(vec, val))
			return false;
	}
	return true;
}

bool bf_is_contains(bf_vec_t *vec, const char *str)
{
	int i;
	for (i = 0; i < 8; ++i) {
		uint32_t val = bkdr_hash_modified(str, seeds[i]);
		if (!bf_test_bit(vec, val))
			return false;
	}
	return true;
}

#ifndef NDEBUG 
int main1(int argc, char *argv[])
{
	if (argc < 3) {
		fprintf(stderr, "usage: bf as0 [as1 as2 ...] ts\n"
				"as means string to add to the bloom filter\n"
				"ts means the string to test if it is in the filter vector\n"
				);
		return 1;
	}

	bf_vec_t *vec = calloc(1, sizeof(bf_vec_t));
	if (vec == NULL)
		return 1;
		
	int i;
	for (i = 1; i < argc - 1; ++i) {
		if (bf_add(vec, argv[i]))
			printf("add to bloom filter successed, string %s\n", argv[i]);
		else
			printf("add to bloom filter FAILED, string %s\n", argv[i]);
	}
	printf("------------------------------------------------------------------\n");
	if (bf_is_contains(vec, argv[argc - 1]))
		printf("test string %s is in bloom filter\n", argv[argc - 1]);
	else
		printf("test string %s is NOT in bloom filter\n", argv[argc - 1]);

	free(vec);
	return 0;
}

int main2(int argc, char *argv[])
{
	if (argc != 3) {
		fprintf(stderr, "usage: bf filename ts\n"
			"file of filename contains the strings to be added\n"
			"ts means the string to test if it is in the filter vector\n"
			);
		return 1;
	}

	bf_vec_t *vec = calloc(1, sizeof(bf_vec_t));
	if (vec == NULL)
		return 1;
	
	char buf[128] = {0};	
	FILE *fp = fopen(argv[1], "rt");
	if (fp == NULL) {
		free(vec);
		return 1;
	}
	while (fgets(buf, sizeof(buf), fp) != NULL) {
		buf[strlen(buf) - 1] = '\0';
		if (bf_add(vec, buf))
			printf("add to bloom filter successed, string %s\n", buf);
		else
			printf("add to bloom filter FAILED, string %s\n", buf);
	}

	printf("------------------------------------------------------------------\n");
	if (bf_is_contains(vec, argv[2]))
		printf("test string %s is in bloom filter\n", argv[2]);
	else
		printf("test string %s is NOT in bloom filter\n", argv[2]);
	
	free(vec);
	return 0;
}

int main(int argc, char *argv[])
{
	return main2(argc, argv);
}
#endif
在Linux 2.6.39.4 SMP x86_64 gcc version 4.4.3下做了简单测试,效率还是比较可观的。没有做量化的效率测试,也没有对误判率做量化测试。

我在考虑是不是要加一个谓词回调接口,类似于:

typedef int (*bf_contains_cb)(void *data);
int bf_oper_if_contains(bf_vec_t *vec, const char *str, bf_contains_cb callback, void *data);
这样可用性应该会好一些。暂且放下,等到真正要用时,再做详细的量化测试和代码完善吧。

© 著作权归作者所有

共有 人打赏支持
a
粉丝 2
博文 6
码字总数 2777
作品 0
海淀
程序员
布隆过滤器(Bloom Filter)

基本概念 如果想判断一个元素是不是在一个集合里,一般想到的是将所有元素保存起来,然后通过比较确定。链表、树、散列表(又叫哈希表,Hash table)等等数据结构都是这种思路。但是随着集合...

行者PHPer
2014/04/12
0
0
详解布隆过滤器的原理、使用场景和注意事项

今天碰到个业务,他的 Redis 集群有个大 Value 用途是作为布隆过滤器,但沟通的时候被小怼了一下,意思大概是 “布隆过滤器原理都不懂,还要我优化?”。技术菜被人怼认了、怪不得别人,自己...

YoungChen__
08/30
0
0
如何实现大数据集查询?Bloom Filter或许是你想要的

1、什么情况下需要布隆过滤器? 先来看几个比较常见的例子 字处理软件中,需要检查一个英语单词是否拼写正确 在 FBI,一个嫌疑人的名字是否已经在嫌疑名单上 在网络爬虫里,一个网址是否被访...

流川枫AI
2017/06/18
0
0
网络爬虫之url等高效率去重原理

布隆过滤器用于字符串去重复,比如网络爬虫抓取时URL去重、邮件提供商反垃圾黑名单Email地址去重。等等。用哈希表也可以用于元素去重,但是占用空间比较大,而且空间使用率只有50%。   布隆...

小湘西
2015/11/12
0
0
海量数据判重——布隆过滤器(Bloom filter)与Bitmap对比

前言 之前写过一篇Bitmap在海量整数排序中应用的博客,在看过布隆过滤器之后,感觉两个有些相似,但是又有区别,在查阅了很多资料之后,这里决定稍作总结。 关于布隆过滤器(Bloom filter)的...

tick_tock97
2017/12/01
0
0

没有更多内容

加载失败,请刷新页面

加载更多

记一次winserver2003系统,https无法访问,内存占用持续增加,解决办法

先交代一下环境: win server2003系统,系统装在hyper-v虚拟机里 大概2016年底的镜像,距离今天两年左右 病症:大概9月10号左右用这个镜像还可以访问https,但是今天用这个镜像新装的系统,就...

阳阳露
29分钟前
3
0
jdbc连接orcal数据库

import java.sql.Connection;  import java.sql.DriverManager;  import java.sql.ResultSet;  import java.sql.SQLException;  import java.sql.Statement;    ......

小橙子的曼曼
53分钟前
1
0
Vue学习资料

一直以为Vue是依赖nodejs的。 作为前端也可以耦合性就很低了。 //npm包管理器 进行管理npm install vue//初始化一个项目vue init//本地调试npm run dev//编译完成 ...

大灰狼wow
今天
1
0
fullcalendar重新渲染

uiCalendarConfig.calendars.lesson_calendar.fullCalendar('removeEvents');var ym = uiCalendarConfig.calendars.lesson_calendar.fullCalendar('getView').title;$scope.get_lesson(y......

人来疯啊
今天
1
0
多渠道打包总结

https://www.jianshu.com/p/2130db7584c8 https://blog.csdn.net/u011153817/article/details/50772496...

塔塔米
今天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部