Гамма-код Элиаса

Гамма-код Элиаса — это универсальный код для кодирования положительных целых чисел, разработанный Питером Элиасом. Он обычно используется при кодировании целых чисел, максимальное значение которых не может быть определено заранее.

Описание алгоритма

Чтобырший значащий бит (самую большую степень 2, которую число включает — 2^N) и младшие N бит.

1. Записать N в унарном коде; то есть N нолей, за которыми следует единица.
2. Дописать N младших двоичных цифр числа следом за этим унарным кодом.

Начало кодирования:

Обобщение

Гамма-кодирование не подходит для кодирования нулевых значений или отрицательных чисел. Единственный способ закодировать ноль — прибавить к нему 1 до кодирования и отнять после декодирования. Другой способ — приписать в начале любой ненулевой код с 1 , а затем кодировать ноль как простой 0. Единственный способ закодировать все целые числа — перед началом кодирования установить биекцию (соответствие), отображая целые числа из (0, 1, −1, 2, −2, 3, −3, …) в (1, 2, 3, 4, 5, 6, 7, …).

Пример программного кода

// Кодирование
void eliasGammaEncode(char* source, char* dest)
{
     IntReader intreader(source);
     BitWriter bitwriter(dest);
     while(intreader.hasLeft{
      int num = intreader.getInt();
      int l = log2(num);
      for (int a=0; a < l; a++)
      {       
          bitwriter.putBit(false); //поместить нули, чтобы показать, сколько бит будут следовать
      }
      bitwriter.putBit(true); //пометить конец нолей
      for (int a=0; a < l; a++) //записать биты как простые двоичные числа
      {
                  if (num & (1 << a))
                     bitwriter.putBit(true);
                  else
                     bitwriter.putBit(false);
      }
     }
     intreader.close();
     bitwriter.close();
}
// Декодирование
void eliasGammaDecode(char* source, char* dest)
{
     BitReader bitreader(source);
     BitWriter bitwriter(dest);
     int numberBits = 0;
     while(bitreader.hasLeft())
     {
        while(!bitreader.getBit() || bitreader.hasLeft())numberBits++; //продолжить чтение пока не встретится единица...
        int current = 0;
        for (int a=0; a < numberBits; a++) //прочитать numberBits битов
        {
            if (bitreader.getBit())
               current += 1 << a;
        }
        //записать его как 32-битное число
 
        current = current | ( 1 << numberBits ) ;//последний бит не декодируется!
        for (int a=0; a < 32; a++) //прочитать numberBits битов
        {
            if (current & (1 << a))
               bitwriter.putBit(true);
            else
               bitwriter.putBit(false);
        }
     }
}

См. также

• Омега-код Элиаса
• Дельта-код Элиаса

[[Категория:Алгоритмы сжатия без потерь]до ре ми фа соль ля си]

Число	Значение	Кодирование	Предполагаемая вероятность
1	20 + 0	1	1/2
11	2³ + 3	0001 011	1/128