[c++] 블룸 필터를 이용한 검색

15 Dec 2023

블룸 필터는 확률적 집합 자료구조로, 어떤 요소가 집합에 속해 있는지 여부를 확률적으로 판단할 수 있습니다. 이는 검색을 보다 효율적으로 수행할 수 있도록 도와줍니다.

블룸 필터의 구조

블룸 필터는 보통 비트 배열 또는 비트 벡터로 구현됩니다. 비트 배열의 각 요소는 해시 함수를 통과한 후 특정 위치에 셋팅됩니다. 따라서, 블룸 필터는 입력된 요소가 집합에 있을 가능성을 보여줍니다.

#include <iostream>
#include <vector>
#include <bitset>
#include <functional>

class BloomFilter {
public:
    BloomFilter(int size) : m_bits(size) {}

    void add(const std::string& value) {
        for (auto& hashFunction : m_hashFunctions) {
            size_t index = hashFunction(value) % m_bits.size();
            m_bits.set(index, true);
        }
    }

    bool contains(const std::string& value) const {
        for (auto& hashFunction : m_hashFunctions) {
            size_t index = hashFunction(value) % m_bits.size();
            if (!m_bits.test(index)) {
                return false;
            }
        }
        return true;
    }

private:
    std::vector<std::function<size_t(const std::string&)>> m_hashFunctions = {
        std::hash<std::string>(),
        [](const std::string& value) { return std::hash<std::string>{}(value + "salt"); }
    };
    std::bitset<1000> m_bits;
};

위 코드에서 BloomFilter 클래스의 add 함수는 입력된 문자열을 해시 함수를 통해 해시 값으로 변환한 뒤, 해당 인덱스를 찾아 참 값을 설정합니다. contains 함수는 입력된 문자열이 모든 해시 값을 갖고 있는지를 확인하여, 가능성을 판단합니다.

블룸 필터의 활용

블룸 필터는 대량의 데이터를 다룰 때 중복된 데이터를 신속하게 걸러내는 데에 효과적입니다. 예를 들어, 크롤러가 수집한 URL을 중복 확인할 때 블룸 필터를 사용하면 중복된 URL을 빠르게 걸러내어 처리할 수 있습니다.

불행히도, 블룸 필터는 오검출(거짓 양성)이 발생할 수 있습니다. 즉, 실제로는 존재하지 않는데 존재한다고 판단하는 경우가 발생할 수 있으므로 이러한 확률적 특성을 유의해야 합니다.

결론

블룸 필터는 확률적인 검색을 위한 유용한 자료구조로, 대량의 데이터 중에서 특정 요소가 존재하는지를 빠르게 확인할 수 있는 장점이 있습니다. 그러나 그 확률적 특성으로 인해 오검출이 발생할 수 있음을 유의해야 합니다.

이로써, 블룸 필터를 이용한 검색에 대한 간략한 소개를 마치겠습니다.