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

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

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

К примеру, множество двоичных слов [math]S_1[/math] = [math] \{00, 01, 100, 110, 1010, 1011\} [/math] является префиксным множеством двоичных последовательностей, поскольку, если проверить любую из 30 возможных совместных комбинаций ([math]w_i[/math], [math]w_j[/math]) из [math]S_1[/math], то видно, что [math]w_i[/math] никогда не явится префиксом (или началом) [math]w_j[/math]. С другой стороны, множество [math]S_2[/math] = [math] \{00, 001, 1110\} [/math] не является префиксным множеством двоичных последовательностей, так как последовательность 00 является префиксом (началом) другой последовательности из этого множества — 001. Соответственно, множество [math]S_1[/math] может быть множеством кодовых слов для вектора данных в коде без памяти, а [math]S_2[/math] — нет.

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

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

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

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

Основная идея состоит в том, чтобы отдельно описывать порядок значения элемента ("экспоненту" [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...[/math] = 13 это последние 4 цифры. Порядок числа определяется позицией старшей ненулевой цифры в записи числа. Как и при обычной записи в десятичной системе, он равен числу цифр в записи числа без предшествующих незначащих нулей. В данном примере порядок равен четырем.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1. Записать число в двоичном представлении;

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

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

1. Выделить из целого числа старший значащий бит (самую большую степень 2, которую число включает — 2N) и младшие N бит;

2. Записать N в унарном коде, то есть N нулей, за которыми следует единица;

3. Дописать N младших двоичных цифр числа следом за этим унарным кодом.

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

1. Считать все нули, встречающиеся до первой 1. Пусть N — количество этих нулей;

2. Принимая во внимание единицу, которая станет первым битом целого числа, со значением 2^N, считать оставшиеся N цифр целого числа.

Примеры

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

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

2. Дописать перед числом три нуля 0001111.

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

1. Считываем нули до первой единицы, N = 4;

2. Считываем единицу и N = 4 бит. Получаем [math]2^4[/math] + [math]0001_2[/math] = 17.

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

Число	Гамма-код
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, …).

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

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

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

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

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

1. Сосчитать L — количество значащих битов в двоичном представлении числа N;

2. Сосчитать M — количество значащих битов в двоичном представлении числа L;

3. Записать M — 1 нулей и одну единицу;

4. С правой стороны дописать биты числа L без старшей единицы;

5. С правой стороны дописать биты числа N без старшей единицы ([math]N_2[/math]).

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

1. Сосчитать L — количество значащих битов в двоичном представлении числа N;

2. Закодировать L с помощью гамма-кода Элиаса;

3. Дописать к L справа двоичное представление числа N без старшей единицы.

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

1. Сосчитать M — количество нулей во входном потоке до первой единицы;

2. Не включая единицу считать M битов. Считанное число в сумме с [math]2^M[/math] дает L;

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

Примеры

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

1. В двоичном представлении числа N = 10 = [math]1010_2[/math] 4 значащих бита (L = 4);

2. В двоичном представлении числа L = 4 = [math]100_2[/math] 3 значащих бита (M = 3);

3. Пишем M — 1 ноль и одну единицу 001;

4. Дописываем справа биты числа L без старшей единицы 00100;

5. Дописываем с правой стороны биты числа N без старшей единицы 00100010.

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

1. Считаем количество нулей до первой единицы во входном потоке (M = 2);

2. Читаем из потока следующие M бит (00). Это дает нам L = [math]2^M[/math] + [math]00_2[/math] = 4;

3. Читаем из потока следующие L — 1 бит (010). N = [math]2^{L- 1}[/math] + [math]010_2[/math] = 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	114

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

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

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

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

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

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

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

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

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

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

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

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

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

1. В конец представления записать 0;

2. Если число не единица (N <> 1), слева от построенной последовательности добавить его двоичное представление;

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.

Пример декодирования последовательности 10 100 10001 0

1. N = 1;

2. Считываем группу 10. N = 2;

3. Считываем группу 100. N = 4;

4. Считываем группу 10001. N = 17;

5. Следующий бит = 0, поэтому закодированное число — 17.

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

Число	Омега-код
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
17	10 100 10001 0

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

1. для 1 будет 0 групп;

2. 2 ... 3 ([math]2^1 ... 2^2[/math] − 1) — 1 группа;

3. 4 ... 15 ([math]2^2 ... 2^{2^2}[/math] − 1) — 2 группы;

4. 16 ... 65536 ([math]2^{2^2} ... 2^{2^{2^2}}[/math] − 1) — 3 группы;

5. 65536 ... [math]2\times10^{19728} (2^{2^{2^2}} ... 2^{2^{2^{2^2}}}[/math] − 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

Ссылки

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