> elias | gamma | universal <
// Elias Gamma ― パラメータ不要の正の整数向け普遍符号
普遍符号
追加パラメータなしで任意の正の整数を扱えます。
プレフィックスフリー
どのコードも他のコードの接頭辞にならないため、一意に復号できます。
漸近的に最適
特定の分布に対して最適圧縮に近い性能を発揮します。
>> 技術情報
Elias Gamma の仕組み:
Elias Gamma は正の整数 n を次のように符号化します。1) N = ⌊log₂(n)⌋ を求める、2) N 個の 0 を一元符号として書く、3) n の2進表現（長さ N+1 ビット）を続けて書く。結果として長さ (2N+1) ビットのコードが得られます。
符号化の例:
n=1: log₂(1)=0 コード: 1 (0 がなく、"1" のみ) n=2: log₂(2)=1 コード: 010 (0 が 1 個 + "10") n=5: log₂(5)=2 コード: 00101 (0 が 2 個 + "101") n=10: log₂(10)=3 コード: 0001010 (0 が 3 個 + "1010") 長さの式: 2⌊log₂(n)⌋ + 1
Elias Gamma を使う理由:
- >パラメータ不要
- >実装がシンプル
- >小さな整数に適している
- >普遍符号として理論的に重要
- >データ圧縮研究でよく用いられる
>> よくある質問
Elias Gamma 符号とは？
Elias Gamma は Peter Elias によって提案された、正の整数のための普遍符号です。各整数は、ビット長を一元符号で表し、その後に元の2進表現を続けることで符号化されます。データ分布を知らなくても利用できるため「普遍」な符号と呼ばれます。
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 や算術符号化ほど一般的ではありません。