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

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

Кодирование

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

  1. Пусть N  = ⌊log 2 X ⌋; — наибольшая степень числа 2 в X , поэтому 2 N ≤ X < 2 N +1 .
  2. Пусть L  = ⌊log 2 N +1⌋ будет наибольшей степенью числа 2 в N +1, поэтому 2 L ≤ N +1 < 2 L +1 .
  3. Напишите L нулей, а затем
  4. двоичное представление числа N +1 в формате L +1 , за которым следует
  5. все, кроме начального бита (т.е. последних N бит ) X.

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

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

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

Код начинается с использования вместо : γ ′ {\displaystyle \гамма '} γ {\displaystyle \гамма}

ЧислоНН+1δ-кодированиеПодразумеваемая вероятность
1 = 2 00111/2
2 = 2 1 + 0120 1 0 01/16
3 = 2 1 + 1120 1 0 11/16
4 = 2 2 + 0230 1 1 001/32
5 = 2 2 + 1230 1 1 011/32
6 = 2 2 + 2230 1 1 101/32
7 = 2 2 + 3230 1 1 111/32
8 = 2 3 + 03400 1 00 0001/256
9 = 2 3 + 13400 1 00 0011/256
10 = 2 3 + 23400 1 00 0101/256
11 = 2 3 + 33400 1 00 0111/256
12 = 2 3 + 43400 1 00 1001/256
13 = 2 3 + 53400 1 00 1011/256
14 = 2 3 + 63400 1 00 1101/256
15 = 2 3 + 73400 1 00 1111/256
16 = 2 4 + 04500 1 01 00001/512
17 = 2 4  +  14500 1 01 00011/512

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

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

Пример:

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

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

Пример кода

Кодирование

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

Расшифровка

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

Обобщения

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

Смотрите также

Ссылки

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

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

  • Хамада, Ходзуми (июнь 1983 г.). «URR: Универсальное представление действительных чисел». New Generation Computing . 1 (2): 205– 209. doi :10.1007/BF03037427. ISSN  0288-3635. S2CID  12806462. Получено 09.07.2018 .(Примечание. Код Элиаса δ совпадает с представлением URR Хамады.)
Взято с "https://en.wikipedia.org/w/index.php?title=Elias_delta_coding&oldid=1261412701"