- Дельта-код Элиаса
-
Дельта-код Элиаса — это универсальный код для кодирования положительных целых чисел, разработанный Питером Элиасом.
Содержание
Кодирование
Алгоритм кодирования числа N:
- Сосчитать
— количество значащих битов в двоичном представлении числа
.
- Сосчитать
— количество значащих битов в двоичном представлении числа
.
- Записать
нулей и одну единицу.
- Дописать
—
младших битов двоичного представления числа
без старшей единицы (
).
- Дописать
—
младших битов двоичного представления числа
без старшей единицы (
).
Иначе этот алгоритм можно описать так:
- Сосчитать
— количество значащих битов в двоичном представлении числа
.
- Закодировать
с помощью гамма-кода Элиаса (γ(L)).
- Дописать двоичное представление числа
без старшей единицы.
То есть и в дельта-, и в гамма-коде Элиаса число кодируется в виде экспоненты
(разрядности числа — количества значащих битов) и мантиссы
(собственно значащих битов), но в гамма-коде экспонента записывается в унарном виде, а в дельта-коде к ней ещё раз применяется гамма-кодирование.
Пример кодирования числа 10:
- В двоичном представлении числа
4 значащих бита (
).
- В двоичном представлении числа
3 значащих бита (
).
- Записываем
нуля и одну единицу →
001
. - Дописывем биты числа
без старшей единицы →
00
. - Дописывем биты числа
без старшей единицы →
010
. - Результат —
00100010
.
Результаты кодирования первых 17 чисел (для сравнения показан также гамма-код):
N L M Дельта-код Длина,
битПредполагаемая
вероятностьГамма-код Длина,
битγ(L) 1 1 1 1 1 1/2 1 1 2 2 2 01 0 0 4 1/16 01 0 3 3 2 2 01 0 1 4 1/16 01 1 3 4 3 2 01 1 00 5 1/32 001 00 5 5 3 2 01 1 01 5 1/32 001 01 5 6 3 2 01 1 10 5 1/32 001 10 5 7 3 2 01 1 11 5 1/32 001 11 5 8 4 3 001 00 000 8 1/256 0001 000 7 9 4 3 001 00 001 8 1/256 0001 001 7 10 4 3 001 00 010 8 1/256 0001 010 7 11 4 3 001 00 011 8 1/256 0001 011 7 12 4 3 001 00 100 8 1/256 0001 100 7 13 4 3 001 00 101 8 1/256 0001 101 7 14 4 3 001 00 110 8 1/256 0001 110 7 15 4 3 001 00 111 8 1/256 0001 111 7 16 5 3 001 01 0000 9 1/512 00001 0000 9 17 5 3 001 01 0001 9 1/512 00001 0001 9 С помощью дополнительной обработки исходных значений дельта-код можно использовать также для кодирования нулевых и отрицательных целых чисел (см.: Гамма-код Элиаса#Обобщение).
Декодирование
Алгоритм декодирования числа из дельта-кода Элиаса:
- Сосчитать
— количество нулей во входном потоке до первой единицы.
- За единицей следуют
младших битов числа
, прочитать их и добавить к результату значение
. Если биты
во входном потоке записаны от старших к младшим, то первую единицу после ведущей серии нулей можно читать как часть двоичного представления числа
, в этом случае добавлять
отдельным шагом нет необходимости.
- Следом идут
младших битов числа
, прочитать их и добавить к результату значение
.
Пример декодирования последовательности битов 001010001:
- Прочитать из потока 001 и определить, что в начале 2 ведущих нуля (
).
- Прочитать из потока следующие
бита → 01; это даёт
.
- Прочитать из потока следующие
бита → 0001; это даёт
.
Эффективность
Можно видеть, что для чисел 2, 3, 8…15 дельта-код длиннее гамма-кода, для чисел 1, 4…7, 16…31 длина дельта-кода совпадает с длиной гамма-кода, для всех остальных чисел дельта-код короче гамма-кода. Соответственно, дельта-код тем менее выгоднее гамма-кода, чем неравномернее распределение вероятностей кодируемых чисел и чем более вероятны их значения при приближении к нулю.
См. также
Литература
- Д. Ватолин, А. Ратушняк, М. Смирнов, В. Юкин. Раздел 1. Методы сжатия без потерь. Глава 1. Кодирование источников данных без памяти. Разделение мантисс и экспонент // Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео. — М.: Диалог-МИФИ, 2002. — С. 23—24. — 384 с. — ISBN 5-86404-170-x
Категория:- Алгоритмы сжатия без потерь
- Сосчитать
Wikimedia Foundation. 2010.