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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Примеры

Пример кодирования числа [math]15[/math]

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

Пример декодирования последовательности битов [math]0001111[/math]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Примеры

Пример кодирования числа [math]10[/math]

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

Пример декодирования последовательности битов [math]00100010[/math]

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

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

Число	Дельта-код
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" тут обозначены биты мантиссы без старшей единицы.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Примеры

Пример кодирования числа [math]N = 12[/math]

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

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

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

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

Число	Омега-код
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. для [math]1[/math] будет [math]0[/math] групп;
2. [math]2 ... 3 (2^1 ... 2^2 - 1)[/math] — [math]1[/math] группа;
3. [math]4 ... 15 (2^2 ... 2^{2^2} - 1)[/math] — [math]2[/math] группы;
4. [math]16 ... 65536 (2^{2^2} ... 2^{2^{2^2}} - 1)[/math] — [math]3[/math] группы;
5. [math]65536 ... 2\times10^{19728} (2^{2^{2^2}} ... 2^{2^{2^{2^2}}} - 1)[/math] — всего [math]4[/math] группы.

Здесь быстрое возрастание количества значений в группе сильно напоминает функцию Аккермана. Начиная с третьей [math](i = 3)[/math] группы их диапазон лежит между значениями функции [math]A(i - 3, 4) + 3[/math] и [math]A(i -2, 4) + 3[/math].

Число	Омега-код	Длина
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

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

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