[자료구조] 블룸 필터(bloom filter)

블룸 필터(bloom filter)

블룸 필터는 해시 테이블에 비해 공간 효율이 매우 높은 방법이지만, 결정적(deterministic) 솔루션 대신 부정확한 결과를 얻을 수 있다.

• 거짓-부정(false-negative)dl 이 없다는 것은 보장하지만, 거짓-긍정(false-positive)는 나올 수 있다.
  • 즉, 특정 원소가 존재한다는 긍정적인 답변을 받을 경우, 이 원소는 실제로 있을 수도 있고 없을 수도 있다.
  • 그러나 특정 원소가 존재하지 않는다는 부정적인 답변을 받았다면 이 원소는 확실히 없다
• 뻐꾸기 해싱과 마찬가지로 블룸 필터도 여러 개의 해시 함수를 사용한다
  • 정확도를 위해 세 개 이상을 사용해야 한다
• 블룸 필터는 실제 값을 저장하지는 않으며, 대신 특정 값이 있는지 없는지를 나타내는 부울 타입 배열을 사용한다
• 원소를 삽입할 경우, 모든 해시 함수 값을 계산하고 부울 타입 배열에서 이 해시 값에 대응되는 위치의 비트 값을 1로 설정한다
• 룩업의 경우, 모든 해시 함수 값을 계산하고 이에 대응되는 위치의 비트 값이 1로 설정되어 있는지를 검사한다
  • 만약 검사한 모든 비트가 1이면 true를 반환한다
  • 1이 아닌 비트가 하나라도 있으면 false를 반환하고, 이는 해당 원소가 없음을 의미한다

블룸 필터가 결정적이지 않은 이유

• 특정 비트가 다수 원소에 의해 1로 설정될 수 있기 때문이다.
  • 특정 값 x와 연관된 모든 비트가 이전에 삽입된 다른 원소 값들에 의해 모두 1로 설정되어 있을 가능성이 있다는 뜻이다
    • 이러한 경우 x에 대한 룩업 함수는 true를 반환할 것이다
    • 이처럼 특정 원소가 있다고 잘못 판단하는 것을 거짓-긍정이라고 한다
    • 원소의 개수가 많아질수록 거짓-긍정이 발생할 가능성은 증가한다
    • 그러나 x와 연관된 비트 중 하나라도 1로 설정되어 있지 않다면 x가 확실하게 없다고 말할 수 있다.
      • 그러므로 거짓-부정은 발생할 수 없다
• 부울 배열의 모든 원소가 true 또는 1로 설정될 경우, 이 배열은 포화 상태가 된다
  • 이 상태에서 룩업 함수는 항상 true를 반환하고 삽입함수는 블룸 필터 상태에 아무런 영향을 주지 못한다

Example) 블룸 필터 만들기

#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;
    }
};

using namespace std;

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;
}

• 해시 함수의 인자 num은 내부에서 어떤 해시 함수를 사용할 지 결정하는 역할을 한다
  • 이렇게 함으로써 여러 개의 해시 함수를 따로 만들지 않아도 된다
• lookup() 함수는 필요한 모든 비트가 1로 설정되어 있는지를 검사한다
• 위 예제를 보면, 이 프로그램에서 필요한 정보를 저장하기 위해 겨우 7비트만 사용했다.
  • 필터 크기를 좀 더 크게 설정하고 해시 함수를 보완하면 훨씬 더 나은 성능을 얻을 수 있다
• 블룸 필터는 컨테이너에 실제 데이터를 저장하지 않기 때문에 다양한 타입의 데이터에 대해서도 저장할 수 있다
  • 해시 함수를 잘 만들었다면 하나의 블룸 필터에 정수, 문자열, 상수 등의 데이터를 섞어서 삽입할 수도 있다
• 블룸 필터를 사용하기에 적합한 실제 상황
  • 데이터 양이 너무 많아서 해시 테이블조차도 사용하기 버겁고, 거짓-양성이 있어도 괜찮은 경우
  • ex) 새로운 이메일 주소 생성 시 중복 검사를 하는 경우
    • 기본적인 중복 검사도 매우 빈번하게 수행해야 한다
    • 사용하고 있지 않은 이메일 주소를 사용중이라고 해도 큰 문제는 없다
  • ex) 새로운 추천 광고 선택 알고리즘