[자료구조] 블룸 필터

<본 카테고리는 "코딩 테스트를 위한 자료 구조와 알고리즘 with C++을 기반으로 작성하였습니다>

---

블룸 필터

개요

　블룸 필터(Bloom filter)는 크기가 m인 비트 배열과 k개의 독립적인 해시 함수로 구성된 확률적 데이터 구조다. 컨테이너다. 초기에 모든 비트가 0으로 설정되어 있으며, 원소를 추가할 때마다 각 해시 함수를 사용하여 계산된 인덱스에 해당하는 비트를 1로 설정하는 방식으로 작동한다. 해시 테이블과 비슷하지만, 공간 효율이 매우 높다.

 

---

특징

　블룸 필터의 가장 큰 특징은 공간 효율성이다. 원소를 직접 저장하지 않고 비트 배열을 사용해 원소의 존재 여부를 추적함으로써 메모리를 효율적으로 사용한다. 그러나, 비트를 이용한 데이터를 처리하는 방식으로 인해 거짓 - 양성이라는 부정확한 결과를 얻을 수 있다. 여기서 거짓 - 양성(false positive)이란 원소가 실제로 필터에 없지만 존재한다고 판단하는 것을 의미한다. 물론, 실제로 필터에 존재하는데 없다고 판단하는 거짓 - 부정(false negative)은 발생하지 않는다.

 

　이러한 특징으로 인해 빠른 조회가 가능하고, 병렬 처리가 가능하다는 장점이 있다. 반대로 블룸 필터가 거짓 - 긍정을 허용하기 때문에 원소를 삭제하는 것이 어렵다. 만약 필터를 변형하여 원소 삭제를 지원하도록 할 경우, 공간 및 성능 효율성이 떨어지기 마련이다. 

 

 

　위 그림은 크기가 7이고, 3개의 독립적인 해시 함수로 구성된 블룸 필터에서 원소 삽입이 어떻게 작동하는지 설명하고 있다. 해당 필터를 기준으로 직접 컨테이너를 구현해 보도록 하겠다.

---

구현

#include <iostream>
#include <vector>

class bloom_filter
{
	std::vector<bool> _filter;
	int _bits;

	int hash(int num, int key)
	{
		switch (num)
		{
			case 0:
				return key % _bits;

			case 1:
				return (key / 7) % _bits;

			case 2:
				return (key / 11) % _bits;
		}

		return 0;
	}

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

　블룸 필터 클래스를 생성하고, 해시 함수를 생성한다.

 

	void insert(int key)
	{
		_filter[hash(0, key)] = true;
		_filter[hash(1, key)] = true;
		_filter[hash(2, key)] = true;

		print();
	}

　원소를 삽입하는 insert() 함수다. 해시 값에 대응하는 비트를 1로 바꿔준다.

 

	void lookUp(int key)
	{
		bool res = _filter[hash(0, key)] && _filter[hash(1, key)] && _filter[hash(2, key)];

		if (res)
			std::cout << "There is a possibility that the " << key << " is in the filter\n";

		else
			std::cout << "The " << key << " is not in the filter\n";
	}

　원소를 찾는 lookUp 함수다. 테이블에서 and 연산을 통해 결과를 출력하면 된다. 

 

	void print()
	{
		for (const auto& val : _filter)
			std::cout << val << ' ';
		std::cout << "\n";
	}
};

　간단하게 테이블에서 비트가 어떤 값을 갖고 있는지 출력하는 print() 함수다.

 

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

 

　100, 54, 82를 차례대로 삽입하고, 5와 50, 20, 54를 찾으면 다음과 같은 결과가 나온다. 여기서 5를 삽입하지 않았음에도 있을 수 있다고 출력하는 이유를 앞선 원소 삽입 과정에서 5에 해당하는 비트들이 이미 1이 되었기 때문이다. 그림으로 보면 다음과 같다.

 

 

총합본

#include <iostream>
#include <vector>

class bloom_filter
{
	std::vector<bool> _filter;
	int _bits;

	int hash(int num, int key)
	{
		switch (num)
		{
			case 0:
				return key % _bits;

			case 1:
				return (key / 7) % _bits;

			case 2:
				return (key / 11) % _bits;
		}

		return 0;
	}

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

	void lookUp(int key)
	{
		bool res = _filter[hash(0, key)] && _filter[hash(1, key)] && _filter[hash(2, key)];

		if (res)
			std::cout << "There is a possibility that the " << key << " is in the filter\n";

		else
			std::cout << "The " << key << " is not in the filter\n";
	}

	void insert(int key)
	{
		_filter[hash(0, key)] = true;
		_filter[hash(1, key)] = true;
		_filter[hash(2, key)] = true;

		print();
	}

	void print()
	{
		for (const auto& val : _filter)
			std::cout << val << ' ';
		std::cout << "\n";
	}
};

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

---

요약

블룸 필터
1. 정의: 비트 배열과 해시 함수로 구성된 확률적 자료구조
2. 특징
　a. 공간 효율성이 높음
　b. 거짓 - 긍정 허용 (거짓 - 부정 X)