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

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

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

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

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

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

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

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

Число	Значение	Кодирование	Предполагаемая вероятность
1	20 + 0	1	1/2
2	21 + 0	0 10	1/8
3	21 + 1	0 11	1/8
4	2² + 0	00 100	1/32
5	2² + 1	00 101	1/32
6	2² + 2	00 110	1/32
7	2² + 3	00 111	1/32
8	2³ + 0	000 1000	1/128
9	2³ + 1	000 1001	1/128
10	2³ + 2	000 1010	1/128
11	2³ + 3	000 1011	1/128
12	2³ + 4	000 1100	1/128
13	2³ + 5	000 1101	1/128
14	2³ + 6	000 1110	1/128
15	2³ + 7	000 1111	1/128
16	24 + 0	0000 10000	1/512
17	24 + 1	0000 10001	1/512
…

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

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

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 numberBits = log2(num);

      // поместить numberBits нулей, чтобы показать, сколько бит будут следовать
      for (int a = numberBits - 1; a >= 0; a--)
      {       
          bitwriter.putBit(false);
      }

      // скопировать (numberBits + 1) битов числа
      for (int a = numberBits; 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);
     IntWriter intwriter(dest);

     while (bitreader.hasLeft())
     {
        int numberBits = 0;

        // продолжить чтение пока не встретится единица...
        while (bitreader.getBit() == false)
        {
            numberBits++;

            if (!bitreader.hasLeft())
            {
                // неожиданный конец потока битов
                // аварийный выход
                // игнорируем уже прочитанные биты
                return;
            }
        }

        if (numberBits > (sizeof(int) * BITS_PER_BYTE - 1))
        {
            // переполнение целочисленного типа
            // входной поток содержит неверные данные
            // аварийный выход
            // игнорируем уже прочитанные биты
            return;
        }

        int num = 1;

        // прочитать numberBits битов
        for (; numberBits > 0; numberBits--)
        {
            if (!bitreader.hasLeft())
            {
                // неожиданный конец потока битов
                // аварийный выход
                // игнорируем уже прочитанные биты
                return;
            }

            num = num << 1;

            if (bitreader.getBit() == true)
               num = num | 1;
        }

        intwriter.putInt(num);
     }

     intreader.close();
     bitwriter.close();
}

См. также

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