Bitmap (Encoding)

참고한 것들

• 비크람씨 블로그

정수 집합 인코딩 §

• Bitmap 이라는 이름을 좀 풀어서 말하면, 0 이상 정수의 집합을 bit 에 mapping 해놓은 것 라고 정리할 수 있다.
• 이것은 어떤 0 이상의 정수 $n$ 에 대해 $n\in S$ 이면, $n$ 번째 bit 를 1 로 설정하는 (즉, $bi{t}_n=1$) 방법이다.
  • 프로그래밍 언어로 표현하자면, bitmap |= (1 << n) 정도가 된다.

예시 §

• 예시로 보자. 간단하다.
• 만약 다음과 같은 집합이 있다면,

{1,2,5,9}

• 이 집합을 다음과 같은 하나의 숫자로 표현하는 것이다.

                    0 1 2 3 4 5 6 7 8 9
bitmap (in array): [0,1,1,0,0,1,0,0,0,1]
bitmap (in binary): 1000100110
bitmap (in decimal): 550

장점 §

• 장점은 집합의 union, intersection 과 같은 연산이 bitwise operation 으로 변환되기에 (union 는 OR 로, intersection 은 AND 로) 연산이 개빨라진다는 것이다.
  • 분명 장점이긴 한데, 코딩할 때 집합을 많이 사용하지 않는다면 이 장점이 잘 체감되지 않을 수도 있다.
  • 그래서 search engine 의 예시를 들어볼까 한다.
    • 간단한 search engine 을 만든다고 생각해 보자. 여기에서는 문서를 저장하면, 해당 문서에 ID 를 매기고 여기에 등장하는 모든 단어들을 tokenize 한다.
    • 그리고 이 단어들에 대해, (단어 -> 문서 ID 들의 집합) 으로 매핑을 해 놓으면 어떤 단어가 어떤 문서들에서 등장하는지 빠르게 파악할 수 있겠지?
    • 근데 검색할 때 생각하면 그냥 단어 하나로 검색할 수도 있지만 “고구마” 와 “감자” 가 모두 등장하는 문서를 검색하거나 (즉, AND 연산) “당근” 혹은 “양배추” 가 등장하는 문서 (즉, OR 연산) 를 검색하는 것도 필요하다.
    • 이때 이 “정수 집합 연산” 이 사용된다: (“고구마” 가 등장하는 문서 ID 집합) 과 (“감자” 가 등장하는 문서 ID 집합) 간의 AND, OR 와 같은 연산을 하게 되는 것.