범용 부호

데이터 압축에서 범용 부호(Universal code)는 양의 정수를 구분자 없이 서로 구별되는 이진 부호로 대응시키는 접두 부호이며, 그 중 정수의 실제 확률 분포와 상관 없이 분포가 단조적이면 (즉 모든 정수 $i$에 대해 $p(i)\geq p(i+1)$이 성립) 부호 길이의 기댓값이 최적 부호 길이의 기댓값보다 최대 상수배보다 작은 것을 가리킨다. 특히 두 기댓값의 비율의 한계가 부호의 정보 엔트로피의 함수로 주어지며, 엔트로피가 무한대로 접근하면 함수값이 1이 될 때 그 부호를 점근적으로 최적이라고 한다.

일반적으로 대부분의 범용 부호는 정수가 클수록 더 긴 부호를 대응시킨다. 이러한 부호는 가능한 메시지의 종류가 정해져 있을 때 효과적으로 이용할 수 있는데, 메시지를 확률이 큰 것부터 배열해서 번호를 붙인 뒤 원하는 메시지의 번호를 전송하는 방법을 쓸 수 있다. 범용 부호는 일반적으로 확률 분포가 잘 알려져 있을 때는 쓰이지 않으며, 아직 실용적으로 쓰이는 확률 분포에 대해 최적으로 알려져 있는 범용 부호는 없다.

양의 정수가 아닌 정수 전체를 대응시키는 부호는 부호화 전에 정수 (0, 1, -1, 2, -2, 3, -3, …)를 양의 정수 (1, 2, 3, 4, 5, 6, 7, …)로 대응시켜서 범용 부호로부터 만들어 낼 수 있다.

종류

다음은 잘 알려진 범용 부호의 목록이다. 별표(*)로 표시한 것은 점근적으로 최적인 부호이다.

• 엘리어스 감마 부호
• 엘리어스 델타 부호 *
• 엘리어스 오메가 부호 *
• 지수 골롬 부호 (엘리어스 감마 부호를 포함함, MPEG-4에서 쓰임)
• 피보나치 부호 *
• 레벤시테인 부호 * (블라디미르 레벤시테인이 1968년 논문[1]에서 범용 부호를 소개하면서 함께 언급한 부호.)
• 바이트 부호 또는 콤마 부호 * (2비트 이상의 특수한 패턴이 하나의 부호를 끝내는 형식.)

다음은 범용 부호는 아니지만 모든 정수를 대응시키는 부호들의 목록이다.

• 일진 부호 (엘리어스 부호에서 사용됨)
• 라이스 부호 (일진 부호를 포함함. FLAC 코덱에서 사용됨)
• 골롬 부호 (라이스 부호와 일진 부호를 포함함)

이 부호들이 범용 부호가 아님은 가우스-쿠즈민 분포나 제타 분포(s=2)에 따르는 정수를 부호화하면 길이 기댓값이 무한대가 된다는 것으로 알 수 있다. 예를 들어서 일진 부호를 제타 분포에 적용하면 길이의 기댓값은 다음과 같다.

$E(l)={\frac {6}{\pi ^{2}}}\sum _{l=1}^{\infty }{\frac {1}{l}}=\infty$

반면 범용 부호인 엘리어스 감마 부호를 여기에 적용하면 길이의 기댓값은 약 3.51비트로, 엔트로피(약 3.43비트)에 근접한다.

참고 문헌

• David J. C. MacKay. Information Theory, Inference, and Learning Algorithms Cambridge: Cambridge University Press, 2003. ISBN 0-521-64298-1

외부 링크

• Кодирование целых чисел