Кодирование Элиаса Омеги - Elias omega coding

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

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

Чтобы закодировать номер 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 гугол, 10¹⁰⁰, это 11 1000 101001100 (заголовок длины 15 бит), за которым следует 333-битное двоичное представление 1 гугола, что составляет 10010 01001001 10101101 00100101 10010100 11000011 01111100 11101011 00001011 00100111 10000100 11000100 11001110 00001011 11110011 10001010 11001110 0110000000011 10001010011 10001010 11001110 0110000000011 01000011 00001000 10101000 00101110 10001111 00010000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 и завершающий 0, всего 349 бит.

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

Пример кода