Омега-код Элиаса — это универсальный код для кодирования положительных целых чисел, разработанный Питером Элиасом.
Так же, как гамма- и дельта-код Элиаса, он приписывает к началу целого числа порядок его величины в универсальном коде. Однако, в отличие от двух других указанных кодов, омега-код рекурсивно кодирует префикс, именно поэтому он также известен, как рекурсивный код Элиаса.
Чтобы закодировать число:
- Переписать группу нолей в конец представления.
- Если число, которое требуется закодировать, — единица, стоп; если нет, добавить двоичное представление числа в качестве группы в начало представления.
- Повторить предыдущий шаг, с количеством только что записанных цифр(бит), минус один, как с новым числом, которое следует закодировать.
Первые несколько кодов показаны ниже. Также дано так называемое предполагаемое распределение, описывающее распределение значений, для которых это кодирование выдаёт в результате код минимального размера (см.: универсальный код).
Начало кодирования:
Число |
Кодирование |
Предполагаемая вероятность
|
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 приобретает значение группы, интерпретируемой как двоичное число.
Омега-кодирование используется в приложениях, где самое большое кодируемое значение неизвестно заранее, или для сжатия данных, в которых маленькие значения встречаются намного чаще, чем большие.
См. также
Литература
Партнерские ресурсы |
---|
Криптовалюты |
|
---|
Магазины |
|
---|
Хостинг |
|
---|
Разное |
- Викиум - Онлайн-тренажер для мозга
- Like Центр - Центр поддержки и развития предпринимательства.
- Gamersbay - лучший магазин по бустингу для World of Warcraft.
- Ноотропы OmniMind N°1 - Усиливает мозговую активность. Повышает мотивацию. Улучшает память.
- Санкт-Петербургская школа телевидения - это федеральная сеть образовательных центров, которая имеет филиалы в 37 городах России.
- Lingualeo.com — интерактивный онлайн-сервис для изучения и практики английского языка в увлекательной игровой форме.
- Junyschool (Джунискул) – международная школа программирования и дизайна для детей и подростков от 5 до 17 лет, где ученики осваивают компьютерную грамотность, развивают алгоритмическое и креативное мышление, изучают основы программирования и компьютерной графики, создают собственные проекты: игры, сайты, программы, приложения, анимации, 3D-модели, монтируют видео.
- Умназия - Интерактивные онлайн-курсы и тренажеры для развития мышления детей 6-13 лет
- SkillBox - это один из лидеров российского рынка онлайн-образования. Среди партнеров Skillbox ведущий разработчик сервисного дизайна AIC, медиа-компания Yoola, первое и самое крупное русскоязычное аналитическое агентство Tagline, онлайн-школа дизайна и иллюстрации Bang! Bang! Education, оператор PR-рынка PACO, студия рисования Draw&Go, агентство performance-маркетинга Ingate, scrum-студия Sibirix, имидж-лаборатория Персона.
- «Нетология» — это университет по подготовке и дополнительному обучению специалистов в области интернет-маркетинга, управления проектами и продуктами, дизайна, Data Science и разработки. В рамках Нетологии студенты получают ценные теоретические знания от лучших экспертов Рунета, выполняют практические задания на отработку полученных навыков, общаются с экспертами и единомышленниками. Познакомиться со всеми продуктами подробнее можно на сайте https://netology.ru, линейка курсов и профессий постоянно обновляется.
- StudyBay Brazil – это онлайн биржа для португалоговорящих студентов и авторов! Студент получает уникальную работу любого уровня сложности и больше свободного времени, в то время как у автора появляется дополнительный заработок и бесценный опыт.
- Автор24 — самая большая в России площадка по написанию учебных работ: контрольные и курсовые работы, дипломы, рефераты, решение задач, отчеты по практике, а так же любой другой вид работы. Сервис сотрудничает с более 70 000 авторов. Более 1 000 000 работ уже выполнено.
- StudyBay – это онлайн биржа для англоязычных студентов и авторов! Студент получает уникальную работу любого уровня сложности и больше свободного времени, в то время как у автора появляется дополнительный заработок и бесценный опыт.
|
---|