블룸 필터
Bloom filter
1. 개념
[image]
(위키백과, 영어 주의)
어떤 값을 여러 해시 함수에 넣어 결과값들을 임의의 테이블에 인덱싱하여 해당되는 모든 값이 1인지를 따지는 자료구조.
해시 함수는 기본적으로 충돌의 가능성이 있기에 블룸 필터에는 긍정 오류[1]의 가능성이 있다. 다만 반대로 부정 오류의 가능성은 없다. 즉, 해당 값이 테이블 내 확률적으로 있거나 절대로 없음을 확인할 수 있다.
해시 함수들을 기본적으로 여러개를 가지는데 임의의 테이블의 크기, 넣어야 하는 자료의 크기, 해시 함수의 수에 따라 오류의 확률이 정해진다.
그래서 요구하는 긍정 오류율이 있다면 넣어야 하는 자료의 크기를 고려해서 테이블의 크기와 해시 함수의 수를 정하는 편이다.
여기 까지 읽었으면 알겠지만 있는지 없는지 만을 보는 그 특성 때문에 삽입만 가능하고 '''제거가 안된다.'''(...) 위의 그림에서 보다시피 여러 값이 똑같은 인덱스에 대응될 수 있기 때문에 어떤 저장된 값을 제거하기 위해 해당 값에 대응되는 인덱스의 요소들을 0으로 만들어버리면 기존에 저장되어있던 다른 값들에 영향을 미치게 되기 때문이다.
2. 구현
사실 알고리즘 자체는 매우 간단하기 때문에 구현에 머리를 싸맬 필요가 없다. 삽입 시엔 그냥 여러개의 해시 함수를 준비하고 들어오는 값에 대해 해시 값을 여러개를 만든 다음, 그 값을 테이블의 인덱스에 대응시켜 1로 바꿔버리면 끝. 값의 확인의 경우에도 마찬가지로 하고 해당 인덱스들에 대응되는 모든 값들이 1인지만 확인하는거로 바꾸면 구현 끝.
3. 활용
자료구조의 특성 때문에 활용 자체에 의문이 들 수 있지만, 알고리즘을 보라. '''얼마나 간단한가.''' 그 간단함때문에 쓰일 수 있다. 즉 매우 빠르다. 오류가 나도 그렇게 문제가 되는 상황이 아니라면 충분히 쓸 수 있다는것. 해시 테이블에 비해 매우 적은 양의 메모리를 사용하기 때문에 굉장히 많은 양의 데이터를 처리해야 해서 기존의 에러가 없는 해시 테이블을 쓰기에는 시간과 메모리적으로 부담될 때 사용할 수 있다.
구체적인 예로는 구글 크롬은 URL이 악의적인 사이트(멀웨어 사이트)의 URL인지를 확인할 때 바로 이 블룸 필터를 사용한다. 또 맞춤법 검사기의 경우 이 블룸 필터가 쓰이기도 한다.
4. 그 외
제거가 안된다는 매우 기묘한 특성 때문에 블룸 필터에 제거 기능을 더한 자료 구조가 만들어 졌다. 다만 블룸 필터라 부르지 않고 카운팅 필터라고 불린다.
테이블의 엔트리들을 1비트 대신 n비트로 설정하고 값을 삽입할 때 해당 인덱스들에 대응하는 값들을 단순히 1로 설정하는 대신 1을 증가시키는 것이다. 삭제할 때는 반대로 1씩 감소시킨다. 즉, 블룸 필터는 카운팅 필터가 n=1일때의 특수한 케이스라고 볼 수 있다.
[1] 쉽게 말해 넣은 적 없는 값에 대해 있다고 하는 경우. 그 반대인 부정 오류는 넣은 적 있는데 없다고 하는 겅우이다.