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

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

Кодирование

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

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

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

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

Чтобы представить число ${\displaystyle x}$, Дельта Элиаса (δ) использует ${\displaystyle \lfloor \log _{2}(x)\rfloor +2\lfloor \log _{2}(\lfloor \log _{2}(x)\rfloor +1)\rfloor +1}$ биты.^[1]:200

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

Число	N	N + 1	δ кодирование	Предполагаемая вероятность
1 = 2^0	0	1	1	1/2
2 = 2^1 + 0	1	2	0 1 0 0	1/16
3 = 2^1 + 1	1	2	0 1 0 1	1/16
4 = 2^2 + 0	2	3	0 1 1 00	1/32
5 = 2^2 + 1	2	3	0 1 1 01	1/32
6 = 2^2 + 2	2	3	0 1 1 10	1/32
7 = 2^2 + 3	2	3	0 1 1 11	1/32
8 = 2^3 + 0	3	4	00 1 00 000	1/256
9 = 2^3 + 1	3	4	00 1 00 001	1/256
10 = 2^3 + 2	3	4	00 1 00 010	1/256
11 = 2^3 + 3	3	4	00 1 00 011	1/256
12 = 2^3 + 4	3	4	00 1 00 100	1/256
13 = 2^3 + 5	3	4	00 1 00 101	1/256
14 = 2^3 + 6	3	4	00 1 00 110	1/256
15 = 2^3 + 7	3	4	00 1 00 111	1/256
16 = 2^4 + 0	4	5	00 1 01 0000	1/512
17 = 2^4 + 1	4	5	00 1 01 0001	1/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. закодированное число = 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.

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

• Хамада, Ходзуми (июнь 1983 г.). «URR: универсальное представление действительных чисел». Вычислительная техника нового поколения. 1 (2): 205–209. Дои:10.1007 / BF03037427. ISSN  0288-3635. Получено 2018-07-09. (NB. Δ-код Элиаса совпадает с URR-представлением Хамады.)