본문으로 이동

범용 부호

위키백과, 우리 모두의 백과사전.

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

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

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

종류

[편집]

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

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

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

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

참고 문헌

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

외부 링크

[편집]