비트 맵 과 부 릉 필터

우선 비트 맵 이 뭔 지, 부 릉 필터 가 뭔 지 이해 해 볼 까요?

비트 맵: 하나의 정수 가 한 무더기 의 정수 에 있 는 지 신속하게 판단 하 는 데 사용 된다

부 릉 필터: 문자열 이 한 무더기 에 있 는 지 판단 하 는 데 사 용 됩 니 다

부 릉 필터 에 대한 상세 한 설명

부 릉 필 터 는 비트 맵 과 해시 표를 결합 시 켰 습 니 다. 먼저 문자열 을 문자열 해시 알고리즘 으로 해시 표 에 비 추 었 습 니 다. 그러나 해시 충돌 로 인해 우 리 는 하나의 문자열 이 여러 개의 서로 다른 문자열 해시 알고리즘 을 사용 하여 전체 해시 표 에 동시에 비 추어 하나의 문자열 이 이 문자열 에 있 는 지 여 부 를 판단 할 수 있 습 니 다.우 리 는 이 문자열 의 위 치 를 계산 할 수 있 습 니 다. 이 문자열 의 매 핑 위치 가 1 일 때 만 존 재 를 표시 합 니 다. 한 위치 가 0 이면 존재 하지 않 는 다 는 것 을 표시 하지만 브 론 필 터 는 존재 하지 않 는 다 고 판단 하 는 것 이 정확 하지 않 습 니 다. 존재 가 정확 하지 않 을 수 있 습 니 다. 하 쉬 충 돌

이 존재 하기 때 문 입 니 다.

부 릉 필터 의 장점: 다른 데이터 구조 에 비해 부 릉 필 터 는 공간 과 시간 적 으로 큰 장점 을 가진다.부 릉 필터 저장 공간 과 삽입 / 조회 시간 은 모두 상수 입 니 다.또한, Hash 함 수 는 서로 관계 가 없 으 며 하드웨어 가 병행 하여 실현 하기에 편리 합 니 다.부 릉 필 터 는 요소 자 체 를 저장 할 필요 가 없 으 며, 보안 에 대한 요구 가 매우 엄격 한 경우 에 유리 하 다.부 릉 필 터 는 전집 을 나 타 낼 수 있 으 며, 다른 어떤 데이터 구조 도 나 타 낼 수 없다.

부 릉 필터 의 단점: 오산 율 이 그 중의 하나 이다.저 장 된 요소 의 수량 이 증가 함 에 따라 오산 율 이 증가한다.그러나 원소 의 수량 이 너무 적 으 면 산열 표를 사용 하면 충분 하 다.또 일반적으로 부 릉 필터 에서 요 소 를 삭제 할 수 없다.우 리 는 비트 배열 을 정수 배열 로 바 꾸 고 하나의 요소 에 해당 하 는 카운터 에 1 을 추가 하면 요 소 를 삭제 할 때 계수 기 를 빼 면 된다 고 생각 하기 쉽다.그러나 안전 한 요 소 를 삭제 하 는 것 은 쉽 지 않다.우선 삭 제 된 요소 가 부 릉 필터 안에 있다 는 것 을 보증 해 야 합 니 다. 이 필터 만 으로 는 보장 할 수 없습니다.또 카운터 가 돌아 가 는 것 도 문제 가 될 수 있다.오 산 률 을 낮 추 는 데 많은 작업 이 있어 부 릉 필터 의 변종 이 생 겼 다.

부 릉 필터 의 응용: A. 영어 단어 가 맞 춤 법 이 정확 한 지 확인 해 야 합 니 다. B. 용의자 의 이름 이 혐의 명단 에 있 는 C. 인터넷 파충류, 한 사이트 가 방문 되 었 는 지 등

1. 비트 맵 구현
. h 파일

#pragma once
#include

typedef uint64_t BitmapType;
#define BitmapMaxSize 1000
typedef struct Bitmap
{
    uint64_t* data;
    uint64_t capacity;//          
}Bitmap;
//   
void BitmapInit(Bitmap* bm,uint64_t capacity);
//  
void BitmapDestroy(Bitmap* bm);
//       1
void BitmapSet(Bitmap* bm,uint64_t index);
//       0
void BitmapUnset(Bitmap* bm,uint64_t index);
//       1
void BitmapFill(Bitmap* bm);
//       0
void BitmapClear(Bitmap* bm);
//        1
int BitmapTest(Bitmap* bm,uint64_t index);

(1) 비트 맵 의 한 사람 이 1 인지 확인 합 니 다.

int BitmapTest(Bitmap* bm,uint64_t index)
{
    if(bm == NULL || index >= bm->capacity)
    {
        //    
        return 0;
    }
    uint64_t n,offset;
    GetOffset(index,&n,&offset);
    uint64_t ret = bm->data[n] & (0x1ul << offset);
    return ret > 0 ? 1 : 0;
}

(2) 비트 맵 의 모든 비트 를 0 으로 설정

void BitmapClear(Bitmap* bm)
{
    if(bm == NULL)
    {
        return;
    }
    uint64_t size = Getsize(bm->capacity);
    memset(bm->data,0x0,(sizeof(BitmapType)*size));
    return;
}

(3) 비트 맵 초기 화

uint64_t Getsize(uint64_t capacity)
{
    uint64_t size = capacity / (sizeof(BitmapType)*8)+1;
    return size;
}
void BitmapInit(Bitmap* bm,uint64_t capacity)
{
    if(bm == NULL)
    {
        return;
    }
    //capacity             
    //   capacity = 100，2   
    //   capacity = 200，4   
    //   capacity = 300，5   
    //   capacity = N，N/（sizeof(uint64_t) * 8）+ 1
    bm->capacity = capacity;
    //size                  
    uint64_t size = Getsize(capacity);
    bm->data = (BitmapType*)malloc(sizeof(BitmapType)*size);
    memset(bm->data,0,sizeof(BitmapType)*size);
    return;
}

(4) 비트 맵 삭제

void BitmapDestroy(Bitmap* bm)
{
    if(bm == NULL)
    {
        return;
    }
    bm->capacity = 0;
    free(bm->data);
    return;
}

(5) 비트 맵 의 한 분 을 1 로 설정 합 니 다.

void GetOffset(uint64_t index,uint64_t* n,uint64_t* offset)
{
    *n = index / (sizeof(BitmapType)*8);
    *offset = index % (sizeof(BitmapType)*8);
    return;
}
void BitmapSet(Bitmap* bm,uint64_t index)
{
    if(bm == NULL || index >= bm->capacity)
    {
        return;
    }
    uint64_t n,offset;
    GetOffset(index,&n,&offset);
    bm->data[n] |= (0x1ul << offset);
    return;
}
void TestSet()
{
    TEST_HEADER;
    Bitmap bm;
    BitmapInit(&bm,100);
    BitmapSet(&bm,50);
    int ret = BitmapTest(&bm,50);
    printf("ret expected 1,actual %d
",ret);
    ret = BitmapTest(&bm,20);
    printf("ret expected 0,actual %d
",ret);
}

(6) 비트 맵 의 한 분 을 0 으로 설정 합 니 다.

void BitmapUnset(Bitmap* bm,uint64_t index)
{
    if(bm == NULL || index >= bm->capacity)
    {
        return;
    }
    uint64_t n,offset;
    GetOffset(index,&n,&offset);
    bm->data[n] &= ~(0x1ul << offset);
    return;
}
void TestUnset()
{
    TEST_HEADER;
    Bitmap bm;
    BitmapInit(&bm,100);
    BitmapSet(&bm,50);
    int ret = BitmapTest(&bm,50);
    printf("ret expected 1,actual %d
",ret);
    BitmapUnset(&bm,50);
    ret = BitmapTest(&bm,50);
    printf("ret expected 0,actual %d
",ret);
}

(7) 비트 맵 의 모든 비트 를 1 로 설정

void TestFill()
{
    TEST_HEADER;
    Bitmap bm;
    BitmapInit(&bm,100);
    BitmapFill(&bm);
    int ret = BitmapTest(&bm,50);
    printf("ret expected 1,actual %d
",ret);
    ret = BitmapTest(&bm,0);
    printf("ret expected 1,actual %d
",ret);
    ret = BitmapTest(&bm,99);
    printf("ret expected 1,actual %d
",ret);
}
void BitmapFill(Bitmap* bm)
{
    if(bm == NULL)
    {
        return;
    }
    uint64_t size = Getsize(bm->capacity);
    memset(bm->data,0xff,(sizeof(BitmapType)*size));
    return;
}

2. 부 릉 필터 구현
. h 파일

#pragma once
#include"bitmap.h"
//               ，        
typedef uint64_t (*BloomHash)(const char*);
#define BloomHashCount 2

typedef struct BloomFilter
{
    Bitmap bm;
    BloomHash bloom_hash[BloomHashCount];
}BloomFilter;

void BloomFilterInit(BloomFilter* bf);

void BloomFilterDestroy(BloomFilter* bf);

void BloomFilterInsert(BloomFilter* bf,const char* str);

int BloomFilterIsExist(BloomFilter* bf,const char* str);

（1）hash_func.c

#include 
#include

size_t BKDRHash(const char* str)
{
    size_t hash = 0;
    size_t ch = 0;
    while(ch = (size_t)*str++)
    {
        hash = hash * 131 +ch;
    }
    return hash;
}

size_t SDBMHash(const char* str)
{
    size_t hash = 0;
    size_t ch = 0;
    while(ch = (size_t)*str++)
    {
        hash = hash * 65599 +ch;
    }
    return hash;
}

(2) 부 릉 필터 초기 화

void BloomFilterInit(BloomFilter* bf)
{
    if(bf == NULL)
    {
        return;
    }
    BitmapInit(&bf->bm,10000);
    bf->bloom_hash[0] = SDBMHash;
    bf->bloom_hash[1] = BKDRHash;
    return;
}

(3) 부 릉 필터 소각

void BloomFilterDestroy(BloomFilter* bf)
{
    if(bf == NULL)
    {
        return;
    }
    bf->bloom_hash[0] = NULL;
    bf->bloom_hash[1] = NULL;
    BitmapDestroy(&bf->bm);
    return;
}

(4) 부 릉 필터 에 문자열 삽입

void BloomFilterInsert(BloomFilter* bf,const char* str)
{
    if(bf == NULL || str == NULL)
    {
        //    
        return;
    }
    size_t i = 0;
    for(;i < BloomHashCount;++i)
    {
        uint64_t hash = bf->bloom_hash[i](str) % BitmapMaxSize;
        BitmapSet(&bf->bm,hash);
    }
    return;
}

(5) 부 릉 필터 에 문자열 이 있 는 지 확인 하기

int BloomFilterIsExist(BloomFilter* bf,const char* str)
{
    if(bf == NULL || str == NULL)
    {
        //    
        return 0;
    }
    size_t i = 0;
    for(;i < BloomHashCount;++i)
    {
        uint64_t hash = bf->bloom_hash[i](str) % BitmapMaxSize;
        int ret = BitmapTest(&bf->bm,hash);
        if(ret == 0)
        {
            return 0;
        }
    }
    return 1;
}

(6) 전체 테스트 함수

void TestBloom()
{
    TEST_HEADER;
    BloomFilter bf;
    BloomFilterInit(&bf);
    BloomFilterInsert(&bf,"nihao");
    BloomFilterInsert(&bf,"haha");
    int ret = BloomFilterIsExist(&bf,"nihao");
    printf("ret expected 1,actual %d
",ret);
    ret = BloomFilterIsExist(&bf,"hehe");
    printf("ret expected 0,actual %d
",ret);
}

위 에 있 는 이 부 릉 알고리즘 은 공간 을 절약 하지만 삭제 알고리즘 을 지원 하지 않 습 니 다. 위 에 있 는 알고리즘 은 한 위치 에 몇 개의 수 를 매 핑 했 을 수 있 기 때문에 한 개의 수 를 삭제 하면 다른 수 에 영향 을 줄 수 있 습 니 다.
만약 에 우리 가 삭제 알고리즘 을 사용 하려 면 인용 계수 방법 을 사용 할 수 있 습 니 다. 그러면 하나의 수 를 저장 하 는 위 치 는 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트