エリアスデルタコーディング

エリアスδコードまたはエリアスデルタコードは、ピーターエリアスによって開発された正の整数を符号化する汎用コードです。^{[1] : 200}

X ≥ 1 の数値をコード化するには :

1. N  = ⌊log ₂ X ⌋ をXにおける 2 の最大の累乗とすると、 2 ^N ≤ X < 2 ^{N +1 と}なります。
2. L  = ⌊log ₂ N +1⌋ をN +1における 2 の最大の累乗とすると、 2 ^L ≤ N +1 < 2 ^{L +1 と}なります。
3. L個のゼロを書き、続いて
4. N +1のL +1ビットの2進表現、続いて
5. Xの先頭ビット (つまり最後のNビット)を除くすべて。

同じプロセスを表現する同等の方法:

1. X を、そこに含まれる 2 の最大の累乗 (2 ^N ) と残りのN個の 2 進数字に分けます。
2. N +1 をEliasガンマコーディングでエンコードします。
3. 残りのNバイナリ桁をN +1のこの表現に追加します。

数値を表現するために、エリアスのデルタ(δ)はビットを使用します。^{[1] : 200}これは、前の式の部分により、全体的なエンコードされた表現のビットが[エリアスのガンマ符号化を使用して得られるものよりも] 少なくなる非常に大きな整数に役立ちます。 ${\displaystyle x}$${\displaystyle \lfloor \log _{2}(x)\rfloor +2\lfloor \log _{2}(\lfloor \log _{2}(x)\rfloor +1)\rfloor +1}$${\displaystyle \log _{2}(\lfloor \log _{2}(x)\rfloor +1)}$

コードは、の代わりにを使用して始まります。 ${\displaystyle \gamma '}$${\displaystyle \gamma}$

Elias デルタコード化整数をデコードするには:

1. 最初のゼロに到達するまで、ストリームからゼロを読み取ってカウントします。このゼロのカウントをL と呼びます。
2. ^{到達した数字が 2 L}の整数の最初の桁であると考えて、残りのL桁の整数を読み取ります。この整数をN +1 と呼び、 1 を引くとNになります。
3. 最終出力の先頭に 1 を配置し、値 2 ^Nを表します。
4. 次のN桁を読み取って追加します。

例：

001010011
1. 001 の先頭のゼロが 2 つ
2. さらに2ビット、つまり00101を読み込みます。
3. N+1をデコード = 00101 = 5
4. 完全なコード、つまり「0011」の残りのビットはN = 5 − 1 = 4になります。
5. エンコードされた数字 = 2 4 + 3 = 19

このコードは、 Elias ガンマ コーディングで説明されているのと同じ方法で、ゼロまたは負の整数に一般化できます。

void eliasDeltaEncode ( char * source , char * dest ) { IntReaderイントリーダー( source ); BitWriterビットライター( dest ); while ( intreader . hasLeft ()) { int num = intreader . getInt (); int len = 0 ; int lengthOfLen = 0 ;    

     
     
     
    
           
           
           

        len = 1 + floor ( log2 ( num )); // 1+floor(log2(num)) を計算しますlengthOfLen = floor ( log2 ( len )); // floor(log2(len)) を計算しますfor ( int i = lengthOfLen ; i > 0 ; -- i ) bitwriter . outputBit ( 0 ); for ( int i = lengthOfLen ; i >= 0 ; -- i ) bitwriter . outputBit (( len >> i ) & 1 ); for ( int i = len -2 ; i >= 0 ; i -- ) bitwriter . outputBit (( num >> i ) & 1 ); } bitwriter . close (); intreader . close (); }      
           
      
                
            
                
                
                
                
    
    
    

void eliasDeltaDecode ( char * source , char * dest ) { BitReader bitreader ( source ); IntWriter intwriter ( dest ); while ( bitreader . hasLeft ()) { int num = 1 ; int len = 1 ; int lengthOfLen = 0 ; while ( ! bitreader . inputBit ()) // 不正なファイルの場合、潜在的に危険です。lengthOfLen ++ ; for ( int i = 0 ; i < lengthOfLen ; i ++ ) { len <<= 1 ; if ( bitreader . inputBit ()) len |= 1 ; } for ( int i = 0 ; i < len -1 ; 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、...) にマッピングする一対一変換を設定することです。この一対一変換は、プロトコル バッファーの「ジグザグ」符号化を使用して実行できます (ジグザグ コードやJPEG ジグザグ エントロピー符号化と混同しないでください)。

• エリアスガンマ（γ）コーディング
• エリアスオメガ（ω）コーディング
• ゴロム・ライスコード

• 浜田穂積 (1983 年 6 月). 「URR: 実数のユニバーサル表現」.新世代コンピューティング. 1 (2): 205–209. doi :10.1007/BF03037427. ISSN  0288-3635. S2CID  12806462. 2018 年 7 月 9 日閲覧.(注: エリアス δ コードは Hamada の URR 表現と一致します。)