分享

更多

   

快速URL排重的方法

2008-10-31  Ralf_Jones
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[] = {0x10x20x40x8163264128};
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 <= 0continue;
                
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);
}

 

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

    本站是提供个人知识管理的网络存储空间,所有内容均由用户发布,不代表本站观点。如发现有害或侵权内容,请点击这里 或 拨打24小时举报电话:4000070609 与我们联系。

    猜你喜欢

    0条评论

    发表

    类似文章
    喜欢该文的人也喜欢 更多