비트 맵 & 부 릉 필터

비트 맵 정의:
  비트 의 상 태 를 이용 하여 하나의 숫자 가 존재 하 는 지 여 부 를 저장 합 니 다. 사실은 하나의 수 를 간단 한 숫자 로 매 핑 하여 그 가 존재 하 는 지 여 부 를 표시 하 는 것 입 니 다. 일반적인 사용 상황 은 하나의 숫자 가 존재 하 는 지 여 부 를 찾 는 것 입 니 다.
데이터 구조:
  
1/8=0    1%8=1   1 < 1 (두 번 째 bit 위치 1)
2/8=0    2%8=2   1 < 2 (세 번 째 bit 위치 1)
3/8=0    3%8=3  1 < 3 (네 번 째 bit 위치 1)
4/8=0    ....
이 숫자 가 존재 하 는 지 찾 습 니 다:
  먼저 이 수의 존재 위 치 를 계산 한 다음 에 이 위치 가 1 인지, 만약 존재 한다 면 존재 하지 않 는 다.
단점: 가 독성 이 떨어진다.
적용:  1. 40 억 개의 중복 되 지 않 는 unsigned int 의 정 수 를 주 고 순 서 를 정 하지 않 은 다음 에 하나의 수 를 주 었 습 니 다. 이 숫자 가 그 40 억 개의 수 에서 이 40 억 개의 숫자 를 bitmap 에 저장 하 는 지 여 부 를 어떻게 신속하게 판단 한 다음 에 제 시 된 숫자 에 대해 bitmap 에 있 는 지 판단 하면 됩 니 다.2. 비트 맵 법 으로 성형 배열 의 중복 여 부 를 판단 한다.      배열 을 옮 겨 다 니 며 하나씩 bitmap 에 넣 고 bitmap 에 있 었 는 지 확인 합 니 다. 넣 지 않 았 다 면 중복 되 는 요소 입 니 다.       3. 비트 맵 으로 성형 배열 정렬      먼저 배열 을 옮 겨 다 니 며 배열 의 최대 최소 값 을 얻 은 다음 이 최대 최소 값 에 따라 bitmap 의 범 위 를 축소 합 니 다.여기 서 int 의 음수 에 대해 모두 unsigned int 로 전환 하여 처리 해 야 하 며, 위 치 를 취 할 때 숫자 는 최소 값 을 빼 야 합 니 다.

#define  _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;
#include<vector>
class BitMap
{
public:
BitMap(size_t size)
{
_bm.resize(size / 32 + 1);
_size = 0;
}
BitMap()
:_size(0)
{}
void Set(size_t num)
{
size_t index = num >> 5;
if ((_bm[index] & 1 << (num % 32)) == 0)
{
_bm[index] |= 1 << (num % 32);
++_size;
}
}
void Reset(size_t num)
{
size_t index = num >> 5;
if ((_bm[index] & (1 << (num % 32))) == 1 << (num % 32))
{
_bm[index] &= ~(1 << (num % 32));
--_size;
}
}
bool Test(size_t num)
{
size_t index = num >> 5;
if ((_bm[index] & (1 << (num % 32))) == 1 << (num % 32))
{
return true;
}
return false;
}
size_t Size()
{
return _size;
}
private:
vector<unsigned int> _bm;
size_t _size;
};
//
//void test()
//{
//BitMap x(100);
//x.Set(0);
//x.Set(1);
//x.Set(2);
//x.Set(3);
//x.Set(4);
//x.Set(5);
//x.Reset(1);
//x.Reset(3);
//int ret=x.Test(4);
//
//
//}
//int main()
//{
//test();
//system("pause");
//return 0;
//}

위의 비트 맵 을 이용 하여 부 릉 필 터 를 실현 합 니 다.
모방 함수:
   한 종류의 사용 을 함수 처럼 보이 게 하 는 것 이다.그 실현 은 바로 클래스 에서 하나의 operator () 를 실현 하 는 것 이다. 이런 유형 은 유사 한 함수 의 행 위 를 하 는데 바로 모방 함수 류 이다.
부 릉 필터:
  블 룸 필터 (Bloom Filter) 는 1970 년 블 룸 필터 가 제안 했다.그것 은 실제로 매우 긴 바 이 너 리 벡터 와 일련의 랜 덤 맵 함수 이다.부 릉 필 터 는 하나의 요소 가 집합 에 있 는 지 검색 하 는 데 사용 할 수 있다.그것 의 장점 은 공간 효율 과 조회 시간 이 일반적인 알고리즘 을 훨씬 초과 한 다 는 것 이다. 단점 은 일정한 오 식 률 과 삭제 어려움 이 있다 는 것 이다.
응용 필드:
     워드 프로세서 에 서 는 영어 단어 가 맞 춤 법 이 정확 한 지 확인 해 야 합 니 다 (즉, 이미 알 고 있 는 사전 에 있 는 지 판단 하 는 것 입 니 다).FBI 에서 용의자 의 이름 이 이미 용의자 명단 에 있 는 지 여부;인터넷 파충류 에 서 는 인터넷 주소 가 방 문 된 적 이 있 는 지 등 이 있다.가장 직접적인 방법 은 집합 중의 모든 요 소 를 컴퓨터 에 존재 시 키 고 새로운 요 소 를 만 났 을 때 그것 을 집합 중의 요소 와 직접 비교 하면 된다.일반적으로 컴퓨터 의 집합 은 해시 표 (hash table) 로 저장 된다.그것 의 장점 은 빠 르 고 정확 하 며, 단점 은 비용 저장 공간 이다.집합 이 비교적 시간 이 걸 렸 을 때 이 문 제 는 현저 하지 않 았 지만 집합 이 커 졌 을 때 하 쉬 표 의 저장 효율 이 낮은 문제 가 나 타 났 다. 
장점:
           부 릉 필터 저장 공간 과 삽입 / 조회 시간 은 모두 상수 입 니 다.또한, Hash 함 수 는 서로 관계 가 없 으 며 하드웨어 가 병행 하여 실현 하기에 편리 합 니 다.부 릉 필 터 는 요소 자 체 를 저장 할 필요 가 없 으 며, 보안 에 대한 요구 가 매우 엄격 한 경우 에 유리 하 다.
단점:
     오산 율.저 장 된 요소 의 수량 이 증가 함 에 따라 오산 율 이 증가한다.
 

#define  _CRT_SECURE_NO_WARNINGS
#include"Map.h"
#include<string>

size_t _GetSize(const size_t size)  //             
{
const int _PrimeSize = 28;
static const unsigned long _PrimeList[_PrimeSize] =
{
53ul, 97ul, 193ul, 389ul, 769ul,
1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
1610612741ul, 3221225473ul, 4294967291ul
};
size_t i = 0;
for (; i < _PrimeSize; i++)
{
if (_PrimeList[i] <= size && i != _PrimeSize - 1)
{
i++;
}
else
{
break;
}
}
return _PrimeList[i];
}


template<class T>
struct __HashFunc1
{
size_t BKDRHash(const char* str)
{
register size_t hash = 0;
while (size_t ch = (size_t)*str++)
{
hash = hash * 131 + ch;    
}
return hash;
}

size_t operator()(const T& str)
{
return BKDRHash(str.c_str());
}
};


template<class T>
struct __HashFunc2
{
size_t SDBMHash(const char* str)
{
register size_t hash = 0;
while (size_t ch = (size_t)*str++)
{
hash = 65599 * hash + ch;
//hash = (size_t)ch + (hash << 6) + (hash << 16) - hash;  
}
return hash;
}


size_t operator()(const T& str)
{
return SDBMHash(str.c_str());
}
};


template<class T>
struct __HashFunc3
{
size_t RSHash(const char *str)
{
register size_t hash = 0;
size_t magic = 63689;
while (size_t ch = (size_t)*str++)
{
hash = hash * magic + ch;
magic *= 378551;
}
return hash;
}


size_t operator()(const T& str)
{
return RSHash(str.c_str());
}
};


template<class T>
struct __HashFunc4
{
size_t APHash(const char *str)
{
register size_t hash = 0;
size_t ch;
for (long i = 0; ch = (size_t)*str++; i++)
{
if ((i & 1) == 0)
{
hash ^= ((hash << 7) ^ ch ^ (hash >> 3));
}
else
{
hash ^= (~((hash << 11) ^ ch ^ (hash >> 5)));
}
}
return hash;
}


size_t operator()(const T& str)
{
return APHash(str.c_str());
}
};


template<class T>
struct __HashFunc5
{
size_t JSHash(const char *str)
{
register size_t hash = 1315423911;
while (size_t ch = (size_t)*str++)
{
hash ^= ((hash << 5) + ch + (hash >> 2));
}
return hash;
}


size_t operator()(const T& str)
{
return JSHash(str.c_str());
}
};


template <class K=string,
class HashFunc1 = __HashFunc1<K>,
class HashFunc2 = __HashFunc2<K>,
class HashFunc3 = __HashFunc3<K>,
class HashFunc4 = __HashFunc4<K>,
class HashFunc5 = __HashFunc5<K>
>
class BloomFilter
{
public:
BloomFilter(size_t size = 0)
:_bitmap(size),
_capacity(size)
{}
void Set(const K& key)
{
size_t index1 = HashFunc1()(key);
size_t index2 = HashFunc2()(key);
size_t index3 = HashFunc3()(key);
size_t index4 = HashFunc4()(key);
size_t index5 = HashFunc5()(key);
_bitmap.Set(index1%_capacity);
_bitmap.Set(index2%_capacity);
_bitmap.Set(index3%_capacity);
_bitmap.Set(index4%_capacity);
_bitmap.Set(index5%_capacity);
}
bool Test(const K& key)
{
size_t index1 = HashFunc1()(key);
if (!(_bitmap.Test(index1%_capacity)))
return false;
size_t index2 = HashFunc2()(key);
if (!(_bitmap.Test(index2%_capacity)))
return false;
size_t index3 = HashFunc3()(key);
if (!(_bitmap.Test(index3%_capacity)))
return false;
size_t index4 = HashFunc4()(key);
if (!(_bitmap.Test(index4%_capacity)))
return false;
size_t index5 = HashFunc4()(key);
if (!(_bitmap.Test(index5%_capacity)))
return false;
return true;
}
private:
BitMap _bitmap;
size_t _capacity;
};
void test()
{
BloomFilter<> bf(50);
bf.Set("aaa");
bf.Set("bbb");
bf.Set("ccc");
int ret = bf.Test("acc");
ret = bf.Test("bbb");
ret = bf.Test("aaa");
ret = bf.Test("aaa");
}
int main()
{
test();
system("pause");
return 0;
}

본문 은 "fun" 블 로그 에서 나 왔 으 니, 반드시 이 출처 를 보존 하 시기 바 랍 니 다.http://10725723.blog.51cto.com/10715723/1773401