참고한 것들
블룸 필터 (Bloom Filter)
- 블룸 필터는 원소가 집합 내에 존재하는지 확률적으로 알 수 있게 해주는 자료구조이다.
- 여기서 확률적으로 라는 말이 중요한데, 이것은 False-positive 가 존재할 수도 있다는 의미이다.
- 즉, 블룸필터를 돌렸을 때 “존재하지 않음” 으로 결과가 나오면 해당 원소는 반드시 집합 내에 존재하지 않지만,
- “존재함” 으로 결과가 나오면 집합 내에 있을수도 있고 없을 수도 있다는 얘기이다.
- 따라서 블룸 필터는 이름처럼 “필터” 의 용도로 사용하게 된다.
- 검사할 원소의 갯수가 음청나게 많은 경우에, 블룸 필터를 먼저 돌려서 확실하게 존재하지 않는 원소들만 먼저 걸러내고, 나머지에 대해 다른 방법을 이용해 검사하면 되는 것.
아이디어
- 이 블룸 필터를 생각한 사람은 당연히 블룸씨 일거고, 이것은 Space/time trade-offs in hash coding with allowable errors (CACM Mag) 에서 공개되었다.
- 이름에서부터 알 수 있듯이,
원리
그림이 좀 안맞죠?
- 위키피디아 에서 가져온 그림을 수정해서 사용했는데 가운데 “hashes” 부분이 좀 헷갈릴 수 있을것 같아 첨언하자면,
- 저 “hashes” 는 bit array 가 아니라 hash 의 결과고, bit array 는 표현 안돼있습니다.
- 블룸 필터를 hash 함수의 collision 을 아주 똑똑하게 사용한다.
- 원소를 집합에 추가할 때는 hash 함수를 돌려서 그 결과를 어딘가에 저장해 놓고
- 원소를 집합에 존재하는지 검사하고자 할 때도 hash 함수를 돌려서 그의 결과를 저장된 것들과 비교하면 다음과 같은 결과가 나올 수 있다:
- 우선, hash 결과가 저장된 것들 중에 없다면 해당 원소는 집합에 한번도 추가된 적이 없다고 결론내릴 수 있다.
- 한번이라도 추가됐다면 저장된 것들 중에 분명히 있어야 되기 때문.
- 하지만 hash 결과가 저장된 것들 중에 있다면
- 진짜 그 원소가 추가된 적이 있었을 수도 있지만
- 이 부분이 중요하다 - 검사하는 원소와 collision 되는 다른 원소가 추가되었을 수도 있다.
- 우선, hash 결과가 저장된 것들 중에 없다면 해당 원소는 집합에 한번도 추가된 적이 없다고 결론내릴 수 있다.
- 구체적으로는 결과를 bit array 에 저장한다.
- Hash 의 결과가 4bit 라면, 0~15 까지 16개의 값을 가질 수 있으므로 16bit 저장소를 사용하게 되는 것.
- 따라서 “John Smith” 을 hash 한 결과가 2 이라면, 2번째 index 의 bit 에 1을 저장해 원소가 추가되었음을 표시한다.
- 이렇게 하면 bit comparison 으로 결과를 알 수 있어 빠르기 때문.
- False positive 확률을 낮추기 위해 hash function 을 여러개 사용하기도 한다.
- 어떤 값을 여러개의 hash function 에 돌려 나온 결과들에 대한 bit 를 전부 키고
- 확인할 때도 이 hash function 들을 다 돌려 모든 bit 가 켜져있는지 여부로 판단하는 것.