エリアス オメガコーディング

エリアスωコーディングまたはエリアスオメガコーディングは、ピーターエリアスによって開発された正の整数をエンコードするユニバーサルコードです。エリアスガンマコーディングやエリアスデルタコーディングと同様に、このコーディングは正の整数の前にユニバーサルコードでその大きさの順序の表現を付加することで機能します。ただし、他の2つのコードとは異なり、エリアスオメガはそのプレフィックスを再帰的にエンコードするため、再帰エリアスコードと呼ばれることもあります。

オメガ コーディングは、エンコードされた最大の値が事前にわからないアプリケーションや、小さな値が大きい値よりも頻繁に使用されるデータを 圧縮するために使用されます。

正の整数 N をエンコードするには:

1. コードの最後に「0」を付けます。
2. N = 1の場合 、停止します。エンコードは完了です。
3. Nのバイナリ表現をコードの先頭に追加します。これは少なくとも 2 ビットになり、最初のビットは 1 になります。
4. N は、先頭に追加されたビット数から 1 を引いた値とします。
5. 手順 2 に戻り、新しいNのエンコードを先頭に追加します。

Elias オメガエンコードされた正の整数をデコードするには:

1. 変数N を値 1 に設定して開始します。
2. 次のビットが「0」の場合は停止します。デコードされた数値はNです。
3. 次のビットが「1」の場合は、それに加えてNビットを読み取り、その 2 進数をNの新しい値として使用します。手順 2 に戻ります。

オメガ コードは、いくつかの「グループ」として考えることができます。グループは、コードを終了する単一の 0 ビット、または 1 で始まる 2 つ以上のビットと、その後に続く別のグループのいずれかです。

最初のいくつかのコードを以下に示します。これには、このコーディングによって最小サイズのコードが生成される値の分布を記述する、いわゆる暗黙の分布が含まれます。詳細については、 「ユニバーサル コードと実際の圧縮の関係」を参照してください。

1グーゴル、10 ¹⁰⁰のエンコードは、11 1000 101001100 (長さヘッダーの 15 ビット) となり、その後に 1 グーゴルの 333 ビットのバイナリ表現が続きます。これは、10010 01001001 10101101 00100101 10010100 11000011 01111100 11101011 00001011 00100111 10000100 11000100 11001110 00001011 11110011 10001010 11001110 01000000 10001110 00100001 00011010 01111100 10101010 10110010 01000011 00001000 10101000 00101110 10001111 00010000 000000000 000000000 000000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 末尾の 0 で、合計 349 ビットになります。

1 グーゴルの 100 乗 (10 ¹⁰⁰⁰⁰ ) は、33,220 ビットの 2 進数です。オメガ符号化は 33,243 ビット長で、11 1111 1000000111000100 (22 ビット) に続いて 33,220 ビットの値と末尾の 0 が続きます。エリアスのデルタ符号化では、同じ数が 33,250 ビット長で、00000000000000 1000000111000100 (31 ビット) に続いて 33,219 ビットの値が続きます。オメガ符号化とデルタ符号化は、通常の 33,220 ビットの 2 進数表現よりもそれぞれ 0.07% と 0.09% 長くなります。

正の整数Nの符号化では、必要なビット数B ( N )は再帰的に次のようになります。つまり、整数 のエリアス オメガ コードの長さはです。ここで、和の項の数は、2 進反復対数で上方に制限されます。正確には、 とします。ある に対して であり、コードの長さは です。 なので、 となります。 $${\displaystyle {\begin{aligned}B(0)&=0\,,\\B(N)&=1+\lfloor \log _{2}(N)\rfloor +B(\lfloor \log _{2}(N)\rfloor )\,.\end{aligned}}}$$${\displaystyle N}$$${\displaystyle 1+(1+\lfloor \log _{2}N\rfloor {})+(1+\lfloor \log _{2}\lfloor \log _{2}N\rfloor {}\rfloor {})+\cdots }$$${\displaystyle f(x)=\lfloor \log _{2}x\rfloor {}}$${\displaystyle N>f(N)>f(f(N))>\cdots >f^{k}(N)=1}$${\displaystyle k}$${\displaystyle (k+1)+f(N)+f^{2}(N)+\dots +f^{k}(N)}$${\displaystyle f(x)\leq \log _{2}x}$${\displaystyle k\leq \log _{2}^{*}(N)}$

反復対数は任意の固定 に対してすべて よりも遅く増加するため、漸近的増加率は となり、合計が 1 を下回ると終了します。 ${\displaystyle \log_{2}^{n}N}$${\displaystyle n}$${\displaystyle \Theta (\log _{2}N+\log _{2}^{2}N+\cdots )}$

エリアスオメガ符号は漸近的に最適なプレフィックス符号である。^[1]

証明の概略。プレフィックス コードは、クラフト不等式を満たす必要があります。エリアス オメガ コーディングの場合、クラフト不等式は次のように示されます。ここで、合計は漸近的に積分と同じであり、次のようになります。分母が で終了する場合、積分は として発散します。ただし、分母が で終了する場合、積分は として収束します。エリアス オメガ コードは、発散と収束の境界上にあります。 $${\displaystyle \sum _{n=1}^{\infty }{\frac {1}{2^{O(1)+\log _{2}n+\log _{2}\log _{2}n+\cdots }}}\leq 1}$$$${\displaystyle \int _{1}^{\infty }{\frac {dx}{x\times \ln x\times \ln \ln x\cdots }}\leq O(1)}$$${\displaystyle \ln^{k}x}$${\displaystyle \ln ^{k+1}\infty }$${\displaystyle (\ln ^{k}x)^{1+\epsilon }}$${\displaystyle {\frac {1}{(\ln ^{k}\infty )^{\epsilon }}}}$

void eliasOmegaEncode ( char * source , char * dest ) { IntReader intreader ( source ); BitWriter bitwriter ( dest ); while ( intreader . hasLeft ()) { int num = intreader . getInt (); BitStack bits ; while ( num > 1 ) { int len = 0 ; for ( int temp = num ; temp > 0 ; temp >>= 1 ) // 1+floor(log2(num)) len ++ を計算します。for ( int i = 0 ; i < len ; i ++ ) bits . pushBit (( num >> i ) & 1 ); num = len - 1 ; } while ( bits . length () > 0 ) bitwriter . putBit ( bits . popBit ()); bitwriter . putBit ( false ); // ゼロを 1 つ書き込む} bitwriter . close (); intreader . close (); }    

     
     
     
    
           
         
            
               
                        
                
                    
                    
                
        
           
            
                                
    
    
    

void eliasOmegaDecode ( char * source , char * dest ) { BitReader bitreader ( source ); IntWriter intwriter ( dest ); while ( bitreader . hasLeft ()) { int num = 1 ; while ( bitreader . inputBit ()) // 不正なファイルの場合、潜在的に危険です。{ int len = num ; num = 1 ; for ( int i = 0 ; i < len ; ++ i ) { num <<= 1 ; if ( bitreader . inputBit ()) num |= 1 ; } } intwriter . putInt ( num ); // 値を書き出します} bitreader . close (); intwriter . close (); }     
     
     
     
    
           
              
        
               
              
                    
            
                  
                 
                      
            
        
                   
    
    
    

エリアスのオメガ コーディングでは、ゼロまたは負の整数はエンコードされません。すべての非負整数をエンコードする 1 つの方法は、エンコード前に 1 を加算し、デコード後に 1 を減算するか、非常によく似たレーベンシュタイン コーディングを使用することです。すべての整数をエンコードする 1 つの方法は、エンコード前にすべての整数 (0、1、-1、2、-2、3、-3、...) を厳密に正の整数 (1、2、3、4、5、6、7、...) にマッピングする一対一変換を設定することです。

• エリアスデルタ（δ）コーディング
• エリアスガンマ（γ）コーディング
• イーブン・ロデ符号化

• エリアス、ピーター(1975 年 3 月)。「ユニバーサル コードワード セットと整数の表現」IEEE Transactions on Information Theory 21 ( 2): 194–203。doi : 10.1109 /tit.1975.1055349。
• Fenwick, Peter (2003)。 「ユニバーサル コード」。Sayood, Khalid (編)。ロスレス圧縮ハンドブック。ニューヨーク、ニューヨーク、米国: Academic Press。pp . 55–78。doi :10.1016/B978-012620861-0/ 50004-8。ISBN 978-0123907547。

• Pythonでの実装