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

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

Для того, чтобы закодировать число:
# Записать его в двоичном виде.
# Сосчитать биты и записать количество битов в двоичном виде (Х).
# Использовать двоичное значение, записанное в шаге 1 снова, удалить стоящий впереди бит и записать оставшиеся биты (Y).
# Присоединить второе двоичное значение (Y) к первому (X).
# Сосчитать биты, записанные в шаге 2 (X), вычесть 1 из этого числа и добавить в начало много нулей.

Аналогичным образом этот процесс можно описать так:
# Разделить целое число на самую большую степень 2, которую оно содержит (2<sup>N'</sup>), и оставшиеся N' двоичных цифр целого числа.
# Закодировать N = N' + 1 с помощью гамма-кода Элиаса.
# Добавить оставшиеся N' двоичных цифр к представлению N.

Начало кодирования:
<source lang="html4strict">
                                         Предполагаемые вероятности
 1 = 20 => N' = 0, N = 1 => 1             1/2
 2 = 21 + 0 => N' = 1, N = 2 => 0100      1/16
 3 = 21 + 1 => N' = 1, N = 2 => 0101       "
 4 = 2² + 0 => N' = 2, N = 3 => 01100     1/32
 5 = 2² + 1 => N' = 2, N = 3 => 01101      "
 6 = 2² + 2 => N' = 2, N = 3 => 01110      "
 7 = 2² + 3 => N' = 2, N = 3 => 01111      "
 8 = 2³ + 0 => N' = 3, N = 4 => 00100000  1/256
 9 = 2³ + 1 => N' = 3, N = 4 => 00100001   "
10 = 2³ + 2 => N' = 3, N = 4 => 00100010   "
11 = 2³ + 3 => N' = 3, N = 4 => 00100011   "
12 = 2³ + 4 => N' = 3, N = 4 => 00100100   "
13 = 2³ + 5 => N' = 3, N = 4 => 00100101   "
14 = 2³ + 6 => N' = 3, N = 4 => 00100110   "
15 = 2³ + 7 => N' = 3, N = 4 => 00100111   "
16 = 24 + 0 => N' = 4, N = 5 => 001010000 1/512
17 = 24 + 1 => N' = 4, N = 5 => 001010001  "
…
</source>

Чтобы декодировать число из Дельта-кода Элиаса:
# Прочитать и сосчитать количество нулей из потока, пока не встретится 1. Пусть L — количество нулей.
# Учитывая, что единица, которая была достигнута — это первая цифра целого числа, значение которого 2<sup>L</sup>, прочитать оставшиеся L цифр этого целого числа. Пусть N — прочитанное число.
# Поместить единицу на первое место конечного вывода, который представляет собой значение 2<sup>N</sup>-1. Прочитать и добавить следующие N-1 цифр.

Пример:
001010001
# 2 ведущих ноля в 001.
# вычесть 2 или более битов, то есть 00101.
# декодировать N = 00101 = 5.
# получится N' = 5 — 1 = 4 оставшихся бита для полного кода, то есть '0001'.
# закодировать число = 24 + 1 = 17.

Этот код может быть также применён к целым числам с нулевым или отрицательным значением (см.: [[гамма-код Элиаса]]).

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

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

[[en:Elias delta coding]]
[[ko:엘리어스 델타 부호]]
[[ja:デルタ符号]]