본문 바로가기
Bioinformatics/Algorithms

k-mer로 부터 Bloom Filter (블룸 필터) 생성

by 임은천 2014. 8. 2.

k-mer 전체 갯수 * k-mer 당 bit 크기는 bloom filter의 전체 비트 크기가 된다.


블룸 필터는 셋과 마찬가지로 특정 요소가 존재하는지 여부를 판별하는데 사용할 수 있다. 실제 키를 저장하는 것 대신에 키는 비트의 조합으로 변환된다. 그렇기 때문에 메모리 소비양은 줄어들지만, 실제 존재하지 않는 키가 존재하는 것으로 나타나게 될 수 있다. 이를 줄이기 위해서는 해시 함수의 개수를 늘려야 한다.


이는 반드시 다른 종류의 해시 함수를 많이 가질 필요가 있는 게 아니라, 다른 종류의 씨드값을 동일한 해시 함수에 적용함으로써도 얻을 수 있다.


k-mer를 읽어들이면서, 해시 함수 갯수만큼 해시 값을 계산하고, 개별 해시 값들에 대해서 블룸 필터 안의 비트 벡터 내에서 인덱스를 구하고, 이 인덱스에 들어갈 비트 값을 해시 값에 따라서 정한다. 가령, 이 때의 비트 값은 최소 자료 구조 타입인 char(1 byte)를 고려해서 8개의 마스크 값이 가능하다.


    0x01,  //00000001

    0x02,  //00000010

    0x04,  //00000100

    0x08,  //00001000

    0x10,  //00010000

    0x20,  //00100000

    0x40,  //01000000

    0x80   //10000000


실제로 메모리를 할당할 때, bit* (포인터)에 할 수 있으면 이럴 필요는 없지만, 실제로는 char*(포인터)가 가장 작은 단위이므로 이럴 수 밖에 없는 것이다.


그리고 bloom 필터에서 특정 키가 존재하는 지 확인하려면 마찬가지로, 다른 씨드 값으로 해시를 계산해 가면서, 개별 해시에 해당하는 마스크값의 비트가 블룸 필터의 비트 벡터에 하나라도 존재하지 않으면, 해당 값은 존재하지 않는 것이다.


다만, 이런 개별 비트는 우연히 다른 키 값에 의해서 세팅될 수 있으므로, 좀 더 높은 정확도가 필요하다면, 해시의 개수를 늘려야 한다.

댓글