bloomfilterの実現

2372 ワード

bloomfilterは、複数のhash関数を利用してkeyを所定の位置にマッピングし、記憶空間を大幅に節約することができる。
検索エンジンの爬虫類は自分があるページに登ったかどうかを判断する時に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; }