http://borame.cs.pusan.ac.kr/ai_home/lecture/MG/mg03.ppt
(그렇다.. 또 managing gigabytes란 책이다. 대체 저 책에 안나온건 뭐란 말인가..)

Inverted Index등에서 Compression으로 사용할 수 있는

\gamma

인코딩 방법에 대한 설명.

먼저 Variable Length로 어떤 수를 저장하는 가장 간단한 방법은 1을 0, 2를 10, 3을 110, 4를 1110, 5를 11110, … 과 같이 1의 갯수를 사용해 어떤 수를 표현하는 것이다. 그러나 이 인코딩 방법은 작은 숫자에 대해서 유리하고 큰 숫자에 대해서 불리하다. 그런 이유로 ppt 슬라이드에

Pr[x] = 2^{-x}

란 표현이 있는데, 이는 어떤 수

x

가 나올 확률이

x

의 크기에 따라 exponentially decay해야만 unary encoding이 유리하다는 의미이다.

반면에

\gamma

인코딩은

1 + \lfloor log x \rfloor

bit의 unary code와

\lfloor log x \rfloor

bit binary code로 표현한다. 한 예로 9는

\lfloor 9 \rfloor = 3

이므로 1+3=4 비트로 unary encoding한다. 즉 앞자리는 1110. 다음 남은 수자 1 이므로 이를

\lfloor 9 \rfloor = 3

비트로 인코딩한다. 즉 뒷자리는 001. 합치면 1110001.

이외에도 Golomb code와 같은 인코딩 기법, 잘 아는 lossy encoidng이 있다.