Bloom Filter
블룸 필터는 공간을 효율적으로 사용할 수 있는 확률적 데이터 구조로, 어떤 원소가 주어진 집합의 원소로 존재하는지 여부를 테스트하는데 사용된다.
블룸필터에서 False Positive 는 발생할 수 있지만, False Negative 는 발생할 수 없다. 다른말로 하자면, 주어진 쿼리는 “ 아마 집합에 존재할 것 ” 이거나 “ 반드시 집합에 존재하지 않는다 ” 라는 결과만 얻게된다.
B) 알고리즘 설명
빈 블룸 필터는 m 개의 0 값을 가진 bit array 로 시작한다. 반드시 서로 다른 k 개의 해시 함수를 가지고 있어야 하며, 각 해시 함수는 m 개의 array position 중 하나에 매핑되어야 한다.
B.1) 원소 추가
각 k 개의 해시 함수를 통과시켜 k 개의 bit position 을 얻은 뒤에 1 로 설정한다.
B.2) 원소 질의
추가와 동일하게 k 개의 함수를 통과시켜 k 개의 bit position 을 확인하여 값이 모두 1 인지 본다. 만약 하나라도 0 이 있으면 해당 원소는 반드시 집합에 존재하지 않는다. 모두 1 이면 집합에 존재할 수 있다.
C) 예시
집합 {x, y, z} 를 표현한 예시다. 색이 있는 화살표는 각 집합의 원소들이 bit array 내에 매핑된 포지션을 나타낸다. 또한 m=18 이고 k=3 이다.
w 는 집합에 존재하지 않는다. 왜냐하면 해당 값에 해싱 처리를 했을 때 비트 중 한 값이 0 값을 가지기 때문이다.