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

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

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

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

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

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

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

                               Предполагаемые вероятности
 1 = 20 + 0 = 1                  1/2
 2 = 21 + 0 = 010                1/8
 3 = 21 + 1 = 011                 "
 4 = 22 + 0 = 00100              1/32
 5 = 22 + 1 = 00101               "
 6 = 22 + 2 = 00110               "
 7 = 22 + 3 = 00111               "
 8 = 23 + 0 = 0001000            1/128
 9 = 23 + 1 = 0001001             "
10 = 23 + 2 = 0001010             "
11 = 23 + 3 = 0001011             "
12 = 23 + 4 = 0001100             "
13 = 23 + 5 = 0001101             "
14 = 23 + 6 = 0001110             "
15 = 23 + 7 = 0001111             "
16 = 24 + 0 = 000010000          1/512
17 = 24 + 1 = 000010001           "
…

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

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

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

Ссылки

Оригинал статьи на английском Elias gamma coding  (неопр.).