일라이어스 감마 부호

일라이어스 감마 부호는 피터 일라이어스(Peter Elias)가 개발한 범용 부호(universal code) 중 하나로, 양의 정수를 가변 길이로 부호화하는 방식이다. 주로 데이터 압축 분야에서 사용되며, 특히 부호화할 숫자의 분포를 미리 알 수 없거나 작은 숫자가 자주 나타나는 경우에 효율적이다. 일라이어스 감마 부호는 접두 부호(prefix code)의 일종이므로, 별도의 구분자 없이도 고유하게 해독될 수 있다.

작동 원리

일라이어스 감마 부호는 양의 정수 $N$을 부호화할 때, $N$의 이진 표현 길이 정보와 $N$ 자체의 이진 표현 정보를 결합한다. 구체적인 부호화 과정은 다음과 같다.

1. 길이 정보($L$) 부호화:

   • 정수 $N$의 이진 표현에서 최상위 비트(MSB)를 제외한 나머지 비트의 개수, 즉 $N$의 이진 표현 길이에서 1을 뺀 값($\lfloor \log_2 N \rfloor$)만큼의 0을 앞에 붙이고, 그 뒤에 1을 붙인다. 이는 $\lfloor \log_2 N \rfloor$의 단항 부호(unary code) 표현과 같다.
   • 예를 들어, $N=13$ (이진수로 1101)의 이진 표현 길이는 4비트이다. $\lfloor \log_2 13 \rfloor = 3$이므로, 3개의 0 뒤에 1을 붙인 0001이 길이 정보가 된다.

2. 값 정보($S$) 부호화:

   • 정수 $N$의 이진 표현에서 최상위 비트(항상 1)를 제외한 나머지 비트들을 그대로 붙인다.
   • 예를 들어, $N=13$ (이진수로 1101)에서 최상위 비트 1을 제외한 101이 값 정보가 된다.

3. 결합:

   • 길이 정보($L$) 뒤에 값 정보($S$)를 붙여 최종 일라이어스 감마 부호를 완성한다.
   • $N=13$의 경우, 길이 정보 0001과 값 정보 101을 결합하여 최종 부호는 0001101이 된다.

예시

디코딩 원리

일라이어스 감마 부호를 디코딩하는 과정은 부호화의 역순으로 이루어진다.

1. 길이 정보($L$) 추출:

   • 수신된 비트 스트림에서 0이 연속되는 개수를 세다가 처음으로 1이 나타나면 멈춘다. 0의 개수($k$)가 $\lfloor \log_2 N \rfloor$ 값을 나타낸다.
   • 이때 1은 길이 정보의 끝을 나타내며, 이 1을 포함하여 $k+1$개의 비트가 길이 정보이다.

2. 값 정보($S$) 추출:

   • 길이 정보가 끝난 직후부터 $k$개의 비트를 읽는다. 이 $k$개의 비트가 $N$의 이진 표현에서 최상위 비트를 제외한 값 정보($S$)가 된다.

3. 정수 $N$ 복원:

   • 값 정보($S$) 앞에 최상위 비트 1을 붙여 $N$의 이진 표현을 완성하고, 이를 십진수로 변환한다.
   • 예를 들어, 0001101을 디코딩할 때:
     • 0001에서 0의 개수는 3개($k=3$)이므로, 다음 3개의 비트가 값 정보이다.
     • 다음 3개 비트는 101이다.
     • 101 앞에 1을 붙여 1101을 만들고, 이를 십진수로 변환하면 13이 된다.

특징 및 응용 분야

• 범용 부호(Universal Code): 어떤 확률 분포를 따르는 양의 정수열이든 부호화할 수 있으며, 최적의 효율을 보장하지는 않지만 합리적인 수준의 압축률을 제공한다.
• 접두 부호(Prefix Code): 모든 부호 단어는 다른 부호 단어의 접두사가 될 수 없으므로, 비트 스트림에서 각 숫자의 경계를 명확히 구분할 수 있다. 이는 고유한 디코딩을 가능하게 한다.
• 효율성: 작은 숫자에 대해서는 효율적이지만, 숫자가 커질수록 이진 표현 길이 정보($\lfloor \log_2 N \rfloor$)를 부호화하는 데 더 많은 0을 사용하게 되어 효율성이 다소 떨어진다.
• 단순성: 구현이 비교적 간단하다는 장점이 있다.

응용 분야:

• 데이터 압축: 특히 작은 숫자가 많이 등장하는 데이터(예: 텍스트 파일에서 단어의 빈도 수, 이미지 압축 시 작은 계수 값)를 압축할 때 유용하다.
• 색인 구조: 검색 엔진의 역색인(inverted index)과 같은 데이터 구조에서 문서 ID 간의 간격(gap)이나 빈도수를 저장할 때 사용될 수 있다.
• 그래프 표현: 그래프의 인접 리스트에서 노드 ID를 부호화할 때 사용되기도 한다.

다른 일라이어스 부호와의 비교

일라이어스 감마 부호 외에도 피터 일라이어스가 개발한 다른 범용 부호들이 있다.

• 일라이어스 델타 부호 (Elias Delta Code): 감마 부호와 유사하지만, 길이 정보 자체를 감마 부호로 다시 부호화하여 큰 숫자에 대해 감마 부호보다 더 효율적이다.
• 일라이어스 오메가 부호 (Elias Omega Code): 델타 부호보다 더 재귀적인 방식으로 길이 정보를 부호화하여 매우 큰 숫자에 대해 더 높은 압축률을 제공한다.

일라이어스 감마 부호는 이러한 일라이어스 계열 부호 중 가장 기본적이고 단순한 형태이며, 작은 숫자 범위에서 효율적인 압축을 제공한다.