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

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

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

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

Записать его в двоичной форме.
Перед двоичным представлением числа дописать нули. Количество нулей на единицу меньше количества битов двоичного представления числа.

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

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

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

Число	Значение	Кодирование	Предполагаемая вероятность
1	2⁰ + 0	1	1/2
2	2¹ + 0	0 1 0	1/8
3	2¹ + 1	0 1 1	1/8
4	2² + 0	00 1 00	1/32
5	2² + 1	00 1 01	1/32
6	2² + 2	00 1 10	1/32
7	2² + 3	00 1 11	1/32
8	2³ + 0	000 1 000	1/128
9	2³ + 1	000 1 001	1/128
10	2³ + 2	000 1 010	1/128
11	2³ + 3	000 1 011	1/128
12	2³ + 4	000 1 100	1/128
13	2³ + 5	000 1 101	1/128
14	2³ + 6	000 1 110	1/128
15	2³ + 7	000 1 111	1/128
16	2⁴ + 0	0000 1 0000	1/512
17	2⁴ + 1	0000 1 0001	1/512
…

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

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

Считать все нули, встречающиеся до первой 1. Пусть N — количество этих нулей.
Принимая во внимание единицу, которая станет первым (самая значащим) битом целого числа, со значением 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 = l-1; a >= 0; 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);
        }
     }
}

См. также

Литература

Universal codeword sets and representations of the integers (англ.) // IEEE Transactions on Information Theory^[англ.] : journal. — 1975. — March (vol. 21, no. 2). — P. 194—203. — doi:10.1109/tit.1975.1055349.