범용 부호 문서 원본 보기

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

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

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

== 종류 ==

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

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

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

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

이 부호들이 범용 부호가 아님은 [[가우스-쿠즈민 분포]]나 [[제타 분포]](s=2)에 따르는 정수를 부호화하면 길이 기댓값이 무한대가 된다는 것으로 알 수 있다. 예를 들어서 일진 부호를 제타 분포에 적용하면 길이의 기댓값은 다음과 같다.
: <math>E(l) = \frac{6}{\pi^2} \sum_{l=1}^\infty \frac{1}{l} = \infty</math>
반면 범용 부호인 엘리어스 감마 부호를 여기에 적용하면 길이의 기댓값은 약 3.51비트로, 엔트로피(약 3.43비트)에 근접한다.

== 참고 문헌 ==
* David J. C. MacKay. [http://www.inference.phy.cam.ac.uk/mackay/itila/book.html Information Theory, Inference, and Learning Algorithms] Cambridge: [[케임브리지 대학교 출판부|Cambridge University Press]], 2003. {{ISBN|0-521-64298-1}}

== 외부 링크 ==
* [https://web.archive.org/web/20070214150309/http://www-lat.compression.ru/download/integers.html Кодирование целых чисел]

{{압축 방식}}

{{전거 통제}}

[[분류:무손실 압축 알고리즘]]
[[분류:데이터 압축]]