快速URL排重的方法

Ralf_Jones 2008-10-31

展开全文

http://blog.csdn.net/oyd/archive/2007/07/19/1699237.aspx
我这里介绍一个极适合大量URL快速排重的方法，这个算法被称为Bloom filter，基本上，它也只适合这样的场合。

这里的大量是指有5000万至1亿的URL，更大的数据量可能也不合适了。

一开始我使用了一个最复杂的做法，是有一个单独的daemon程序负责排重，数据和排重结果通过socket传输。
后来发现不行，仅仅几百万数据要做好几个小时，5000万不把人都急疯了？至于daemon中具体用什么算法就次要了，因为一涉及到网络通讯，速度再快也被拉下来（这里针对的是发送一条记录/返回一条结果的模式，一次传送一批数据则与网络状况有关了）

所以，把目标锁定在单机排重，一开始，试验了perl中的hash，非常简单的代码

use DB_File;

my %db;

#tie %db, ‘DB_File‘, "createdb.dat", or die "Can‘t initialize db:: $! ";

while(<>) {

chomp $_;

$db{$_} = 1;# add code here

}

#untie %db;

从标准输入或文件中每行一个URL读入，插入到perl内置的hash表中，这就成了，需要输出结果则预先判断一下插入的key是否存在。

这个方法速度很快，可惜的是，它占用内存太大，假设1个URL平均50字节，5000万个URL需要2.5G内存。

于是又想到一个方法，把部分数据放入硬盘空间，perl中也提供一个现成的模块DB_File，把上面代码中的注释去掉，就可使用DB_File了，用法与hash一样，只是内部用数据库实现的。

测试了一下，速度明显下降了一个档次，仅40万的数据就要1分钟，关键还在于随着数据量的增加，速度下降加快，两者不呈线性关系。

数据量大的时候，有可能用MySQL的性能会比DB_File好，但是总体上应该是一丘之貉，我已经不抱期望了。

也许DB_File可以优化一下，使用更多的内存和少量的硬盘空间，不过这个方案还是太复杂，留给专家解决吧，一般来说，我认为简单的方法才有可能做到高效。

下面我们的重点对象隆重登场：Bloom filter。简单的说是这样一种方法：在内存中开辟一块区域，对其中所有位置0，然后对数据做10种不同的hash，每个hash值对内存bit数求模，求模得到的数在内存对应的位上置1。置位之前会先判断是否已经置位，每次插入一个URL，只有当全部10个位都已经置1了才认为是重复的。

如果对上面这段话不太理解，可以换个简单的比喻：有10个桶，一个桶只能容纳1个球，每次往这些桶中扔两个球，如果两个桶都已经有球，才认为是重复，问问为了不重复总共能扔多少次球？

10次，是这个答案吧？每次扔1个球的话，也是10次。表面上看一次扔几个球没有区别，事实上一次两个球的情况下，重复概率比一次一个球要低。Bloom filter算法正式借助这一点，仅仅用少量的空间就可以进行大量URL的排重，并且使误判率极低。

有人宣称为每个URL分配两个字节就可以达到0冲突，我比较保守，为每个URL分配了4个字节，对于5000万的数量级，它只占用了100多M的空间，并且排重速度超快，一遍下来不到两分钟，极大得满足了我的欲望。

接上篇，起初我为了输入输出方便，是用perl去实现的，后来发现perl中求模速度太慢，就改用C了

常量定义：SPACE指你要分配多大的内存空间，我这里是为5000万数据的每一条分配4字节

const int SPACE = 50000000 * 4;
const int MAXNUM = SPACE * 8;
#define LINE_MAX 2048
int bits[] = {0x1, 0x2, 0x4, 0x8, 16, 32, 64, 128};
char* db = NULL;

主程序：这里循环读入标准输入的每一行，进行排重。

int main(int argc, char* argv[])
{
        db = new char[SPACE];
        memset(db, 0, SPACE);
        char line[LINE_MAX];
        while (fgets(line, LINE_MAX, stdin) != NULL) {
                int len = strlen(line);
                len--;
                if (len <= 0) continue;
                if (!is_exist(line, len)) {
                        // add code here
                }
        }
        return 0;
}

判定函数：我没有做Bloom filter算法中描述的10次hash，而是做了一个MD5，一个SHA1，然后折合成9次hash。

bool is_exist(const char* str, int len) {
        unsigned int hashs[9];
        unsigned char buf[20];
        MD5(str, len, buf);
        memcpy(hashs, buf, 16);
        SHA1(str, len, buf);
        memcpy(hashs + 4, buf, 20);
        int k = 0;
        for (int j = 0; j < sizeof(hashs) / sizeof(hashs[0]); j++) {
                int bitnum = hashs[j] % MAXNUM;
                int d = bitnum / 8;
                int b = bitnum % 8;
                char byte = db[d];
                if (byte & bits[b] == bits[b]) {
                } else {
                        byte |= bits[b];
                        db[d] = byte;
                        k++;
                }
        }
        return (k == 0);
}

主要算法就在这里了，实际应用的话可以采用循环监视磁盘文件的方法来读入排重数据，那些代码就与操作系统相关，没必要在这写了

Bloom Filter概念和原理

数学之美系列二十一－布隆过滤器（Bloom Filter）