Редактирование: Гамма-код Элиаса

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

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

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

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

{| class="standard" style="text-align:right"
! Число || Значение || Кодирование || Предполагаемая<br />вероятность
|-
| 1 || 2<sup>0</sup> + 0 || 1 || 1/2
|-
| 2 || 2<sup>1</sup> + 0 || 0 1 0 || 1/8
|-
| 3 || 2<sup>1</sup> + 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<sup>4</sup> + 0 || 0000 1 0000 || 1/512
|-
|17 || 2<sup>4</sup> + 1 || 0000 1 0001 || 1/512
|-
|… || || ||
|}

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

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

# Считать все нули, встречающиеся до первой 1. Пусть N — количество этих нулей.
# Принимая во внимание единицу, которая станет первым (самая значащим) битом целого числа, со значением 2<sup>N</sup>, считать оставшиеся N цифр целого числа.

Гамма-кодирование используется в приложениях, где самое большое значение не может быть известно заранее, или чтобы сжать данные, в которых маленькие значения встречаются более часто чем большие.

== Обобщение ==
<!-- на этот заголовок есть ссылки из других статей -->
Гамма-кодирование не подходит для кодирования нулевых значений или отрицательных чисел. Единственный способ закодировать ноль — прибавить к нему 1 до кодирования и отнять после декодирования. Другой способ — приписать в начале любой ненулевой код с 1 , а затем кодировать ноль как простой 0. Единственный способ закодировать все целые числа — перед началом кодирования установить [[биекция|биекцию]] (соответствие), отображая целые числа из (0, 1, −1, 2, −2, 3, −3, …) в (1, 2, 3, 4, 5, 6, 7, …).

== Пример программного кода ==
<source lang="c">
// Кодирование
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);
        }
     }
}
</source>

== См. также ==
* [[Омега-код Элиаса]]
* [[Дельта-код Элиаса]]

[[Категория:Алгоритмы сжатия без потерь]]