색인 압축 기법 정리 : Byte Align and Gamma Compression

색인 압축에는 두가지 영역이 있는데 첫번째 영역은 Term Dictionary의 영역과, 두번째 영역은 posting 영역의 압축이 있다.

Term Dic의 압축은 일단 다루지는 않겠고, (이 부분의 압축 기법은 Lucene 색인 파일 구조에 잘 나타나 있다. 예를 들어 prefix를 공유하는 기법이라든지 말이다.)

posting list영역의 압축 기법은 대표적으로 연속된 doc id를 기준으로 d-gap을 이용하는데, 이 d-gap을 어떤식으로 저장을 하는것이 효율적인가를 다루는 영역이다.

예를들어, d-gap No.가 0 <= d-gap < 64 라면 1바이트만이 필요하겠고, 일반적인 Int값을 영역으로삼는다면 4바이트의 영역을 Fix해서 사용할 것이다. (하지만 실제 세계에는 그런 정해진 범위를 주어질 정도로 친절하지 않다.)

그리고 d-gap의 분포는 그렇게 크지 않은게 일반적이여서 그 영역은 모르지만 작은 숫자들를 4바이트나 그 이상의 크기로 fix해서 잡아버린다면 그에 해당하는 Disk의 영역은 굉장히 낭비가 심할 것이다.

아래와 같이 말이다. ^^;

Value Uncompressed Bit String
1    00000000 00000000 00000000 00000001
3    00000000 00000000 00000000 00000011
4    00000000 00000000 00000000 00000100
63    00000000 00000000 00000000 00111111
180 00000000 00000000 00000000 10110100

그리고 또한 맘대로 비트단위로 자신이 필요한 크기만 Disk에 할당해 버린다면, 각자 크기가 다른 d-gap의 경계를 알지 못하는 경우가 필시 생길 것이다.

그래서 d-gap의 압축이라함은 그 값 안에 데이터의 필요 비트수를 prefix에 저장하는경우가 일반적이고 그 뒤에 실제 값을 저장을 한다. (단순히 이렇게 이야기 했지만 좀 복잡한 문제다.)

대표적인 방법으로 Byte Aligned 방법과 Variable length encoding 방법이 있다.

Byte Aligned 방법은 Fixed Length Index Compression 방법이라고도 하며, 제일 앞에 정해진 몇몇 비트를 길이정보를 포함하는 것으로 활용하는 방법으로 직관적이고 구현하기 쉬운 장점이 있다. (약 15%의 압축 효율이있다고 알려져 있다.)

Variable lengrh encoding 방법은 d-gap 자체가 작은 수들의 연속이라고 가정하고, Huffman encoding방법을 응용해서 만든 압축 방법이다.

Byte Aligned 방법에 대해서 더 자세히 설명하자면..

우리가 압축하고자 하는 d-gap이 “1,2,4,63,180” 이라고 하고, 처음 두 비트를 길이정보를 저장하는 비트라고 지정을 하면 , 아래와 같은 비트 배열이 나올것이다.

value    compressed Bit String
1    00 000001
2    00 000010
4    00 000100
63    00 111111
180 01 000000 10110100

앞의 2비트로 0~3 까지의 표현이 가능하므로 4바이트 길이정보를 저장할 수 있다.(실제로 2비트 정보를 빼야 해서 2^30 – 1까지의 숫자를 표현할 수 있다.)

만일 d-gap의 크기가 2^30이 넘는다면 3비트로 길이정보를 표현하면 될 것이다.
그래서 위에서 Fixed Length 방법이라 칭한것이다.

Variable length encoding방법은 길이의 제한이 없는 방법인데, 이 방법과 ,Lucene에서 쓰는 VInt방법을 혼동했는데 약간 다른 방법임을 알았다.

이 방법은 unary로 표현된 비트와 stop bit(0)그리고 그 다음에 실제적인 값이 들어가는 방식이다.

Unary는 숫자 1로 표현한 그 해당 값을 의미한다. 예를들어 10진수 5를 표현하면 11111 이 되는 것이다.

예를들어 10진수 14를 압축해 보면,

Unary값은 이 숫자를 넘지않는 2진수의 값의 숫자배열이므로 “logX = 3 < 14″로 되어 3을 Unary로 표현하면 111이 된다.

나머지 값의 표현은 2^3과 14사이의 차이값을 넣어주면 될 것이다.

따라서

111 + 0 + (14 – 2^3) = 111 0 110

14를 압축한 값은 “111 0 110″가 된다.

이 방법을 Gamma Compression 방법이라고도 하는데,

위의 예제처럼 1,2,4,63,180 을 압축해보면

Value Compressed Bit String
1 0
2 10 0
4 110 00
63 1111 10 11111
180 11111110 0110100 (2^7 + 52)

위와 같은 결과가 나온다.

실제 위의 값을 Int형으로 고정된 형태로 집어 넣는다고 가정하면,

왜 압축을 쓰는지 알수 있을것이다.

Gamma Compression 응용방법으로 Posting List Size를 알고나서 더 좋은 압축 방법으로 압축하는 방법이 있다. 그러니까. d-gap의 숫자 범위 분포를 알면 이 방법보다 더 효율적으로 압축이 가능한 방법이다. 역시 gamma Compression방법의 응용이다.
일반적으로 Gamma Compression 계열의 압축 방법이 구현의 어려움은 있지만 압축률이 좋다고 일반적으로 알려져 있어서 이 부분은 나중에 더 자세히 써봐야 겠다.

헉 시간이 벌써 이렇게 되다니 ..

너무 늦었군.. 빨리 집에 가야겠다. ㅜㅜ

from future import dream

당신의 나의 뜨거운 감자!

관련