Омега-код Элиаса

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

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

Чтобы закодировать число:

1. Перепишите группу нолей в конец представления.
2. Если число, которое требуется закодировать, — единица, остановитесь; если нет, добавьте двоичное представление числа в качестве группы в начало представления.
3. Повторите предыдущий шаг, с числом только что написанных цифр, минус одго, как с новым числом, которое следует закодировать.

Первые несколько кодов показаны ниже. Включая так называемое предполагаемое распределение, описывающее распределение значений, для которых это кодирование выдает в результате код минимального размера (см.: универсальный код).

Начало кодирования:

Значение	Код	        Предполагаемая вероятность
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
…

Алгоритм декодирования числа, представленного в омега-коде Элиаса:

# Начать с переменной N, установленной в значение 1.
# Считать первую «группу», следующую за остальными N разрядами, которая будет состоять либо из  «0», либо из «1». Если она состоит из «0», это значит, что значение целого числа равно 1; если она начинается с «1», тогда N получает значение группы, которое интерпретируется как двоичное число.
# Считывать каждую следующую группу; она будет состоять либо из «0», либо из «1», следующих за остальными N разрядами. Если группа равна «0», это значит, что значение целого числа равно N; если она начинается с «1», то N приобреатет значение группы, интерпретируемой как двоичное число.

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

См. также

• Гамма-код Элиаса
• Дельта-код Элиаса