해싱 트릭과 블룸 필터

2017/07/14

해싱 트릭과 블룸 필터에 대해서는 위키에 잘 나와있다.

해싱 트릭을 간단히 다시 설명하면,

1. 피처가 종류가 많을 때 그냥 해시 돌린다. 예 : "나이키" -> "fa456721"
2. 이것을 정한 공간으로 나머지 연산을 한다. 예 : 8로 나누면 모든 피쳐가 8개 중 하나
3. 오리지널 해싱 트릭에서는 나머지 값을 인덱스로 하여 1씩 더해서 쓰거나 한다.

이게 뭐꼬? 오픈마켓에서 파는 상품이 100만개라 쳤을때 8로 나누면 이게 온당한 가?

그래서 블룸 필터가 나왔다.

1. 서로 다른 해싱 알고리즘으로 돌린다.
2. 서로 다른 알고리즘의 해싱이 동시에 들이박을 확률은 거의 없지 않을까?
3. 물론 실제로 쓰자면 나머지 연산으로 퉁치는 과정이 있어서 여전히 들이박을 확률이 있다.

나는 이렇게 쓰고 있다.

1. 블룸 필터 방식을 취하되, 2개 알고리즘으로 16비트씩 하이/로로 잡는다.
2. 합쳐서 32비트 공간을 사용한다.
3. 물론 여전히 피처 수가 많다. 이를 우얄꼬..
4. 희소 행렬 데이터에 있어서 빈 공간을 제거하면 몇 비트로 줄어들까? 그것을 찾아보려고 한다.

[t:/] is not "technology - root". dawnsea, rss