> elias | gamma | universal <
// Elias Gamma – 매개변수 없이 양의 정수를 위한 범용 코드
범용 코드
추가 매개변수 없이 모든 양의 정수에 사용 가능합니다.
프리픽스 프리
어떤 코드도 다른 코드의 접두사가 아니므로 복호화가 항상 한 번에 결정됩니다.
점근적으로 최적
특정 분포에 대해 이론적인 최적 압축에 근접합니다.
>> 기술 정보
Elias Gamma의 동작 방식:
Elias Gamma는 양의 정수 n을 다음과 같이 부호화합니다. 1) N = ⌊log₂(n)⌋를 계산한다, 2) N개의 0를 일진법(unary) 코드로 쓴다, 3) n의 이진 표현(N+1비트)을 뒤에 붙인다. 결과 코드는 길이가 (2N+1)비트가 됩니다.
부호화 예시:
n=1: log₂(1)=0 코드: 1 (0 없이 "1"만) n=2: log₂(2)=1 코드: 010 (0 한 개 + "10") n=5: log₂(5)=2 코드: 00101 (0 두 개 + "101") n=10: log₂(10)=3 코드: 0001010 (0 세 개 + "1010") 길이 공식: 2⌊log₂(n)⌋ + 1
Elias Gamma를 사용할 이유:
- >추가 매개변수 불필요
- >구현이 단순함
- >작은 정수에 적합
- >범용 부호 체계
- >정보 이론과 압축 연구에서 중요한 역할
>> 자주 묻는 질문
Elias Gamma 부호란 무엇인가요?
Elias Gamma는 Peter Elias가 제안한 양의 정수를 위한 범용 부호입니다. 각 정수는 비트 길이를 일진법으로 기록하고, 그 뒤에 실제 이진 표현을 붙여 부호화됩니다. 데이터 분포를 모르더라도 사용할 수 있기 때문에 "범용" 부호라고 불립니다.
Elias Gamma는 언제 효율적인가요?
Elias Gamma는 멱법칙 분포(P(n) ∝ n^-2)를 따르는 정수에 대해 가장 효율적입니다. 대략 2log₂(n)+1비트를 사용하므로 작은 값에 적합하지만, 매우 큰 값에서는 효율이 떨어질 수 있습니다.
Gamma, Delta, Omega의 차이는?
Elias Gamma는 2log₂(n)+1비트를 사용합니다. Delta는 이를 log₂(n)+2log₂(log₂(n)+1)+1비트까지 줄여주고, Omega는 매우 큰 수에 대해 더 나은 압축을 제공합니다. Gamma는 가장 단순하고, Delta는 중간 크기의 값에, Omega는 큰 n에 적합합니다.
Elias 부호는 어디에서 사용되나요?
Elias 부호는 정보 이론, 데이터 압축 연구 및 일부 특수 압축 알고리즘에서 사용됩니다. 범용 부호로서 이론적으로 중요하지만, 실무에서는 허프만(Huffman)이나 산술 부호(arithmetic coding)만큼 널리 쓰이지는 않습니다.