Дельта-код Элиаса: различия между версиями
Перейти к навигации
Перейти к поиску
w>AVB м (переименовал «Дельта код Элиаса» в «Дельта-код Элиаса»: орфография) |
w>AVB (викификация, оформление, орфография, стилевые правки) |
||
| Строка 1: | Строка 1: | ||
{{изолированная статья|сирота1}} | {{изолированная статья|сирота1}} | ||
| − | '''Дельта-код Элиаса ''' | + | '''Дельта-код Элиаса ''' — это [[универсальный код]] для кодирования положительных целых чисел, разработанный Питером Элиасом. |
Для того, чтобы закодировать число: | Для того, чтобы закодировать число: | ||
| − | # | + | # Записать его в двоичном виде. |
| − | # | + | # Сосчитать биты и записать количество битов в двоичном виде (Х). |
| − | # | + | # Использовать двоичное значение, записанное в шаге 1 снова, удалить стоящий впереди бит и записать оставшиеся биты (Y). |
| − | # | + | # Присоединить второе двоичное значение (Y) к первому (X). |
| − | # | + | # Сосчитать биты, записанные в шаге 2 (X), вычесть 1 из этого числа и добавить в начало много нулей. |
Аналогичным образом этот процесс можно описать так: | Аналогичным образом этот процесс можно описать так: | ||
| − | # | + | # Разделить целое число на самую большую степень 2, которую оно содержит (2<sup>N'</sup>), и оставшиеся N' двоичных цифр целого числа. |
| − | # | + | # Закодировать N = N' + 1 с помощью гамма-кода Элиаса. |
| − | # | + | # Добавить оставшиеся N' двоичных цифр к представлению N. |
| − | |||
Начало кодирования: | Начало кодирования: | ||
| Строка 35: | Строка 34: | ||
16 = 24 + 0 => N' = 4, N = 5 => 001010000 1/512 | 16 = 24 + 0 => N' = 4, N = 5 => 001010000 1/512 | ||
17 = 24 + 1 => N' = 4, N = 5 => 001010001 " | 17 = 24 + 1 => N' = 4, N = 5 => 001010001 " | ||
| − | |||
… | … | ||
</source> | </source> | ||
Чтобы декодировать число из Дельта-кода Элиаса: | Чтобы декодировать число из Дельта-кода Элиаса: | ||
| − | # | + | # Прочитать и сосчитать количество нулей из потока, пока не встретится 1. Пусть L — количество нулей. |
| − | # Учитывая, что единица, которая была | + | # Учитывая, что единица, которая была достигнута — это первая цифра целого числа, значение которого 2<sup>L</sup>, прочитать оставшиеся L цифр этого целого числа. Пусть N — прочитанное число. |
| − | # | + | # Поместить единицу на первое место конечного вывода, который представляет собой значение 2<sup>N</sup>-1. Прочитать и добавить следующие N-1 цифр. |
| − | |||
Пример: | Пример: | ||
001010001 | 001010001 | ||
| − | # 2 ведущих ноля в | + | # 2 ведущих ноля в 001. |
# вычитайте 2 или более битов, т.e. 00101. | # вычитайте 2 или более битов, т.e. 00101. | ||
# декодируйте N = 00101 = 5. | # декодируйте N = 00101 = 5. | ||
| − | # получим N' = | + | # получим N' = 5 — 1 = 4 оставшихся бита для полного кода, т.e. '0001'. |
# закодированное число = 24 + 1 = 17. | # закодированное число = 24 + 1 = 17. | ||
| − | Этот код может быть также | + | Этот код может быть также применён к целым числам с нулевым или отрицательным значением (см.: [[гамма-код Элиаса]]). |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
== См. также == | == См. также == | ||
Версия от 18:27, 12 мая 2009
 |
Параметр text не задан |
Ошибка Lua в Модуль:Autosorting на строке 85: attempt to index field 'wikibase' (a nil value).Ошибка Lua в Модуль:Autosorting на строке 85: attempt to index field 'wikibase' (a nil value).
Дельта-код Элиаса — это универсальный код для кодирования положительных целых чисел, разработанный Питером Элиасом.
Для того, чтобы закодировать число:
- Записать его в двоичном виде.
- Сосчитать биты и записать количество битов в двоичном виде (Х).
- Использовать двоичное значение, записанное в шаге 1 снова, удалить стоящий впереди бит и записать оставшиеся биты (Y).
- Присоединить второе двоичное значение (Y) к первому (X).
- Сосчитать биты, записанные в шаге 2 (X), вычесть 1 из этого числа и добавить в начало много нулей.
Аналогичным образом этот процесс можно описать так:
- Разделить целое число на самую большую степень 2, которую оно содержит (2N'), и оставшиеся N' двоичных цифр целого числа.
- Закодировать N = N' + 1 с помощью гамма-кода Элиаса.
- Добавить оставшиеся N' двоичных цифр к представлению N.
Начало кодирования:
Предполагаемые вероятности
1 = 20 => N' = 0, N = 1 => 1 1/2
2 = 21 + 0 => N' = 1, N = 2 => 0100 1/16
3 = 21 + 1 => N' = 1, N = 2 => 0101 "
4 = 2² + 0 => N' = 2, N = 3 => 01100 1/32
5 = 2² + 1 => N' = 2, N = 3 => 01101 "
6 = 2² + 2 => N' = 2, N = 3 => 01110 "
7 = 2² + 3 => N' = 2, N = 3 => 01111 "
8 = 2³ + 0 => N' = 3, N = 4 => 00100000 1/256
9 = 2³ + 1 => N' = 3, N = 4 => 00100001 "
10 = 2³ + 2 => N' = 3, N = 4 => 00100010 "
11 = 2³ + 3 => N' = 3, N = 4 => 00100011 "
12 = 2³ + 4 => N' = 3, N = 4 => 00100100 "
13 = 2³ + 5 => N' = 3, N = 4 => 00100101 "
14 = 2³ + 6 => N' = 3, N = 4 => 00100110 "
15 = 2³ + 7 => N' = 3, N = 4 => 00100111 "
16 = 24 + 0 => N' = 4, N = 5 => 001010000 1/512
17 = 24 + 1 => N' = 4, N = 5 => 001010001 "
…
Чтобы декодировать число из Дельта-кода Элиаса:
- Прочитать и сосчитать количество нулей из потока, пока не встретится 1. Пусть L — количество нулей.
- Учитывая, что единица, которая была достигнута — это первая цифра целого числа, значение которого 2L, прочитать оставшиеся L цифр этого целого числа. Пусть N — прочитанное число.
- Поместить единицу на первое место конечного вывода, который представляет собой значение 2N-1. Прочитать и добавить следующие N-1 цифр.
Пример: 001010001
- 2 ведущих ноля в 001.
- вычитайте 2 или более битов, т.e. 00101.
- декодируйте N = 00101 = 5.
- получим N' = 5 — 1 = 4 оставшихся бита для полного кода, т.e. '0001'.
- закодированное число = 24 + 1 = 17.
Этот код может быть также применён к целым числам с нулевым или отрицательным значением (см.: гамма-код Элиаса).