Элиас омега-кодирование

Кодирование Элиаса ω или омега-кодирование Элиаса — это универсальный код , кодирующий положительные целые числа, разработанный Питером Элиасом . Подобно гамма-кодированию Элиаса и дельта-кодированию Элиаса , оно работает путем добавления к положительному целому числу префикса с представлением его порядка величины в универсальном коде. Однако, в отличие от этих двух других кодов, Элиас омега рекурсивно кодирует этот префикс; таким образом, их иногда называют рекурсивными кодами Элиаса .

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

Чтобы закодировать положительное целое число N :

Поставьте «0» в конце кода.
Если N = 1, остановиться; кодирование завершено.
Добавьте двоичное представление N в начало кода. Это будет как минимум два бита, первый бит из которых равен 1.
Пусть N равно количеству только что добавленных бит минус один.
чтобы добавить кодировку нового N. Вернитесь к шагу 2 ,

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

Начните с переменной N , которой присвоено значение 1.
Если следующий бит равен «0», остановитесь. Декодированное число N. —
Если следующий бит равен «1», прочитайте его плюс еще N бит и используйте это двоичное число в качестве нового значения N . Вернитесь к шагу 2.

Примеры

Коды Омега можно рассматривать как несколько «групп». Группа — это либо один бит 0, который завершает код, либо два или более бита, начинающиеся с 1, за которыми следует другая группа.

Первые несколько кодов показаны ниже. Включено так называемое подразумеваемое распределение , описывающее распределение значений, для которых это кодирование дает код минимального размера; см . в разделе «Связь универсальных кодов с практическим сжатием» Подробности .

Ценить	Код	Подразумеваемая вероятность
1	0	1/2
2	10 0	1/8
3	11 0	1/8
4	10 100 0	1/64
5	10 101 0	1/64
6	10 110 0	1/64
7	10 111 0	1/64
8	11 1000 0	1/128
9	11 1001 0	1/128
10	11 1010 0	1/128
11	11 1011 0	1/128
12	11 1100 0	1/128
13	11 1101 0	1/128
14	11 1110 0	1/128
15	11 1111 0	1/128
16	10 100 10000 0	1/2048
17	10 100 10001 0	1/2048
...
100	10 110 1100100 0	1/8192
1000	11 1001 1111101000 0	1/131,072
10,000	11 1101 10011100010000 0	1/2,097,152
100,000	10 100 10000 11000011010100000 0	1/268,435,456
1,000,000	10 100 10011 11110100001001000000 0	1/2,147,483,648

Кодировка для 1 гугола , 10 ¹⁰⁰, равно 11 1000 101001100 (длина заголовка 15 бит), за которым следует 333-битное двоичное представление 1 гугола, то есть 10010 01001001 10101101 00100101 10010100 11000011 01111100 11101011 000 01011 00100111 10000100 11000100 11001110 00001011 11110011 10001010 11001110 01000000 10001110 00100001 00011010 01111100 1 0101010 10110010 01000011 00001000 10101000 00101110 10001111 00010000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000 000 00000000 00000000 00000000 00000000 и завершающий 0, всего 349 бит.

Гугол в сотой степени (10 ¹⁰⁰⁰⁰) — 33220-битное двоичное число. Его омега-кодирование имеет длину 33 243 бита: 11 1111 1000000111000100 (22 бита), за которым следуют 33 220 бит значения и завершающий 0. При дельта-кодировании Элиаса то же число имеет длину 33 250 бит: 00000000000000 100000011100 0100 (31 бит), за которым следует 33 219 бит значения. Кодирование омега и дельта соответственно на 0,07% и 0,09% длиннее обычного 33220-битного двоичного представления числа.

Длина кода

Для кодирования положительного целого числа $N$ необходимое количество битов $B (N)$ определяется рекурсивно: ${\begin{aligned}B(0)&=0\,,\\B(N)&=1+\lfloor \log _{2}(N)\rfloor +B(\lfloor \log _{2}(N)\rfloor )\,.\end{aligned}}$ То есть длина омега-кода Элиаса для целого числа $N$ является $1+(1+\lfloor \log _{2}N\rfloor {})+(1+\lfloor \log _{2}\lfloor \log _{2}N\rfloor {}\rfloor {})+\cdots$ где количество членов суммы ограничено сверху двоичным повторным логарифмом . Если быть точным, пусть $f(x)=\lfloor \log _{2}x\rfloor {}$ . У нас есть $N>f(N)>f(f(N))>\cdots >f^{k}(N)=1$ для некоторых $k$ , а длина кода равна $(k+1)+f(N)+f^{2}(N)+\dots +f^{k}(N)$ . С $f(x)\leq \log _{2}x$ , у нас есть $k\leq \log _{2}^{*}(N)$ .

Поскольку повторный логарифм растет медленнее всех $\log _{2}^{n}N$ для любого фиксированного $n$ , асимптотическая скорость роста равна $\Theta (\log _{2}N+\log _{2}^{2}N+\cdots )$ , где сумма прекращается, когда она падает ниже единицы.

Асимптотическая оптимальность

Омега-кодирование Элиаса является асимптотически оптимальным префиксным кодом. ^[1]

Эскиз доказательства. Префиксный код должен удовлетворять неравенству Крафта . Для омега-кодирования Элиаса неравенство Крафта гласит: $\sum _{n=1}^{\infty }{\frac {1}{2^{O(1)+\log _{2}n+\log _{2}\log _{2}n+\cdots }}}\leq 1$ Теперь суммирование асимптотически совпадает с интегралом, что дает нам $\int _{1}^{\infty }{\frac {dx}{x\times \ln x\times \ln \ln x\cdots }}\leq O(1)$ Если знаменатель в какой-то момент заканчивается $\ln ^{k}x$ , то интеграл расходится как $\ln ^{k+1}\infty$ . Однако если знаменатель в какой-то момент заканчивается $(\ln ^{k}x)^{1+\epsilon }$ , то интеграл сходится как ${\frac {1}{(\ln ^{k}\infty )^{\epsilon }}}$ . Омега-код Элиаса находится на грани между расхождением и сближением.

Пример кода

Кодирование

void eliasOmegaEncode(char* source, char* dest)
{
    IntReader intreader(source);
    BitWriter bitwriter(dest);
    while (intreader.hasLeft())
    {
        int num = intreader.getInt();
        BitStack bits;
        while (num > 1) {
            int len = 0;
            for (int temp = num; temp > 0; temp >>= 1)  // calculate 1+floor(log2(num))
                len++;
            for (int i = 0; i < len; i++)
                bits.pushBit((num >> i) & 1);
            num = len - 1;
        }
        while (bits.length() > 0)
            bitwriter.putBit(bits.popBit());
        bitwriter.putBit(false);                        // write one zero
    }
    bitwriter.close();
    intreader.close();
}

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

void eliasOmegaDecode(char* source, char* dest) {
    BitReader bitreader(source);
    IntWriter intwriter(dest);
    while (bitreader.hasLeft())
    {
        int num = 1;
        while (bitreader.inputBit())     // potentially dangerous with malformed files.
        {
            int len = num;
            num = 1;
            for (int i = 0; i < len; ++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, ...) перед кодированием.

См. также

Ссылки

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

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

Элиас, Питер (март 1975 г.). «Универсальные наборы кодовых слов и представления целых чисел». Транзакции IEEE по теории информации . 21 (2): 194–203. дои : 10.1109/тит.1975.1055349 .
Фенвик, Питер (2003). «Универсальные коды». В Саюде, Халид (ред.). Справочник по сжатию без потерь . Нью-Йорк, штат Нью-Йорк, США: Academic Press . стр. 55–78. дои : 10.1016/B978-012620861-0/50004-8 . ISBN 978-0123907547 .

Внешние ссылки

Реализация на Python

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

[1]