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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Описание алгоритма[править | править вики-текст]

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

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

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

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

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

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

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

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

  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++) //прочитать numberBits битов
        {
            if (current & (1 << a))
               bitwriter.putBit(true);
            else
               bitwriter.putBit(false);
        }
     }
}

См. также[править | править вики-текст]