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

Код Элиаса δ или дельта-код Элиаса — это универсальный код , кодирующий положительные целые числа, разработанный Питером Элиасом . ^[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 цифр.

Пример:

001010011
1. 2 leading zeros in 001
2. read 2 more bits i.e. 00101
3. decode N+1 = 00101 = 5
4. get N = 5 − 1 = 4 remaining bits for the complete code i.e. '0011'
5. encoded number = 2⁴ + 3 = 19

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

Пример кода

Кодирование

void eliasDeltaEncode(char* source, char* dest)
{
    IntReader intreader(source);
    BitWriter bitwriter(dest);
    while (intreader.hasLeft())
    {
        int num = intreader.getInt();
        int len = 0;
        int lengthOfLen = 0;

        len = 1 + floor(log2(num));  // calculate 1+floor(log2(num))
        lengthOfLen = floor(log2(len)); // calculate 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())     // potentially dangerous with malformed files.
            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);            // write out the value
    }
    bitreader.close();
    intwriter.close();
}

Обобщения

Дельта-кодирование Элиаса не кодирует ноль или отрицательные целые числа. Один из способов кодирования всех неотрицательных целых чисел — добавить 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]