神马文学网快速URL排重的方法
来源：百度文库 编辑：神马文学网 时间：2024/06/13 06:30:25
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）
我这里介绍一个极适合大量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）