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

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

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

Чтобы закодировать число:

1. Записать его в двоичной форме.
2. Отнять (вычесть) 1 из числа битов, записанных на шаге 1 и приписать спереди недостающие нули.

Аналогичный способ описания этого процесса:

1. Разделить целое число на самую большую степень 2, которую оно включает (2^N), и на оставшиеся N двоичных цифр от данного целого числа.
2. Записать N в унарном коде; то есть N нолей, следующих за единицей.
3. Присоединить оставшиеся N двоичных цифр к этому представлению N.

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

                               Предполагаемые вероятности
  1 = 2<sup>0</sup> + ''0'' = 1                  1/2
  2 = 2<sup>1</sup> + ''0'' = 01''0''                1/8
  3 = 2<sup>1</sup> + ''1'' = 01''1''                 "
  4 = 2<sup>2</sup> + ''0'' = 001''00''              1/32
  5 = 2<sup>2</sup> + ''1'' = 001''01''               "
  6 = 2<sup>2</sup> + ''2'' = 001''10''               "
  7 = 2<sup>2</sup> + ''3'' = 001''11''               "
  8 = 2<sup>3</sup> + ''0'' = 0001''000''            1/128
  9 = 2<sup>3</sup> + ''1'' = 0001''001''             "
 10 = 2<sup>3</sup> + ''2'' = 0001''010''             "
 11 = 2<sup>3</sup> + ''3'' = 0001''011''             "
 12 = 2<sup>3</sup> + ''4'' = 0001''100''             "
 13 = 2<sup>3</sup> + ''5'' = 0001''101''             "
 14 = 2<sup>3</sup> + ''6'' = 0001''110''             "
 15 = 2<sup>3</sup> + ''7'' = 0001''111''             "
 16 = 2<sup>4</sup> + ''0'' = 00001''0000''          1/512
 17 = 2<sup>4</sup> + ''1'' = 00001''0001''           "
 ...

Распределение предполагаемых вероятностей для кодов добавлено для понятности.

Чтобы декодировать закодированное гамма-кодом Элиаса число следует:

1. Считать все нули, встречающиеся до первой 1. Пусть N — количество этих нулей.
2. Принимая во внимание единицу, которая была достигнута как первая цифра целого числа, со значением 2^N, считать оставшиеся 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++) //Read numberBits bits
        {
            if (current & (1 << a))
               bitwriter.putBit(true);
            else
               bitwriter.putBit(false);
        }
     }
}

См. также

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