Дельта-кодирование Элиаса - Википедия - Elias delta coding

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

Кодирование

Чтобы закодировать номер Икс ≥ 1:

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

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

  1. Отдельный Икс в наивысшей степени двойки он содержит (2N) и остальные N двоичные цифры.
  2. Кодировать N+1 с Гамма-кодирование Элиаса.
  3. Добавьте оставшиеся N двоичные цифры к этому представлению N+1.

Чтобы представить число , Дельта Элиаса (δ) использует биты.[1]:200

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

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

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

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

Пример:

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

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

Пример кода

Кодирование

пустота eliasDeltaEncode(char* источник, char* dest){    IntReader читатель(источник);    BitWriter битрайтер(dest);    пока (читатель.оставил())    {        int число = читатель.getInt();        int len = 0;        int lengthOfLen = 0;        len = 1 + этаж(log2(число));  // вычисляем 1 + этаж (log2 (num))        lengthOfLen = этаж(log2(len)); // вычисляем этаж (log2 (len))              за (int я = lengthOfLen; я > 0; --я)            битрайтер.outputBit(0);        за (int я = lengthOfLen; я >= 0; --я)            битрайтер.outputBit((len >> я) & 1);        за (int я = len-2; я >= 0; я--)            битрайтер.outputBit((число >> я) & 1);    }    битрайтер.Закрыть();    читатель.Закрыть();}

Расшифровка

пустота eliasDeltaDecode(char* источник, char* dest){    BitReader битрейдер(источник);    IntWriter интрайтер(dest);    пока (битрейдер.оставил())    {        int число = 1;        int len = 1;        int lengthOfLen = 0;        пока (!битрейдер.inputBit())     // потенциально опасно с искаженными файлами.            lengthOfLen++;        за (int я = 0; я < lengthOfLen; я++)        {            len <<= 1;            если (битрейдер.inputBit())                len |= 1;        }        за (int я = 0; я < len-1; я++)        {            число <<= 1;            если (битрейдер.inputBit())                число |= 1;        }        интрайтер.положить(число);            // записываем значение    }    битрейдер.Закрыть();    интрайтер.Закрыть();}

Обобщения

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

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

Рекомендации

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

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