存档

2011年11月 的存档

Bloom Filter(一),引子:从哈希到布隆过滤器

2011年11月13日 5 条评论

---

布隆过滤器(Bloom Filter)系列博文总览

信息指纹那篇博文我们提到,使用哈希时,利用信息指纹将字符串转为128位整数既可以降低内存需耗,又可以节省查找时间;但是如果要处理的信息量特别大时,哈希表存储效率低的问题就显现出来了,此时就需要考虑其他数据结构了:Bloom Filter。

本篇文章要解决的问题:什么是布隆过滤器?为什么要使用布隆过滤器?

我们经常会遇到要判断一个元素是否在一个集合中这样的问题,例如以下情景:

  • 字处理软件中,需要检查一个英语单词是否拼写正确(也就是要判断它是否在已知的字典中)
  • 网络爬虫里,一个网址是否被访问过等等

最直接的方法就是将集合放入内存,使用哈希的方法,好处是快速、准确;缺点是费空间。请注意,这件事情是在内存中完成的,所以空间问题必须作为考虑因素。当要哈希的集合比较小时,这个问题不显著,但是当集合巨大时,对于有限的内存来说,哈希表存储效率低的问题就显现出来了,这里借数学之美中的案例说明一下bloom Filter的思想及使用它的必要性:

Yahoo,Hotmail 和 Gmai 那样的公众电子邮件(email)提供商,总是需要过滤来自发送垃圾邮件的人(spamer)的垃圾邮件。一个办法就是记录下那些发垃圾邮件的 email 地址,全世界少说也有几十亿个发垃圾邮件的地址。如果用哈希表,每存储一亿个 email 地址, 就需 1.6GB 的内存(十亿字节为1G。用哈希表实现的具体办法是将每一个 email 地址对应成一个八字节的信息指纹,然后将这些信息指纹存入哈希表,由于哈希表的存储效率一般只有 50%,因此一个 email 地址需要占用十六个字节。一亿个地址大约要 1.6GB, 即十六亿字节的内存)。因此存贮几十亿个邮件地址可能需要上百 GB 的内存,一般服务器是无法存储的。

一种称作布隆过滤器的数学工具,它只需要哈希表 1/8 到 1/4 的大小就能解决同样的问题。

布隆过滤器实际上是一个很长的二进制向量一系列随机映射函数

按我的理解:说白了,bloom filter就是将集合元素进行位编码存储

阅读全文...

一个有意思的小程序

2011年11月2日 没有评论

---

昨晚帮一个学弟改了一下他的程序错误,觉得他的程序很有意思,设计到两个容易忽略的错误,在这里分享一下。

由于原题要求比较繁琐,代码也比较多,我就写了一个简单的测试例子来说明一下这两个错误。

想法很好,就是将内存管理封装成类,以用来管理内存的分配和释放,程序如下:

#include <iostream>
using namespace std;
template <class T>
class Alloc // 封装内存管理类
{
public:
    static void allocate(T*&p,int n)
	{
		p=(T*)malloc(sizeof(T)*n);
	}
    static void deallocate(T*p,int n)
    {
        if(n>1)
			delete []p;
        else
			delete p;
		p=NULL;
    }
};

class String
{
private:
    char* ptr;
	size_t strLen;
public:
    String():ptr(NULL),strLen(0){}
    String (const char *s):strLen(strlen(s)),ptr(NULL)
    {
		Alloc<char>::allocate(ptr,strLen+1);
        strcpy(ptr,s);
	}
	~String()
	{
		Alloc<char>::deallocate(ptr,strLen+1);
	}
};

void main()
{
	String("hello");
	printf("%s\n","success!");
}

阅读全文...