// Elias Omega – 임의로 큰 정수를 위한 점근적으로 최적인 코드
매우 큰 정수에 대해 이론적인 최소 길이에 가까워집니다.
길이를 재귀적으로, 그리고 우아하게 인코딩합니다.
추가 매개변수 없이 모든 양의 정수에 사용할 수 있습니다.
Elias Omega는 숫자의 길이를 값이 1이 될 때까지 재귀적으로 인코딩합니다. n에서 시작하여 log₂(n)을 인코딩하고, 이어서 log₂(log₂(n))을 인코딩하는 식으로 1에 도달할 때까지 계속합니다. 코드는 이러한 값들을 역순으로 이어 붙이고 마지막에 0을 붙여 구성됩니다. 결과적으로 log(n) + log(log(n)) + log(log(log(n))) + ... 비트를 사용합니다.
n=16: 16 → 2진수: 10000 (길이 5) 5 → 2진수: 101 (길이 3) 3 → 2진수: 11 (길이 2) 2 → 2진수: 10 (길이 2) 1 → 종료 코드를 뒤에서부터 구성: 0으로 시작 (종료 비트) 앞에 10 추가 (2를 인코딩) 앞에 11 추가 (3을 인코딩) 앞에 101 추가 (5를 인코딩) 앞에 10000 추가 (16을 인코딩) 결과: 10 11 101 10000 0 효율 비교: n=100: Gamma=13, Delta=12, Omega=10 비트 n=1000: Gamma=19, Delta=16, Omega=14 비트
Elias Omega는 Elias 계열에서 가장 복잡한 코드로, 길이 정보를 재귀적으로 인코딩하여 점근적으로 최적인 특성을 얻습니다. 표현의 길이, 그 길이의 길이 등을 1이 될 때까지 반복해서 인코딩하므로 매우 큰 정수에 대해 매우 효율적인 코드를 제공합니다.
작은 수 (< 10)에는 보통 Gamma가 가장 효율적입니다. 중간 크기 (10–1000)에서는 Delta가 더 좋은 결과를 제공합니다. 큰 수 (> 1000)에서는 Omega의 우수성이 점점 커집니다. Omega는 log*(n) 반복을 사용하며, 점근적으로 최적인 동작을 달성합니다.
코드 길이와 이론적인 최소 길이의 비가 n이 증가함에 따라 1에 수렴하면, 그 코드를 점근적으로 최적이라고 부릅니다. Omega의 경우 length(n)/log₂(n) → 1 (n → ∞)라는 성질을 만족합니다.
이론적으로는 뛰어나지만, Omega는 구현과 디코딩이 더 복잡합니다. 값의 범위가 제한된 실제 데이터에서는 Exp-Golomb나 Rice와 같은 단순한 코드가 더 실용적인 경우가 많습니다. Omega는 주로 이론 분석 및 무한대에 가까운 정수를 다루는 상황에서 빛을 발합니다.