Омега-код Элиаса: различия между версиями

Материал из in.wiki
Перейти к навигации Перейти к поиску
w>U-bot
(более не распознаётся как изолированная статья, Replaced: {{изолированная статья}} → с помощью AWB)
м (18 версий импортировано: Импорт из Википедии)
 
(не показано 11 промежуточных версий 8 участников)
Строка 1: Строка 1:
−
'''Омега-код Элиаса''' — это универсальный код для кодирования положительных целых чисел, разработанный Питером Элиасом.
+
'''Омега-код Элиаса''' — это [[универсальный код]] для кодирования положительных целых чисел, разработанный Питером Элиасом.
  
−
Так же как [[гамма-код Элиаса]] и [[дельта-код Элиаса]], он работает на приписывании к началу целого числа представления его порядка величины в универсальном коде. Однако в отличие от тех двух кодов, омега-код Элиаса рекурсивно кодирует приписываемое в начало, именно поэтому он также известен, как Рекурсивный код Элиаса.
+
Так же, как [[гамма-код Элиаса|гамма-]] и [[дельта-код Элиаса]], он приписывает к началу целого числа порядок его величины в универсальном коде. Однако, в отличие от двух других указанных кодов, омега-код рекурсивно кодирует префикс, именно поэтому он также известен, как '''рекурсивный код Элиаса'''.
  
 
Чтобы закодировать число:
 
Чтобы закодировать число:
−
# Перепишите группу нолей в конец представления.
+
# Переписать группу нолей в конец представления.
−
# Если число, которое требуется закодировать, — единица, остановитесь; если нет, добавьте двоичное представление числа в качестве группы в начало представления.
+
# Если число, которое требуется закодировать, — единица, стоп; если нет, добавить двоичное представление числа в качестве группы в начало представления.
−
# Повторите предыдущий шаг, с числом только что написанных цифр, минус одго, как с новым числом, которое следует закодировать.
+
# Повторить предыдущий шаг, с количеством только что записанных цифр(бит), минус один, как с новым числом, которое следует закодировать.
  
−
Первые несколько кодов показаны ниже. Включая так называемое предполагаемое распределение, описывающее распределение значений, для которых это кодирование выдает в результате код минимального размера (см.: [[универсальный код]]).
+
Первые несколько кодов показаны ниже. Также дано так называемое предполагаемое распределение, описывающее распределение значений, для которых это кодирование выдаёт в результате код минимального размера (см.: [[универсальный код]]).
  
 
Начало кодирования:
 
Начало кодирования:
−
<source lang="html4strict">
+
{| class="standard" style="text-align:right"
−
Значение Код         Предполагаемое распределение
+
! Число || Кодирование || Предполагаемая<br />вероятность
−
1         0         1/2
+
|-
−
2         10 0         1/8
+
| 1 || 0 || 1/2
−
3         11 0         1/8
+
|-
−
4         10 100 0 1/64
+
| 2 || 10 0 || 1/8
−
5         10 101 0 1/64
+
|-
−
6         10 110 0 1/64
+
| 3 || 11 0 || 1/8
−
7         10 111 0 1/64
+
|-
−
8         11 1000 0 1/128
+
| 4 || 10 100 0 || 1/64
−
9         11 1001 0 1/128
+
|-
−
10         11 1010 0 1/128
+
| 5 || 10 101 0 || 1/64
−
11         11 1011 0 1/128
+
|-
−
12         11 1100 0 1/128
+
| 6 || 10 110 0 || 1/64
−
13         11 1101 0 1/128
+
|-
−
14         11 1110 0 1/128
+
| 7 || 10 111 0 || 1/64
−
15         11 1111 0 1/128
+
|-
−
16         10 100 10000 0 1/2048
+
| 8 || 11 1000 0 || 1/128
−
17         10 100 10001 0 1/2048
+
|-
−
…
+
| 9 || 11 1001 0 || 1/128
−
</source>
+
|-
 +
| 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, установленной в значение 1.
 
# Считать первую «группу», следующую за остальными N разрядами, которая будет состоять либо из «0», либо из «1». Если она состоит из «0», это значит, что значение целого числа равно 1; если она начинается с «1», тогда N получает значение группы, которое интерпретируется как двоичное число.
 
# Считать первую «группу», следующую за остальными N разрядами, которая будет состоять либо из «0», либо из «1». Если она состоит из «0», это значит, что значение целого числа равно 1; если она начинается с «1», тогда N получает значение группы, которое интерпретируется как двоичное число.
−
# Считывать каждую следующую группу; она будет состоять либо из «0», либо из «1», следующих за остальными N разрядами. Если группа равна «0», это значит, что значение целого числа равно N; если она начинается с «1», то N приобреатет значение группы, интерпретируемой как двоичное число.
+
# Считывать каждую следующую группу; она будет состоять либо из «0», либо из «1», следующих за остальными N разрядами. Если группа равна «0», это значит, что значение целого числа равно N; если она начинается с «1», то N приобретает значение группы, интерпретируемой как двоичное число.
  
 
Омега-кодирование используется в приложениях, где самое большое кодируемое значение неизвестно заранее, или для сжатия данных, в которых маленькие значения встречаются намного чаще, чем большие.
 
Омега-кодирование используется в приложениях, где самое большое кодируемое значение неизвестно заранее, или для сжатия данных, в которых маленькие значения встречаются намного чаще, чем большие.
Строка 44: Строка 63:
 
* [[Дельта-код Элиаса]]
 
* [[Дельта-код Элиаса]]
  
 +
== Литература ==
 +
* {{статья |author-first=Peter |author-last=Elias |заглавие=Universal codeword sets and representations of the integers |издание={{Нп3|IEEE Transactions on Information Theory}} |том=21 |номер=2 |страницы=194—203 |ссылка=http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=1055349 |doi=10.1109/tit.1975.1055349 |язык=en |тип=journal |месяц=3 |год=1975}}
 
[[Категория:Алгоритмы сжатия без потерь]]
 
[[Категория:Алгоритмы сжатия без потерь]]
−
 
−
[[en:Elias_omega_coding]]
 
−
[[ja:オメガ符号]]
 
−
[[ko:엘리어스 오메가 부호]]
 

Текущая версия от 00:51, 20 августа 2025

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

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

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

  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
…

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

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

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

См. также[править | править код]

Литература[править | править код]

Источник — https://in.wiki/w/index.php?title=Омега-код_Элиаса&oldid=1574018