文档章节

一个简单的布隆过滤器

a
 alex_wei
发布于 2013/07/03 02:39
字数 880
阅读 257
收藏 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
Google Guava 中的布隆过滤

在 Guava 项目的11.0版中,一个新的类添加了进来—— BloomFilter(布隆过滤器)类。布隆过滤器是一种独特的数据结构,用以表明元素是否被保存在一个集合(Set)中。有趣的是,布隆过滤器能够...

可观
2013/01/25
6.1K
1
详解布隆过滤器的原理、使用场景和注意事项

今天碰到个业务,他的 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

没有更多内容

加载失败,请刷新页面

加载更多

《阿里铁军》的读书笔记和读后感范文2600字

《阿里铁军》的读书笔记和读后感范文2600字: 在中国互联网,有一个流传很广的说法是,百度强在技术,腾讯强在产品,阿里强在运营。虽然发展到今天,已经不能再用这样简单的视角来看待这三个...

原创小博客
10分钟前
1
0
怎样实际项目中运用责任链模式

1 模式概要 1.1 简介 责任链模式为请求创建一个接收者对象链,每个接收者都包含对另一个接收者的引用,如果一个对象不能处理该请求,那么它会把请求传给下一个接收者,依此类推 责任链模式避...

小刀爱编程
25分钟前
1
0
【宇润日常疯测-004】JS 遍历数组如何快!快!快!

首先,我就是一后端全栈,对前端也只是会用罢了。闲的无聊来测测,不深究,只看表面,不喜勿喷! 遍历数组在写 JS 代码时候一定是经常用的,那么怎么遍历能达到最高效率呢,很多人一定没有测...

宇润
29分钟前
10
1
Linux系统如何定制History输出格式

Linux系统使用History命令来查看系统的运行记录,从而找出一些问题。但是History输出的数据中常常没有时间等信息。本文就来教大家Linux系统如何定制History输出格式。   具体方法如下 以r...

linuxprobe16
31分钟前
1
0
(一) pyhon 基础语法(数值 字符串 元组 列表 字典)

1、python的数据类型: 数值 字符串 列表 元组 字典; 数值类型包括; 整型(int) 长整型(long) 浮点型(float) 复数型 字符串; 可以通过type() 来查看是什么类型的; 注释:len()只支持 字符...

芬野de博客
32分钟前
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部