[C++] 블룸 필터(Bloom Filter)

블룸 필터(Bloom Filter)

• 해시 테이블에 비해 공간 효율이 매우 높은 방법
• 결정적(Deterministic) 솔루션 대신 부정확한 결과를 얻을 수 있음.
  • 거짓-부정(Fals Negative) 이 없다는 것은 보장하지만, 거짓-긍정(False Positive) 은 나올 수 있음.
    • 특정 원소가 존재한다는 긍정적인 답변을 받을 경우, 이 원소는 실제로 있을 수도 있고 없을 수도 있음.
    • 그러나 특정 원소가 존재하지 않는다는 부정적인 답변을 받았다면, 이 원소는 확실히 없음.
• 뻐꾸기 해싱과 마찬가지로 블룸 필터도 여러 개의 해시 함수를 사용함.
  • 보통 2개의 해시 함수는 충분한 정확도를 기대하기 어렵기 때문에 3개 이상을 사용해야 함.
• 블룸 필터는 실제 값을 저장하지는 않음.
  • 대신 특정 값이 있는지 없는지 를 나타내는 부울(bool) 타입 배열 을 사용함.
• 원소를 삽입할 경우
  • 모든 해시 함수 값 계산
  • 부울 타입 배열에서 이 해시 값에 대응되는 비트 값을 1로 설정
• 원소를 찾을 경우 (룩업)
  • 모든 해시 함수 값 계산
  • 이에 대응되는 위치의 비트 값이 1로 설정되어 있는지 검사
    • 검사한 모든 비트가 1이면 true 반환
    • 1이 아닌 비트가 하나라도 있다면 false 반환
      • 해당 원소가 없음을 의미함.
• 부울 배열의 모든 원소가 true 또는 1로 설정될 경우, 이 배열은 포화 상태가 됨.
  • 이 상태에서 룩업 함수는 항상 true를 반환함.
• 블룸 필터는 컨테이너에 실제 데이터를 저장하지 않기 떄문 에 다양한 타입의 데이터에 대해서도 사용할 수 있음.
• 해시 함수를 충분히 잘 만들었다면 하나의 블룸 필터에 정수, 문자열, 실수 등의 데이터를 섞어서 삽입할 수도 있음.
• 블룸 필터를 사용하기에 적합한 실제 상황
  • 데이터양이 너무 많아서 해시 테이블조차도 사용하기 버거울 경우
  • 거짓-긍정 이 있어도 괜찮은 경우

 

코드

#include <iostream>
#include <vector>

class bloom_filter {
    std::vector<bool> data;
    int nBits;

    int hash(int num, int key) {
        switch (num) {
            case 0: return key % nBits;
            case 1: return (key / 7) % nBits;
            case 2: return (key / 11) % nBits;
        }
        return 0;
    }

public:
    bloom_filter(int n) : nBits(n) {
        data = std::vector<bool>(nBits, false);
    }

    void lookup(int key) {
        bool result = data[hash(0, key)] & data[hash(1, key)] & data[hash(2, key)];

        if (result) {
            std::cout << key << ": 있을 수 있음." << std::endl;
        }
        else {
            std::cout << key << ": 절대 없음." << std::endl;
        }
    }

    void insert(int key) {
        data[hash(0, key)] = true;
        data[hash(1, key)] = true;
        data[hash(2, key)] = true;
        std::cout << key << "을(를) 삽입: ";

        for (auto a : data) {
            std::cout << a << " ";
        }
        std::cout << std::endl;
    }
};

int main() {
    bloom_filter bf(7);

    bf.insert(100);
    bf.insert(54);
    bf.insert(82);

    bf.lookup(5);
    bf.lookup(50);
    bf.lookup(20);
    bf.lookup(54);

    return 0;
}

 

결과

100을(를) 삽입: 1 0 1 0 0 0 0 
54을(를) 삽입: 1 0 1 0 1 1 0  
82을(를) 삽입: 1 0 1 0 1 1 0  
5: 있을 수 있음.
50: 절대 없음.
20: 절대 없음.
54: 있을 수 있음.