WikiSort.ru - Не сортированное

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

Кодирование

Алгоритм кодирования числа N:

1. Сосчитать ${\displaystyle L}$  — количество значащих битов в двоичном представлении числа ${\displaystyle N}$ .
2. Сосчитать ${\displaystyle M}$  — количество значащих битов в двоичном представлении числа ${\displaystyle L}$ .
3. Записать ${\displaystyle M-1}$ нулей и одну единицу.
4. Дописать ${\displaystyle L_{2}}$  — ${\displaystyle M-1}$ младших битов двоичного представления числа ${\displaystyle L}$ без старшей единицы (${\displaystyle 2^{M-1}}$ ).
5. Дописать ${\displaystyle N_{2}}$  — ${\displaystyle L-1}$ младших битов двоичного представления числа ${\displaystyle N}$ без старшей единицы (${\displaystyle 2^{L-1}}$ ).

Иначе этот алгоритм можно описать так:

1. Сосчитать ${\displaystyle L}$  — количество значащих битов в двоичном представлении числа ${\displaystyle N}$ .
2. Закодировать ${\displaystyle L}$ с помощью гамма-кода Элиаса (γ(L)).
3. Дописать двоичное представление числа ${\displaystyle N}$ без старшей единицы.

То есть и в дельта-, и в гамма-коде Элиаса число кодируется в виде экспоненты ${\displaystyle L}$ (разрядности числа — количества значащих битов) и мантиссы ${\displaystyle N_{2}}$ (собственно значащих битов), но в гамма-коде экспонента записывается в унарном виде, а в дельта-коде к ней ещё раз применяется гамма-кодирование.

Пример кодирования числа 10:

1. В двоичном представлении числа ${\displaystyle N=10=1010_{2}}$ 4 значащих бита (${\displaystyle L=4}$ ).
2. В двоичном представлении числа ${\displaystyle L=4=100_{2}}$ 3 значащих бита (${\displaystyle M=3}$ ).
3. Записываем ${\displaystyle M-1=2}$ нуля и одну единицу → 001.
4. Дописывем биты числа ${\displaystyle L}$ без старшей единицы → 00.
5. Дописывем биты числа ${\displaystyle N}$ без старшей единицы → 010.
6. Результат — 00100010.

Результаты кодирования первых 17 чисел (для сравнения показан также гамма-код):

N		L		M	Дельта-код		Длина, бит	Предполагаемая вероятность	Гамма-код		Длина, бит
					γ(L)	${\displaystyle N_{2}}$			${\displaystyle L}$	${\displaystyle N_{2}}$
1	${\displaystyle 1_{2}}$	1	${\displaystyle 1_{2}}$	1	1		1	1/2	1		1
2	${\displaystyle 10_{2}}$	2	${\displaystyle 10_{2}}$	2	01 0	0	4	1/16	01	0	3
3	${\displaystyle 11_{2}}$	2	${\displaystyle 10_{2}}$	2	01 0	1	4	1/16	01	1	3
4	${\displaystyle 100_{2}}$	3	${\displaystyle 11_{2}}$	2	01 1	00	5	1/32	001	00	5
5	${\displaystyle 101_{2}}$	3	${\displaystyle 11_{2}}$	2	01 1	01	5	1/32	001	01	5
6	${\displaystyle 110_{2}}$	3	${\displaystyle 11_{2}}$	2	01 1	10	5	1/32	001	10	5
7	${\displaystyle 111_{2}}$	3	${\displaystyle 11_{2}}$	2	01 1	11	5	1/32	001	11	5
8	${\displaystyle 1000_{2}}$	4	${\displaystyle 100_{2}}$	3	001 00	000	8	1/256	0001	000	7
9	${\displaystyle 1001_{2}}$	4	${\displaystyle 100_{2}}$	3	001 00	001	8	1/256	0001	001	7
10	${\displaystyle 1010_{2}}$	4	${\displaystyle 100_{2}}$	3	001 00	010	8	1/256	0001	010	7
11	${\displaystyle 1011_{2}}$	4	${\displaystyle 100_{2}}$	3	001 00	011	8	1/256	0001	011	7
12	${\displaystyle 1100_{2}}$	4	${\displaystyle 100_{2}}$	3	001 00	100	8	1/256	0001	100	7
13	${\displaystyle 1101_{2}}$	4	${\displaystyle 100_{2}}$	3	001 00	101	8	1/256	0001	101	7
14	${\displaystyle 1110_{2}}$	4	${\displaystyle 100_{2}}$	3	001 00	110	8	1/256	0001	110	7
15	${\displaystyle 1111_{2}}$	4	${\displaystyle 100_{2}}$	3	001 00	111	8	1/256	0001	111	7
16	${\displaystyle 10000_{2}}$	5	${\displaystyle 101_{2}}$	3	001 01	0000	9	1/512	00001	0000	9
17	${\displaystyle 10001_{2}}$	5	${\displaystyle 101_{2}}$	3	001 01	0001	9	1/512	00001	0001	9

С помощью дополнительной обработки исходных значений дельта-код можно использовать также для кодирования нулевых и отрицательных целых чисел (см.: Гамма-код Элиаса#Обобщение).

Декодирование

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

1. Сосчитать ${\displaystyle M}$  — количество нулей во входном потоке до первой единицы.
2. За единицей следуют ${\displaystyle M}$ младших битов числа ${\displaystyle L}$ , прочитать их и добавить к результату значение ${\displaystyle 2^{M}}$ . Если биты ${\displaystyle L}$ во входном потоке записаны от старших к младшим, то первую единицу после ведущей серии нулей можно читать как часть двоичного представления числа ${\displaystyle L}$ , в этом случае добавлять ${\displaystyle 2^{M}}$ отдельным шагом нет необходимости.
3. Следом идут ${\displaystyle L-1}$ младших битов числа ${\displaystyle N}$ , прочитать их и добавить к результату значение ${\displaystyle 2^{L-1}}$ .

Пример декодирования последовательности битов 001010001:

1. Прочитать из потока 001 и определить, что в начале 2 ведущих нуля (${\displaystyle M=2}$ ).
2. Прочитать из потока следующие ${\displaystyle M=2}$ бита → 01; это даёт ${\displaystyle L=2^{M}+01_{2}=4+1=5}$ .
3. Прочитать из потока следующие ${\displaystyle L-1=4}$ бита → 0001; это даёт ${\displaystyle N=2^{L-1}+0001_{2}=16+1=17}$ .

Эффективность

Можно видеть, что для чисел 2, 3, 8…15 дельта-код длиннее гамма-кода, для чисел 1, 4…7, 16…31 длина дельта-кода совпадает с длиной гамма-кода, для всех остальных чисел дельта-код короче гамма-кода. Соответственно, дельта-код тем менее выгоднее гамма-кода, чем неравномернее распределение вероятностей кодируемых чисел и чем более вероятны их значения при приближении к нулю.

См. также

• Омега-код Элиаса

Литература

• Д. Ватолин, А. Ратушняк, М. Смирнов, В. Юкин. Раздел 1. Методы сжатия без потерь. Глава 1. Кодирование источников данных без памяти. Разделение мантисс и экспонент // Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео. — М.: Диалог-МИФИ, 2002. — С. 23—24. — 384 с. — ISBN 5-86404-170-x.
• Elias, Peter (March 1975). “Universal codeword sets and representations of the integers”. IEEE Transactions on Information Theory. 21 (2): 194—203. DOI:10.1109/tit.1975.1055349.