Interested Article - Омега-код Элиаса
martine
- 2020-05-14
- 2
Омега-код Элиаса — это универсальный код для кодирования положительных целых чисел, разработанный Питером Элиасом.
Так же, как гамма- и дельта-код Элиаса , он приписывает к началу целого числа порядок его величины в универсальном коде. Однако, в отличие от двух других указанных кодов, омега-код рекурсивно кодирует префикс, именно поэтому он также известен, как рекурсивный код Элиаса .
Чтобы закодировать число:
- Переписать группу нолей в конец представления.
- Если число, которое требуется закодировать, — единица, стоп; если нет, добавить двоичное представление числа в качестве группы в начало представления.
- Повторить предыдущий шаг, с количеством только что записанных цифр(бит), минус один, как с новым числом, которое следует закодировать.
Первые несколько кодов показаны ниже. Также дано так называемое предполагаемое распределение, описывающее распределение значений, для которых это кодирование выдаёт в результате код минимального размера (см.: универсальный код ).
Начало кодирования:
| Число | Кодирование |
Предполагаемая
вероятность |
|---|---|---|
| 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 приобретает значение группы, интерпретируемой как двоичное число.
Омега-кодирование используется в приложениях, где самое большое кодируемое значение неизвестно заранее, или для сжатия данных, в которых маленькие значения встречаются намного чаще, чем большие.
См. также
Литература
- (англ.) // : journal. — 1975. — March ( vol. 21 , no. 2 ). — P. 194—203 . — doi : .
martine
- 2020-05-14
- 2