Elias Omega Code
イライアスのオメガ符号は、長さ部分を再帰的に符号化する。3つのイライアス万能符号の中で大きな整数に対して最もコンパクトであり、符号長はlog2(n)+log2(log2(n))+...+O(1)である。
目的
整数の上限が未知で大きな値が頻出する場合に、最適な万能符号を提供する。
メカニズム
符号化は再帰的である：nから始めてfloor(log2(n))の2進表現を出力し、その長さを再帰的に符号化し、単一の0を終端マーカーとする。復号は逆再帰で値を再構築する。
ユースケース
- 非常に大きな整数の可変長符号化（variable-length）
- ユニバーサル符号の理論
- 再帰的な符号化の学習（recursive）