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

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

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

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

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);
        }
     }
}

Ссылки

переведено из en-wiki

См. также

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

en:Elias gamma coding ko:엘리어스 감마 부호 ja:ガンマ符号