Гамма-, дельта- и омега-код Элиаса

Коды без памяти

Простейшими кодами, на основе которых может выполняться сжатие данных, являются коды без памяти (англ. code without memory). В коде без памяти каждый символ в кодируемом векторе данных заменяется кодовым словом из префиксного множества двоичных последовательностей или слов.

Примерами кодов без памяти являются кодирование Хаффмана и кодирование Шеннона — Фано.

Коды Хаффмана и Шеннона — Фано являются оптимальными, но все же имеют ряд недостатков. Во-первых, при кодировании методами Хаффмана или Шеннона используются вероятности появления символов алфавита в тексте. Т е для построения кода нам нужно обладать этой информацией. Для того, чтобы декодер мог расшифровать файл таблицу частот, которой пользовался кодер, следует записать в сжатый файл. Следовательно, длина сжатого сообщения увеличивается на длину таблицы частот, которая должна посылаться впереди данных, что может не оправдать сжатия. Во-вторых, необходимость наличия полной частотной статистики перед началом собственно кодирования требует двух проходов по сообщению: одного для построения модели сообщения (таблицы частот и Н-дерева), другого для собственно кодирования. Коды Элиаса решают эту проблему, при их построении не используется вероятности появления символов.

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

Разделение мантисс и экспонент

Английское название метода — Separate Exponents and Mantissas (SEM).

Цель — сжатие потока $R$-битовых элементов.

Основная идея состоит в том, чтобы отдельно описывать порядок значения элемента ("экспоненту" $E_i$) и отдельно — значащие цифры значения ("мантиссу" $M_i$).

Значащие цифры начинаются со старшей ненулевой цифры: например, в числе $000001101_2$ = $1\times2^0+0\times2^1+1\times2^2+1\times2^3+0\times2^4+0\times... = 13$ это последние $4$ цифры. Порядок числа определяется позицией старшей ненулевой цифры в записи числа. Как и при обычной записи в десятичной системе, он равен числу цифр в записи числа без предшествующих незначащих нулей. В данном примере порядок равен четырем.

Методы данной группы являются трансформирующими и поточными, то есть могут применяться даже в том случае, когда объем входных данных заранее не известен. В общем случае скорость работы компрессора (содержащего прямое, "сжимающее" преобразование) равна скорости декомпрессора (реализующего обратное, "разжимающее" преобразование) и зависит только от объема исходных данных. Памяти потребуется всего несколько байт.

В самом простом случае под запись экспонент и мантисс отводится фиксированное число бит: $E$ и $M$. Причем $E \geqslant 1$, $M \geqslant 1$, $E + M = R$, где $R$ — число битов в записи исходного числа.

Этот первый из четырех вариантов метода условно обозначим

1. Fixed $+$ Fixed (Фиксированная длина экспоненты — Фиксированная длина мантиссы), а остальные три:

2. Fixed $+$ Variable (Фиксированная длина экспоненты — Переменная длина мантиссы),

3. Variable $+$ Variable (Переменная длина экспоненты — Переменная длина мантиссы) и

4. Variable $+$ Fixed (Переменная длина экспоненты — Фиксированная длина мантиссы).

Есть несколько путей еще большего увеличения степени сжатия. Например, применение хорошо исследованных схем кодирования (Элиаса, Раиса, Голомба, Фибоначчи).

Коды переменной длины (Variable + Variable)

Определение:

Унарное представление числа $n$ (англ. unary code) — $n$ подряд идущих единиц, заканчивающихся контрольным нулем (иногда наоборот: $n$ нулей, за которыми следует контрольная единица). Более наглядно унарные коды можно представить в виде двоичного дерева, которое устроено следующим образом: каждому ребру, ведущему из вершины к правому ребенку, соответствует единица, иначе ноль, причем левый ребенок уже не имеет детей. Например, если нужно закодировать число m, нужно m раз пройти по правым вершинам и затем остановиться на левой.

Например, унарный код нуля — $0$, единицы — $10$, двойки — $110$ и т. д.

Определение:

Универсальный код (англ. universal code) — префиксный код, который преобразует положительные целые числа в двоичные слова, с дополнительным свойством: при любом истинном распределение вероятностей на целых числах, пока распределение — монотонно (то есть $p(i) \geqslant p(i+1)$ для любого $i$), ожидаемые длины двоичных слов находятся в пределах постоянного фактора ожидаемых длин, которые оптимальный код назначил бы для этого распределения вероятностей.

Гамма-код Элиаса

Определение:

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

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

Способ первый:

1. Записать число в двоичном представлении.
2. Перед двоичным представлением дописать нули, количество нулей на единицу меньше количества битов двоичного представления числа.

Способ второй:

1. Выделить из целого числа старший значащий бит (самую большую степень $2$, которую число включает — $2\times{N}$) и младшие $N$ бит.
2. Записать $N$ в унарном коде, то есть $N$ нулей, за которыми следует единица.
3. Дописать $N$ младших двоичных цифр числа следом за этим унарным кодом.

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

1. Считать все нули, встречающиеся до первой $1$. Пусть $N$ — количество этих нулей.
2. Принимая во внимание единицу, которая станет первым битом целого числа, со значением $2^N$, считать оставшиеся $N$ цифр целого числа.

Примеры

Пример кодирования числа $15$

1. Записать число $15$ в двоичном представлении $1111_2$.
2. Дописать перед числом три нуля $0001111$.

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

1. Считываем нули до первой единицы, $N = 3$.
2. Считываем единицу и $N = 3$ бит. Получаем $2^3$ + $111_2$ = $15$.

Приведем примеры нескольких первых гамма-кодов Элиаса:

Число	Гамма-код
1	1
2	010
3	011
4	00100
5	00101
6	00110
7	00111
8	0001000

Гамма-код Элиаса не подходит для кодирования нулевых значений или отрицательных чисел. Для того, чтобы закодировать ноль нужно прибавить к нему $1$ до кодирования и отнять после декодирования. Чтобы закодировать все целые числа можно установить биекцию (соответствие), отображая целые числа из $(0, 1, -1, 2, -2, 3, -3, ...)$ в $(1, 2, 3, 4, 5, 6, 7, ...)$.

Дельта-код Элиаса

Определение:

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

Алгоритм построения дельта-кода Элиаса

Способ первый:

1. Сосчитать $L$ — количество значащих битов в двоичном представлении числа $N$.
2. Сосчитать $M$ — количество значащих битов в двоичном представлении числа $L$.
3. Записать $M$ — $1$ нулей и одну единицу.
4. С правой стороны дописать биты числа $L$ без старшей единицы.
5. С правой стороны дописать биты числа $N$ без старшей единицы ($N_2$).

Способ второй:

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

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

1. Сосчитать $M$ — количество нулей во входном потоке до первой единицы.
2. Не включая единицу считать $M$ битов. Считанное число в сумме с $2^M$ дает $L$.
3. Далее идут $L$ — $1$ младших битов числа $N$. Считать их и к считанному числу прибавить $2^{L-1}$.

Примеры

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

1. В двоичном представлении числа $N = 10 = 1010_2$ всего $4$ значащих бита $(L = 4)$.
2. В двоичном представлении числа $L = 4 = 100_2$ всего $3$ значащих бита $(M = 3)$.
3. Пишем $M$ — $1$ ноль и одну единицу $001$.
4. Дописываем справа биты числа $L$ без старшей единицы $00100$.
5. Дописываем с правой стороны биты числа $N$ без старшей единицы $00100010$.

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

1. Считаем количество нулей до первой единицы во входном потоке $(M = 2)$.
2. Читаем из потока следующие $M$ бит $(00)$. Это дает нам $L = 2^M + 00_2$ = 4.
3. Читаем из потока следующие $L$ — $1$ бит $(010)$. $N = 2^{L- 1} + 010_2 =$ $10$.

Приведем примеры нескольких первых дельта-кодов Элиаса:

Число	Дельта-код
1	1
2	0100
3	0101
4	01100
5	01101
6	01110
7	01111
8	00100000
9	00100001

Сравнение гамма- и дельта-кодов Элиаса

Диапазон	Гамма-коды	Длина кода, бит	Дельта-коды	Длина кода, бит
1	1	1	1	1
2...3	01x	3	010x	4
4...7	001xx	5	011xx	5
8...15	0001xxx	7	00100xxx	8
16...31	00001xxxx	9	00101xxxx	9
32...63	000001xxxxx	11	00110xxxxx	10
64...127	0000001xxxxxx	13	00111xxxxxx	11
128...255	00000001xxxxxxx	15	0001000xxxxxxx	14

и т. д. Символами "x" тут обозначены биты мантиссы без старшей единицы.

Для диапазона $[2^K,2^{K+1}- 1]$ коды формируются следующим образом:

Гамма-код: $00..(K$ раз$)..01x..(K$ раз$)..x$; длина $2\times{K} + 1$ бит;

Дельта-код: $n...(2\times{L}+1$ раз$)...nx..(K$ раз$)..x$; длина: $2\times{L}+K+1$ бит, где $L = [\log_2{(K+1)}]$ - целая часть логарифма числа $(K+1)$ по основанию $2$; $n$ - биты, относящиеся к записи экспоненты дельта-кода, их число $2\times{L} + 1$.

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

Можно видеть, что для чисел $2, 3, 8...15$ дельта-код длиннее гамма-кода, для чисел $1, 4...7, 16...31$ длина дельта-кода совпадает с длиной гамма-кода, для всех остальных чисел дельта-код короче гамма-кода. Это происходит вследствие того, как строятся данные коды. Как показано выше, длина гама-кода $2\times{K} + 1$, что при больших $K$ очевидно больше, чем $2\times{[\log_2{(K+1)}]} + K + 1$

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

Определение:

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

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

Данные коды состоят из последовательности групп длинной $L_1, L_2, L_3, …, L_m$ бит, которые начинаются (слева) с бита $1$. В конце последовательности (справа) всегда $0$. Длина каждой следующей $(n+1)$-й группы задается значением битов предыдущей $n$-й группы.

В омега-кодах Элиаса длина первой группы — $2$ бита. Длина следующей группы на единицу больше значения предыдущей. Первое значение задается отдельно.

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

1. В конец представления записать $0$.
2. Если число не единица $({N}\neq1)$, слева от построенной последовательности добавить его двоичное представление.
3. В $N$ записать новое значение - количество только что записанных цифр(бит), минус один.
4. Вернуться к шагу 2.

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

1. Записываем в переменную $N$ единицу.
2. Считываем первый слева бит. Если он равен единице, то считываем группу бит длиной $(N + 1)$. Записываем в $N$ число, двоичное представление которого равно этой группе бит. Если он равен нулю, то $N$ и есть наше число.
3. Удаляем считанную группу из последовательности и переходим к шагу 2.

Примеры

Пример кодирования числа $N = 12$

1. Записываем $0$.
2. Добавляем справа от нуля двоичное представление $12 (1100 0)$.
3. $N = 4 - 1 = 3$ (длина последовательности $1100$ минус $1$).
4. Добавляем справа двоичное представление $N (11 1100 0)$.
5. $N = 1$, значит $12$ кодирует последовательность $11 1100 0$.

Пример декодирования последовательности $11 1100 0$

1. $N = 1$.
2. Считываем группу $11. N = 3$.
3. Считываем группу $1100. N = 12$.
4. Следующий бит $= 0$, поэтому закодированное число — $12$.

Приведем примеры нескольких первых омега-кодов Элиаса:

Число	Омега-код
1	0
2	10 0
3	11 0
4	10 100 0
5	10 101 0
6	10 110 0
7	10 111 0
8	11 1000 0
9	11 1001 0
10	11 1010 0
11	11 1011 0
12	11 1100 0
13	11 1101 0
14	11 1110 0
15	11 1111 0
16	10 100 10000 0

Количество групп в коде возрастает быстро вначале, но далее — очень медленно:

1. для $1$ будет $0$ групп;
2. $2 ... 3 (2^1 ... 2^2 - 1)$ — $1$ группа;
3. $4 ... 15 (2^2 ... 2^{2^2} - 1)$ — $2$ группы;
4. $16 ... 65536 (2^{2^2} ... 2^{2^{2^2}} - 1)$ — $3$ группы;
5. $65536 ... 2\times10^{19728} (2^{2^{2^2}} ... 2^{2^{2^{2^2}}} - 1)$ — всего $4$ группы.

Число	Омега-код	Длина
1	0	1
2—3	1x 0	3
4—7	10 1xx 0	6
8—15	11 1xxx 0	7
16—31	10 100 1xxxx 0	11
32—63	10 101 1xxxxx 0	12
64—127	10 110 1xxxxxx 0	13
128—255	10 111 1xxxxxxx 0	14
256—511	11 1000 1xxxxxxxx 0	16
511—1023	11 1001 1xxxxxxxxx 0	17

Источники информации

• Д. Ватолин, Ратушняк, М. Смирнов, В. Юкин "Методы сжатия данных"
• Кодирование целых чисел
• Википедия — Гамма-код Элиаса
• Википедия — Дельта-код Элиаса
• Википедия — Омега-код Элиаса
• Википедия — Универсальный код