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

Код Элиаса δ или дельта-код Элиаса — это универсальный код , кодирующий положительные целые числа, разработанный Питером Элиасом . ^[1]^: 200

Кодирование

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

Пусть N = ⌊log ₂ X ⌋; быть высшей степенью 2 в X , поэтому 2 ^Н ≤ Х < 2 ^{Н +1}.
Пусть L = ⌊log ₂ N +1⌋ — высшая степень двойки в N +1, поэтому 2 ^л ≤ N +1 < 2 ^{Л +1}.
Напишите L нулей, а затем
L N +1-битное двоичное представление +1 , за которым следует
все, кроме ведущего бита (т.е. последних N бит) X .

Эквивалентный способ выразить тот же процесс:

Разделите X на высшую степень двойки, которую он содержит (2 ^Н) и оставшиеся N двоичных цифр.
Закодируйте N +1 с помощью гамма-кодирования Элиаса .
Добавьте оставшиеся N двоичных цифр к этому представлению N +1.

Чтобы представить число $x$ , используется дельта Элиаса (δ) $\lfloor \log _{2}(x)\rfloor +2\lfloor \log _{2}(\lfloor \log _{2}(x)\rfloor +1)\rfloor +1$ биты. ^[1]^: 200Это полезно для очень больших целых чисел, когда общее количество битов закодированного представления оказывается меньше [чем можно было бы получить с помощью гамма-кодирования Элиаса ] из-за $\log _{2}(\lfloor \log _{2}(x)\rfloor +1)$ часть предыдущего выражения.

Код начинается с использования $\gamma '$ вместо $\gamma$ :

Число	Н	Н+1	δ-кодирование	Подразумеваемая вероятность
1 = 2 ⁰	0	1	`1`	1/2

2 = 2 ¹ + 0	1	2	`0 1 0 0`	1/16
3 = 2 ¹ + 1	1	2	`0 1 0 1`	1/16

4 = 2 ² + 0	2	3	`0 1 1 00`	1/32
5 = 2 ² + 1	2	3	`0 1 1 01`	1/32
6 = 2 ² + 2	2	3	`0 1 1 10`	1/32
7 = 2 ² + 3	2	3	`0 1 1 11`	1/32

8 = 2 ³ + 0	3	4	`00 1 00 000`	1/256
9 = 2 ³ + 1	3	4	`00 1 00 001`	1/256
10 = 2 ³ + 2	3	4	`00 1 00 010`	1/256
11 = 2 ³ + 3	3	4	`00 1 00 011`	1/256
12 = 2 ³ + 4	3	4	`00 1 00 100`	1/256
13 = 2 ³ + 5	3	4	`00 1 00 101`	1/256
14 = 2 ³ + 6	3	4	`00 1 00 110`	1/256
15 = 2 ³ + 7	3	4	`00 1 00 111`	1/256

16 = 2 ⁴ + 0	4	5	`00 1 01 0000`	1/512
17 = 2 ⁴ + 1	4	5	`00 1 01 0001`	1/512

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

Прочитайте и посчитайте нули из потока, пока не дойдете до первого. Назовите это количество нулей L .
Учитывая, что достигнутая цифра является первой цифрой целого числа со значением 2 ^л, прочитайте оставшиеся L цифр целого числа. Назовите это целое число N +1 и вычтите единицу, чтобы получить N .
Поместите единицу на первое место нашего окончательного результата, обозначая значение 2. ^Н.
Прочитайте и добавьте следующие N цифр.

Пример:

0010100111. 2 ведущих нуля в числе 001.2. прочитать еще 2 бита, т.е. 001013. декодируем N+1 = 00101 = 54. получить N = 5 − 1 = 4 оставшихся бита для полного кода, т. е. «0011».5. закодированное число = 2 ⁴ + 3 = 19

Этот код можно обобщить до нуля или отрицательных целых чисел теми же способами, что описаны в гамма-кодировании Элиаса .

Пример кода

Кодирование

void   eliasDeltaEncode  (  char  *   source  ,   char  *   dest  )  {      IntReader   intreader  (  source  );      BitWriter   битрайтер  (  dest  );      в то время как   (  intreader  .  hasLeft  ())      {          int   num   =   intreader  .  получитьИнт  ();          интервал   Лен   =   0  ;          int   lengthOfLen   =   0  ;          len   =   1   +   пол  (  log2  (  число  ));    // вычисляем 1+floor(log2(num))          lengthOfLen   =   Floor  (  log2  (  len  ));   // вычисление Floor(log2(len)                для   (  int   i   =   lengthOfLen  ;   i   >   0  ;   --i  bitwriter  )              )  .  выходной бит  (  0  );          for   (  int   i   =   lengthOfLen  ;   i   >=   0  ;   --  i  )              bitwriter  .  выходной бит  ((  len   >>   i  )   &   1  );          for   (  int   i   =   len  -2  ;   i   >=   0  ;   i  --  )              bitwriter  .  выходной бит  ((  число   >>   i  )   &   1  );      }      битрайтер  .  закрывать  ();      интертредер  .  закрывать  ();  }

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

void   eliasDeltaDecode  (  char  *   source  ,   char  *   dest  )  {      BitReader   bitreader  (  source  );      IntWriter   intwriter  (  место назначения  );      while   (  bitreader  .  hasLeft  ())      {          int   num   =   1  ;          интервал   Лен   =   1  ;          int   lengthOfLen   =   0  ;          while   (  !  bitreader  .  inputBit  ())       // потенциально опасно для некорректных файлов.              длинаОфЛен  ++  ;          for   (  int   я   =   0  ;   я   <   lengthOfLen  ;   я  ++  )          {              len   <<=   1  ;              если   (  bitreader  .  inputBit  ())                  len   |=   1  ;          }          for   (  int   я   =   0  ;   я   <   len  -1  ;   я  ++  )          {              num   <<=   1  ;              если   (  bitreader  .  inputBit  ())                  число   |=   1  ;          }          Инрайтер  .  putInt  (  число  );              // записываем значение      }      bitreader  .  закрывать  ();      автор  .  закрывать  ();  }

Обобщения

Дельта-кодирование Элиаса не кодирует ноль или отрицательные целые числа.Один из способов кодирования всех неотрицательных целых чисел — добавить 1 перед кодированием, а затем вычесть 1 после декодирования.Один из способов кодирования всех целых чисел — установить биекцию , отображающую целые числа, все целые числа (0, 1, −1, 2, −2, 3, −3, ...) в строго положительные целые числа (1, 2, 3, 4, 5, 6, 7, ...) перед кодированием.Эту биекцию можно выполнить с использованием кодировки «ZigZag» из протокольных буферов (не путать с кодом Zigzag или зигзагообразным энтропийным кодированием JPEG ).

См. также

Ссылки

^ Перейти обратно: ^а ^б Элиас, Питер (март 1975 г.). «Универсальные наборы кодовых слов и представления целых чисел». Транзакции IEEE по теории информации . 21 (2): 194–203. дои : 10.1109/тит.1975.1055349 .

Дальнейшее чтение

Хамада, Ходзуми (июнь 1983 г.). «URR: Универсальное представление действительных чисел» . Компьютеры нового поколения . 1 (2): 205–209. дои : 10.1007/BF03037427 . ISSN 0288-3635 . S2CID 12806462 . Проверено 9 июля 2018 г. (Примечание. Код Элиаса δ совпадает с представлением URR Хамады.)

[Elias-1] Перейти обратно: ^а ^б Элиас, Питер (март 1975 г.). «Универсальные наборы кодовых слов и представления целых чисел». Транзакции IEEE по теории информации . 21 (2): 194–203. дои : 10.1109/тит.1975.1055349 .

[1]