Изменения

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

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

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

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

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

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

# Запишите его в двоичной форме.

# Записать его в двоичной форме.

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

# Отнять (вычесть) 1 из числа битов, записанных на шаге 1 и приписать спереди недостающие нули.

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

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

# Разделите целое число на самую большую степень 2, которую оно включает (2N), и на оставшиеся N двоичных цифр от данного целого числа.

# Разделить целое число на самую большую степень 2, которую оно включает (2^N), и на оставшиеся N двоичных цифр от данного целого числа.

# Запишите N в унарном коде; то есть N нолей следующих за единицей.

# Записать N в унарном коде; то есть N нолей, следующих за единицей.

# Присоедините оставшиеся N двоичных цифр к этому представлению N.

# Присоединить оставшиеся N двоичных цифр к этому представлению N.

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

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

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

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

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

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

# Считать все встречающиеся до первой 1(единицы) нули. Назовем это количество нолей N.

# Считать все нули, встречающиеся до первой 1. Пусть N — количество этих нулей.

# Принимая во внимание единицу, которая была достигнута как первая цифра целого числа, с значением 2N, считайте оставшиеся N цифр целого числа.

# Принимая во внимание единицу, которая была достигнута как первая цифра целого числа, со значением 2^N, считать оставшиеся N цифр целого числа.

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

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

== Обобщения ==

== Обобщения ==

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

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

 

== Пример программного кода ==

== Пример программного кода ==

<source lang="c">

<source lang="c">

Кодирование

// Кодирование

void eliasGammaEncode(char* source, char* dest)

void eliasGammaEncode(char* source, char* dest)

{

{

       for (int a=0; a < l; a++) //напишите биты как простые двоичные числа

       for (int a=0; a < l; a++) //напишите биты как простые двоичные числа

       {

       {

                   if (num & 1 << a)

                   if (num & (1 << a))

                     bitwriter.putBit(true);

                     bitwriter.putBit(true);

                   else

                   else

     bitwriter.close();

     bitwriter.close();

}

}

Декодирование

// Декодирование

void eliasGammaDecode(char* source, char* dest)

void eliasGammaDecode(char* source, char* dest)

{

{

}

}

</source>

</source>

== См. также ==

== См. также ==

* [[Омега код Элиаса]]

* [[Омега-код Элиаса]]

* [[Дельта код Элиаса]]

* [[Дельта-код Элиаса]]

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

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

[[en:Elias gamma coding]]

[[en:Elias gamma coding]]

[[ko:엘리어스 감마 부호]]

[[ko:엘리어스 감마 부호]]

[[ja:ガンマ符号]]

[[ja:ガンマ符号]]