범용 부호

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

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

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

 종류 

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

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

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

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

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

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

 참고 문헌 
 David J. C. MacKay. Information Theory, Inference, and Learning Algorithms Cambridge: Cambridge University Press, 2003. 

 외부 링크 
 Кодирование целых чисел

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