bloomfilterの実現
2372 ワード
bloomfilterは、複数のhash関数を利用してkeyを所定の位置にマッピングし、記憶空間を大幅に節約することができる。
検索エンジンの爬虫類は自分があるページに登ったかどうかを判断する時にbloomfilterで判断します。
具体的な紹介はこのブログを見てもいいです。http://www.cnblogs.com/heaad/archive/2011/01/02/1924195.html
次は私の実現です。
検索エンジンの爬虫類は自分があるページに登ったかどうかを判断する時にbloomfilterで判断します。
具体的な紹介はこのブログを見てもいいです。http://www.cnblogs.com/heaad/archive/2011/01/02/1924195.html
次は私の実現です。
#include "stdafx.h"
#include<cmath>
#include<iostream>
using namespace std;
class bloomfilter
{
private:
unsigned int m;//bit
unsigned int k;// hash
double f;// False Positive
unsigned int n;//key
char*bitmap;
private:
int hash1(char*str);
int hash2(char*str);
int getbit(const int nn);
void setbit(const int nn);
public:
bloomfilter(const int N);
bool find(char*str);
~bloomfilter();
};
bloomfilter::bloomfilter(const int N)
{
n = N;
f = 0.00001;
// false positive hash k = -ln(f) / ln(2)
//k = -log(f) / log(2.0);
// f、n、m、k ,
//n = m ln(0.6185) / ln(f)
//m = (n + 1)*log(f) / log(0.6185);//m bit , char 8 bit
k = 2;
m = 1000000;
bitmap = new char[m/8+1];
memset(bitmap, 0, (m / 8 + 1)*sizeof(char));
}
bloomfilter::~bloomfilter()
{
delete[]bitmap;
}
bool bloomfilter::find(char*str)
{
int l1 = hash1(str);
int flag = 0;
if (getbit(l1))
flag++;
else
setbit(l1);
int l2 = hash2(str);
if (getbit(l2))
flag++;
else
setbit(l2);
return flag == 2;
}
//
int bloomfilter::getbit(const int nn)
{
int nnn = nn >> 3;
int lessthan8 = nn % 8;
return (bitmap[nnn]>>lessthan8)%2==1;
}
//
void bloomfilter::setbit(const int nn)
{
int nnn = nn >>3;
int lessthan8 = nn % 8;
bitmap[nnn]+=(1 << lessthan8);
}
// hash
int bloomfilter::hash1(char*str)
{
unsigned int h=0;
char *p;
for (p = str; *p!='
'; p++)
{
h = 31 * h + *p;
}
return h%m;
}
int bloomfilter::hash2(char*str)
{
unsigned int hash = 0;
unsigned int i = 0;
int len = strlen(str);
for (i = 0; i < len; str++, i++) {
hash = (*str) + (hash << 6) + (hash << 16) - hash;
}
return hash%m;
}
int _tmain(int argc, _TCHAR* argv[])
{
//cout << log(0.00001) << endl;
//char a = 20;
//a += 1 << 5;
//cout << ((a >> 4)%2==1) << endl;
bloomfilter bf(1000);
cout<<bf.find("www.google.com");
cout<<bf.find("www.baidu.com");
cout<<bf.find("www.google.com");
system("pause");
return 0;
}