Bloom filter(블룸 필터)

블룸 필터는 통계적 특성을 가진 자료구조이다. 
이 블룸 필터는 많은 양의 데이터를 줄여서 공간 효율적으로 빠르게 검색을 할 수 있는 장점이 있다.

우선, 예를 한번 들어서 설명을 하도록 하자. 80번 port에 침입을 시도한 IP중에 1.2.3.4라는 IP가 침입을 시도했느냐를 알고 싶다. 그렇다면, 이 블룸필터를 적용해서 1.2.3.4라는 IP가 침입을 했었는지 안했었는지에 대한 결과를 알아낼 수 있다.
그러면, 블룸필터는 어떻게 어떤식으로 이것을 알아낼까? 우선, 침입을 했었던 IP는 자동으로 블랙리스트 로그에 저장이 된다고 하자. 그렇다면 이 블랙리스트 로그에는 침입을 했었던 IP들이 전부 기록이 되어있을 것이다. 이 블랙리스트 IP 하나하나를 k개의 해싱 함수로 해싱을 한다. 그렇다면, k개의 해싱 값이 나올 테고, 이 해싱값에 해당되는 주소의 비트에 1이라고 표시를 해둔다.
 

이 그림으로 다시 해석을 해보자. 여기서는 3개의 해싱함수를 사용을 하였는데 맨 앞의 비트의 값을 0이라고 하면, w라는 알파벳에 해당되는 해싱값은 4, 13, 16(그림에서는 15로 화살표가 향해 있는데 잘못 그려진듯)이고 x는 1, 5, 13이다. y와 z도 이런식으로 해당되는 해싱값에는 1로 표시가 된다. 

그렇다면, 다시 본론으로 돌아와서 이런식으로 블룸필터가 데이터를 저장하고 있다는 것을 알았으면 이제는 어떻게 검색을 할 것인지에 대해서 보자. 당연히, 검색대상(1.2.3.4라는 IP)을 해싱을 한 후에 해당되는 해싱값들이 나올 것이다. 3개의 해싱 함수로 해싱한 결과로 13, 22, 91로 나왔을때 13, 22, 91번째 비트에 1이라고 모두 표시가 되어있다면 블랙리스트 IP인것이고 13, 22, 91 중에 한 비트라도 1이라고 표시가 되어있지 않다면 블랙리스트 IP가 아니다. 이런식으로 파악을 할 수가 있는 것이다.

실제로, 블룸 필터는 스펠링 체크를 할 때에도 많이 쓰이는 자료구조인데, 사전의 총 용량이 100메가 정도라고 하면 그것의 1/10 정도의 용량인 10메가만큼 메모리에 공간을 만든 후에 사전 안의 모든 단어들을 해싱하여 기록한다. 예를 들어, 내가 Computer라는 단어를 Conputer라고 잘못 오타를 쳤다고 하자. Conputer라는 단어는 블룸 필터 내에서 이러한 단어가 메모리에 있었는지 없었는지를 해싱을 한 후에(해싱값은 82, 121, 160이 나왔다고 하자) 빠른 시간내에 검색을 할 것이고, 당연히 이런 단어는 사전에 없기 때문에 82, 121, 160 모두 1로 표시되어 있지 않을 것이므로 검색 결과 이러한 단어가 없다고 나온다면 그것은 스펠링이 오타가 난 것이라고 판단 할 수 있을 것이다. 

하지만, 바로 위의 예를 조금 더 생각을 해보자. 사전의 단어중에 Window라는 단어의 해싱 값이 82, 160, 200이 나왔다고 하고 Apple이라는 단어의 해싱값이 121, 230, 550이 나왔다고 해보자. 그렇다면 이 해싱값들에 해당하는 비트들엔 당연히 다 1로 기록이 될 것이고 당연히 82, 121, 160 이렇게 3개의 비트에는 모두 1로 표시가 될 것이다. 그렇다면 Conputer라는 단어는 사전에는 없는 단어지만 Conputer를 해싱한 결과인 82, 121, 160이 모두 1로 표시가 되어 있으므로 이 단어는 사전에 있다. 고로 오타가 아니다. 라고 판명을 할 수 있다. 이것이 바로 블룸 필터의 특성인 False Positive(없는데 있다고 하는 것)이다.

하지만 False Negative(있는데 없다고 하는 것)은 블룸 필터에서 발생하지 않는다. Window라는 단어가 82, 160, 200이라는 해싱값으로 블룸 필터 메모리에 저장이 되었다고 하면 당연히 Window라는 단어를 검색하면 똑같이 82, 160, 200이라는 해싱 값이 나올것이고 해당 비트들은 다 1로 표시가 되어있기 때문에 이러한 일은 일어나지 않는다.

블룸 필터의 해싱 함수들은 서로의 해싱 함수들에 대해 Independant 해야 하고, 해싱한 값들은 되도록이면 특정한 값에 치우친게 아닌 아주 고른 분포도를 보여야 한다.  

또한, 블룸 필터는 False Positive라는 오탐을 발생시킬 수 있지만 이 오탐 발생확률을 제어할 수 있다는 것이 특징이다. 위키피디아에 Probability of false positives라는 소제목의 부분에서 짜증나게(?) 생긴 수식들이 바로 오탐 발생확률을 계산할 수 있는 수식이다. 예를 들어, 오탐 발생확률을 1%정도만 되면 만족한다 라고 하면 저 수식의 결과가 0.01 이하로 나온 조건에 따라 블룸 필터를 사용하면 되는 것이다. 이러한 오탐 발생확률을 줄이기 위해선 일반적으로 해싱 함수의 개수를 늘리거나, 저장공간을 늘리는 방법을 채택한다. 1%라는 오탐 발생확률을 기준치로 잡았을 때 해싱 함수의 개수를 늘리면 해싱하는 연산이 많아지기 때문에 시간이 늘어나게 되지만 공간은 이전에 비해 더 적은 공간으로도 사용을 할 수 있다. 반대로 저장공간을 늘리면 공간이 늘어나게 되지만, 해싱함수는 그만큼 덜 써도 상관이 없다. 따라서 이 두 방법은 서로 trade-off한 관계이다.

출처 : http://mindori.egloos.com/1699170