Изменения
← Новая страница: «'''Омега код Элиаса ''' — это универсальный код для кодирования положительных цел…»
'''Омега код Элиаса ''' — это универсальный код для кодирования положительных целых чисел, разработанный Питером Элиасом.
Так же как [[Гамма код Элиаса|Гамма код Элиаса]] и [[Дельта код Элиаса |Дельта код Элиаса]], он работает на приписывании к началу целого числа представления его порядка величины в универсальном коде. Однако в отличие от тех двух кодов, Омега код Элиаса рекурсивно кодирует приписываемое в начало, именно поэтому он также известен, как Рекурсивный код Элиаса.
Чтобы закодировать число:
# Перепишите группу нолей в конец представления.
# Если число, которое требуется закодировать, - единица, остановитесь; если нет, добавьте двоичное представление числа в качестве группы в начало представления.
# Повторите предыдущий шаг, с числом только что написанных цифр, минус одго, как с новым числом, которое следует закодировать.
Первые несколько кодов показаны ниже. Включая так называемое предполагаемое распределение, описывающее распределение значений, для которых это кодирование выдает в результате код минимального размера; чтобы узнать подробнее, смотри статью о Универсальном коде.
Начало кодирования:
<source lang="html4strict">
Значение Код Предполагаемое распределение
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
...
…
</source>
Чтобы декодировать число в Омега коде Элиаса:
# Начните с переменной N, установленной в значение 1.
# Считайте первую «группу», следующую за остальными N разрядами, которая будет состоять либо из «0», либо из «1». Если она состоит из «0», это значит, что значение целого числа равно 1; если она начинается с «1», тогда N получает значение группы, которое интерпретируется как двоичное число.
# Считывайте каждую следующую группу; она будет состоять либо из «0», либо из «1», следующих за остальными N разрядами. Если группа равна «0», это значит, что значение целого числа равно N; если она начинается с «1», то N приобреатет значение группы, интерпретируемой как двоичное число.
Омега кодирование используется в приложениях, где самое большое кодируемое значение неизвестно заранее, или для сжатия данных, в которых маленькие значения встречаются намного чаще, чем большие.
== Ссылки ==
Оригинал статьи на английском
{{cite web
| url = http://en.wikipedia.org/wiki/Elias_omega_coding
| title = Elias omega coding
}}
Так же как [[Гамма код Элиаса|Гамма код Элиаса]] и [[Дельта код Элиаса |Дельта код Элиаса]], он работает на приписывании к началу целого числа представления его порядка величины в универсальном коде. Однако в отличие от тех двух кодов, Омега код Элиаса рекурсивно кодирует приписываемое в начало, именно поэтому он также известен, как Рекурсивный код Элиаса.
Чтобы закодировать число:
# Перепишите группу нолей в конец представления.
# Если число, которое требуется закодировать, - единица, остановитесь; если нет, добавьте двоичное представление числа в качестве группы в начало представления.
# Повторите предыдущий шаг, с числом только что написанных цифр, минус одго, как с новым числом, которое следует закодировать.
Первые несколько кодов показаны ниже. Включая так называемое предполагаемое распределение, описывающее распределение значений, для которых это кодирование выдает в результате код минимального размера; чтобы узнать подробнее, смотри статью о Универсальном коде.
Начало кодирования:
<source lang="html4strict">
Значение Код Предполагаемое распределение
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
...
…
</source>
Чтобы декодировать число в Омега коде Элиаса:
# Начните с переменной N, установленной в значение 1.
# Считайте первую «группу», следующую за остальными N разрядами, которая будет состоять либо из «0», либо из «1». Если она состоит из «0», это значит, что значение целого числа равно 1; если она начинается с «1», тогда N получает значение группы, которое интерпретируется как двоичное число.
# Считывайте каждую следующую группу; она будет состоять либо из «0», либо из «1», следующих за остальными N разрядами. Если группа равна «0», это значит, что значение целого числа равно N; если она начинается с «1», то N приобреатет значение группы, интерпретируемой как двоичное число.
Омега кодирование используется в приложениях, где самое большое кодируемое значение неизвестно заранее, или для сжатия данных, в которых маленькие значения встречаются намного чаще, чем большие.
== Ссылки ==
Оригинал статьи на английском
{{cite web
| url = http://en.wikipedia.org/wiki/Elias_omega_coding
| title = Elias omega coding
}}