// 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 は主に理論的解析や、上限のない整数を扱う場面で力を発揮します。