Введение

Универсальное кодирование положительных целых чисел

Кодирование Элайаса ω или кодирование Элайаса омега — это универсальный код для кодирования положительных целых чисел, разработанный Питером Элайасом. Подобно гамма-кодированию и дельта-кодированию Элайаса, оно работает путем добавления к положительному целому числу представления его порядка величины в универсальном коде. Однако, в отличие от этих двух других кодов, кодирование Элайаса омега рекурсивно кодирует этот префикс; таким образом, они иногда известны как рекурсивные коды Элайаса. Омега-кодирование используется в приложениях, где наибольшее кодируемое значение неизвестно заранее, или для сжатия данных, в которых малые значения встречаются гораздо чаще, чем большие. Для кодирования положительного целого числа N:
Поместите "0" в конец кода. Если N = 1, остановитесь; кодирование завершено. Добавьте в начало кода двоичное представление N. Это будет как минимум два бита, первый из которых равен 1. Пусть N станет равным количеству только что добавленных битов минус один. Вернитесь к шагу 2, чтобы добавить кодирование нового N.

Для декодирования положительного целого числа, закодированного кодированием Элайаса омега:
Начните с переменной 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 гугол (10100) – это 11 1000 101001100 (15-битный заголовок длины), за которым следует 333-битное двоичное представление 1 гугол, равное 10010 01001001 10101101 00100101 10010100 11000011 01111100 11101011 00001011 00100111 10000100 11000100 11001110 00001011 11110011 10001010 11001110 01000000 10001110 00100001 00011010 01111100 10101010 10110010 01000011 00001000 10101000 00101110 10001111 00010000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 и завершающий 0, что в сумме составляет 349 бит. Гугол в сотой степени (1010000) – это 33 220-битное двоичное число. Его омега-кодирование имеет длину 33 243 бита: 11 1111 1000000111000100 (22 бита), за которым следуют 33 220 битов значения и завершающий 0. При дельта-кодировании Элиаса то же число имеет длину 33 250 бит: 000000000000000 1000000111000100 (31 бит), за которым следуют 33 219 битов значения. Омега-кодирование и дельта-кодирование соответственно на 0,07% и 0,09% длиннее, чем обычное 33 220-битное двоичное представление числа.

Длина кода

Для кодирования положительного целого числа N, количество необходимых битов, B(N), определяется рекурсивно следующим образом: то есть, длина кода Элиаса омега для целого числа равна где число слагаемых в сумме ограничено сверху двоичным итерированным логарифмом. Точнее, пусть для некоторого , и длина кода равна . Поскольку , то итерированный логарифм растет медленнее, чем любая функция для любого фиксированного , асимптотическая скорость роста равна , где суммирование прекращается, когда очередной член становится меньше единицы.

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

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

Обобщения

Кодирование Elias omega не кодирует нуль или отрицательные целые числа. Один из способов кодирования всех неотрицательных целых чисел — добавить 1 перед кодированием и затем вычесть 1 после декодирования, или использовать очень похожее кодирование Левенштейна. Один из способов кодирования всех целых чисел — установить взаимно однозначное соответствие, отображающее все целые числа (0, 1, 1, 2, 2, 3, 3, ...) на строго положительные целые числа (1, 2, 3, 4, 5, 6, 7, ...) перед кодированием.