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

Материал из Викиконспекты
Версия от 23:40, 10 декабря 2014; Анна (обсуждение | вклад) (→‎Омега-код Элиаса)
Перейти к: навигация, поиск

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

Простейшими кодами, на основе которых может выполняться сжатие данных, являются коды без памяти (англ. 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]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, ...)[/math] в [math](1, 2, 3, 4, 5, 6, 7, ...)[/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, …, 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] группы.
Число Омега-код Длина
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

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

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Гамма-,_дельта-_и_омега-код_Элиаса&oldid=42032»