WikiSort.ru - Не сортированное

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

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

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

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

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

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

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

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

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

См. также

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

Литература

• Elias, Peter (March 1975). “Universal codeword sets and representations of the integers”. IEEE Transactions on Information Theory. 21 (2): 194—203. DOI:10.1109/tit.1975.1055349.