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

Материал из in.wiki
Перейти к навигации Перейти к поиску
w>AVB
(оформление списка таблицей)
Строка 11: Строка 11:
  
 
Начало кодирования:
 
Начало кодирования:
−
<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 приобреатет значение группы, интерпретируемой как двоичное число.
  

Версия от 22:20, 21 мая 2009

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

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

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

  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 приобреатет значение группы, интерпретируемой как двоичное число.

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

См. также

en:Elias_omega_coding ja:オメガ符号 ko:엘리어스 오메가 부호

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