Просмотр исходного текста страницы Гамма-, дельта- и омега-код Элиаса

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

Примерами кодов без памяти являются [[Алгоритм Хаффмана|кодирование Хаффмана]] и кодирование Шеннона-Фано.
=== Достоинства кодов без памяти ===
*Данные коды являются префиксными, что упрощает декодирование, поэтому часто именно им отдается предпочтение. 
*Таким способом кодирования удается получить более короткие коды, чем с помощью кода фиксированной длины. 
*Декодировать сообщение можно по мере поступления, не получая его целиком.

=== Недостатки кодов без памяти ===
Коды Хаффмана и Шеннона-Фано являются оптимальными, но все же имеют ряд недостатков. 
*При кодировании методами Хаффмана или Шеннона используются вероятности появления символов алфавита в тексте. То есть для построения кода нам нужно обладать этой информацией. Поэтому необходимо знать всю кодируемую последовательность заранее.
*Для того, чтобы декодер мог расшифровать файл, таблицу частот, которой пользовался кодер, следует записать в сжатый файл. Следовательно, длина сжатого сообщения увеличивается на длину таблицы частот, которая должна посылаться впереди данных, что может не оправдать сжатия. Хотя для кодов Хаффмана можно таблицу передавать [[Оптимальное хранение словаря в алгоритме Хаффмана| оптимально]]
*Необходимость наличия полной частотной статистики перед началом собственно кодирования требует двух проходов по сообщению: одного для построения модели сообщения (таблицы частот и дерево кодирования Хаффмана), другого {{---}} для собственно кодирования.

=== Универсальное кодирование ===
{{Определение
|id = def1
|definition ='''Универсальный код ''' (англ. ''universal code'') {{---}}  префиксный код, который преобразует положительные целые числа в двоичные слова, с дополнительным свойством: при любом истинном распределение вероятностей на целых числах, пока распределение — монотонно (то есть <tex>p(i) \geqslant p(i+1)</tex> для любого <tex>i</tex>), ожидаемые длины двоичных слов находятся в пределах постоянного фактора ожидаемых длин, которые оптимальный код назначил бы для этого распределения вероятностей.}}
Универсальное кодирование применяется, когда декодер не знает, что ему придет следующим, и ему приходится работать с данными по мере поступления.

Коды Элиаса позволяют производить процесс декодирования очень просто. По определенному правилу последовательно считываем группы из нулей или единиц и на основании результатов обработки только что считанных данных читаем дальше по тому же правилу. Следовательно, мы можем однозначно декодировать число, либо сказать, что в коде ошибка. Таким образом, мы можем быстро передавать последовательность чисел, так же быстро и точно ее декодируя.

Коды Элиаса для их построения не требуют использования вероятности появления символов, чем выигрывают у кодов Хаффмана и Шеннона. Данные коды могут быть использованы для шифрования, так как по скорости построение и декодирование этих кодов сильно выигрывает у большинства остальных, что в настоящее время очень важно. Однако длины кодов Элиаса зачастую превышают длины обычных двоичных представлений чисел, что накладывает ограничения на область их использования. Это является следствием такого способа кодирования информации. Поэтому лучше использовать эти коды тогда, когда нам передают маленькие числа.

Данные коды применяются и имеют неплохие результаты сжатия. Например, если мы строку преобразуем при помощи алгоритма [[Преобразование MTF|move-to-front]], то получим на выходе последовательность довольно небольших чисел. На небольшие числа коды Элиаса тратят мало бит, поэтому данный алгоритм будет довольно эффективен. Если мы получим значительное количество нулей, а что-то большое будет встречаться иногда, то мы неплохо закодируем и сожмём последовательность. Например, хороший результат даст такая связка: Барроуз-Уиллер + MTF + Коды Элиаса.

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

'''Цель''' {{---}} сжатие потока <tex>R</tex>-битовых элементов.

Основная идея состоит в том, чтобы отдельно описывать порядок значения элемента ("экспоненту" <tex>E_i</tex>) и отдельно {{---}} значащие цифры значения ("мантиссу" <tex>M_i</tex>).

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

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

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

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

1. Fixed <tex>+</tex> Fixed (Фиксированная длина экспоненты {{---}} Фиксированная длина мантиссы), а остальные три:

2. Fixed <tex>+</tex> Variable (Фиксированная длина экспоненты {{---}} Переменная длина мантиссы),

3. Variable <tex>+</tex> Variable (Переменная длина экспоненты {{---}} Переменная длина мантиссы) и

4. Variable <tex>+</tex> Fixed (Переменная длина экспоненты {{---}} Фиксированная длина мантиссы).

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

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

{{Определение
|id = def1
|definition ='''Унарное представление числа <tex>n</tex> ''' (англ. ''unary code'') {{---}} <tex>n</tex> подряд идущих единиц, заканчивающихся контрольным нулем (иногда наоборот: <tex>n</tex> нулей, за которыми следует контрольная единица). Более наглядно унарные коды можно представить в виде двоичного дерева, которое устроено следующим образом: каждому ребру, ведущему из вершины к правому ребенку, соответствует единица, иначе ноль, причем левый ребенок уже не имеет детей. Например, если нужно закодировать число m, нужно m раз пройти по правым вершинам и затем остановиться на левой.}}
Например, унарный код нуля {{---}} <tex>0</tex>, единицы {{---}} <tex>10</tex>, двойки {{---}} <tex>110</tex> и т. д.
=== Гамма-код Элиаса ===

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

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

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

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

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

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

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

==== Примеры ====

''' Пример кодирования числа <tex>15</tex> '''

# Записать число <tex>15</tex> в двоичном представлении  <tex>1111_2</tex>.
# Дописать перед числом три нуля  '''<tex>0001111</tex>'''.

''' Пример декодирования последовательности битов <tex>0001111</tex> '''

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

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

{| class="wikitable" style="width:10cm" border=1
|+
|-align="center" bgcolor=#EEEEFF
! Число || Гамма-код 
|-align="center" bgcolor=#FFFFFF
|1||1
|-align="center" bgcolor=#FFFFFF
|2||010
|-align="center" bgcolor=#FFFFFF
||3||011
|-align="center" bgcolor=#FFFFFF
|4||00100
|-align="center" bgcolor=#FFFFFF
|5||00101
|-align="center" bgcolor=#FFFFFF
|6||00110
|-align="center" bgcolor=#FFFFFF
|7||00111
|-align="center" bgcolor=#FFFFFF
|8||0001000
|}

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

=== Дельта-код Элиаса ===
{{Определение
|id = def1
|definition ='''Дельта-код Элиаса ''' (англ. ''Elias delta code'') {{---}} это универсальный код для кодирования положительных целых чисел, разработанный Питером Элиасом. Как далее будет видно, дельта-код с некоторого числа короче гамма-кода.}}
==== Алгоритм построения дельта-кода Элиаса ====

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

# Сосчитать <tex>L</tex> {{---}} количество значащих битов в двоичном представлении числа <tex>N</tex>.
# Сосчитать <tex>M</tex> {{---}} количество значащих битов в двоичном представлении числа <tex>L</tex>.
# Записать <tex>M</tex> {{---}} <tex>1</tex> нулей и одну единицу.
# С правой стороны дописать биты числа <tex>L</tex> без старшей единицы.
# С правой стороны дописать биты числа <tex>N</tex> без старшей единицы (<tex>N_2</tex>).

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

# Сосчитать <tex>L</tex> {{---}} количество значащих битов в двоичном представлении числа <tex>N</tex>.
# Закодировать <tex>L</tex> с помощью гамма-кода Элиаса.
# Дописать к <tex>L</tex> справа двоичное представление числа <tex>N</tex> без старшей единицы.

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

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

==== Примеры ====

'''Пример кодирования числа <tex>10</tex>'''

# В двоичном представлении числа <tex>N = 10 = 1010_2</tex>  всего <tex>4</tex> значащих бита <tex>(L = 4)</tex>.
# В двоичном представлении числа <tex>L = 4 = 100_2</tex> всего <tex>3</tex> значащих бита <tex>(M = 3)</tex>.
# Пишем <tex>M</tex> {{---}} <tex>1</tex> ноль и одну единицу <tex>001</tex>.
# Дописываем справа биты числа <tex>L</tex> без старшей единицы <tex>00100</tex>.
# Дописываем с правой стороны биты числа <tex>N</tex> без старшей единицы '''<tex>00100010</tex>'''.

'''Пример декодирования последовательности битов <tex>00100010</tex>'''

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

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

{| class="wikitable" style="width:10cm" border=1
|+
|-align="center" bgcolor=#EEEEFF
! Число || Дельта-код
|-align="center" bgcolor=#FFFFFF
|1||1
|-align="center" bgcolor=#FFFFFF
|2||0100
|-align="center" bgcolor=#FFFFFF
|3||0101
|-align="center" bgcolor=#FFFFFF
|4||01100
|-align="center" bgcolor=#FFFFFF
|5||01101
|-align="center" bgcolor=#FFFFFF
|6||01110
|-align="center" bgcolor=#FFFFFF
|7||01111
|-align="center" bgcolor=#FFFFFF
|8||00100000
|-align="center" bgcolor=#FFFFFF
|9||00100001
|}

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

{| class="wikitable" style="width:10cm" border=1
|+
|-align="center" bgcolor=#EEEEFF
! Диапазон || Гамма-коды || Длина кода, бит || Дельта-коды || Длина кода, бит
|-align="center" bgcolor=#FFFFFF
|1||1|||1||1||1
|-align="center" bgcolor=#FFFFFF
|2...3||01x||3||010x||4
|-align="center" bgcolor=#FFFFFF
|4...7||001xx||5||011xx||5
|-align="center" bgcolor=#FFFFFF
|8...15||0001xxx||7||00100xxx||8
|-align="center" bgcolor=#FFFFFF
|16...31||00001xxxx||9||00101xxxx||9
|-align="center" bgcolor=#FFFFFF
|32...63||000001xxxxx||11||00110xxxxx||10
|-align="center" bgcolor=#FFFFFF
|64...127||0000001xxxxxx||13||00111xxxxxx||11
|-align="center" bgcolor=#FFFFFF
|128...255||00000001xxxxxxx||15||0001000xxxxxxx||14
|}
и т. д. Символами "x" тут обозначены биты мантиссы без старшей единицы.

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

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

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

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

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

=== Омега-код Элиаса ===
{{Определение
|id = def1
|definition ='''Омега-код Элиаса ''' (англ. ''Elias omega code'') {{---}} это универсальный код для кодирования положительных целых чисел, разработанный Питером Элиасом. Так же, как гамма- и дельта-код Элиаса, он приписывает к началу целого числа порядок его величины в универсальном коде. Однако, в отличие от двух других указанных кодов, омега-код рекурсивно кодирует префикс, именно поэтому он также известен, как '''рекурсивный код Элиаса'''.}}
Омега-кодирование используется в приложениях, где самое большое кодируемое значение неизвестно заранее, или для сжатия данных, в которых маленькие значения встречаются намного чаще, чем большие.

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

В омега-кодах Элиаса длина первой группы {{---}} <tex>2</tex> бита. Длина следующей группы на единицу больше значения предыдущей. Первое значение задается отдельно.
==== Алгоритм построения омега-кода Элиаса ====
# В конец представления записать <tex>0</tex>.
# Если число не единица <tex>({N}\neq1)</tex>, слева от построенной последовательности добавить его двоичное представление.
# В <tex>N</tex> записать новое значение {{---}} количество только что записанных цифр(бит), минус один.
# Вернуться к шагу 2.

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

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

==== Примеры ====
'''Пример кодирования числа <tex>N  = 12</tex>'''

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

'''Пример декодирования последовательности <tex>11 1100 0</tex>'''

# <tex>N = 1</tex>.
# Считываем группу <tex>11. N = 3</tex>.
# Считываем группу <tex>1100. N = 12</tex>.
# Следующий бит <tex>= 0</tex>, поэтому закодированное число {{---}} '''<tex>12</tex>'''.

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

{| class="wikitable" style="width:10cm" border=1
|+
|-align="center" bgcolor=#EEEEFF
! Число || Омега-код
|-align="center" bgcolor=#FFFFFF
|1||0
|-align="center" bgcolor=#FFFFFF
|2||10 0
|-align="center" bgcolor=#FFFFFF
|3||11 0
|-align="center" bgcolor=#FFFFFF
|4||10 100 0
|-align="center" bgcolor=#FFFFFF
|5||10 101 0
|-align="center" bgcolor=#FFFFFF
|6||10 110 0
|-align="center" bgcolor=#FFFFFF
|7||10 111 0
|-align="center" bgcolor=#FFFFFF
|8||11 1000 0
|-align="center" bgcolor=#FFFFFF
|9||11 1001 0
|-align="center" bgcolor=#FFFFFF
|10||11 1010 0
|-align="center" bgcolor=#FFFFFF
|11||11 1011 0
|-align="center" bgcolor=#FFFFFF
|12||11 1100 0
|-align="center" bgcolor=#FFFFFF
|13||11 1101 0
|-align="center" bgcolor=#FFFFFF
|14||11 1110 0
|-align="center" bgcolor=#FFFFFF
|15||11 1111 0
|-align="center" bgcolor=#FFFFFF
|16||10 100 10000 0
|}

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

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

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

{| class="wikitable" style="width:10cm" border=1
|+
|-align="center" bgcolor=#EEEEFF
! Число || Омега-код || Длина
|-align="center" bgcolor=#FFFFFF
|1||0||1
|-align="center" bgcolor=#FFFFFF
|2—3||1x 0||3
|-align="center" bgcolor=#FFFFFF
|4—7||10 1xx 0||6
|-align="center" bgcolor=#FFFFFF
|8—15||11 1xxx 0||7
|-align="center" bgcolor=#FFFFFF
|16—31||10 100 1xxxx 0||11
|-align="center" bgcolor=#FFFFFF
|32—63||10 101 1xxxxx 0||12
|-align="center" bgcolor=#FFFFFF
|64—127||10 110 1xxxxxx 0||13
|-align="center" bgcolor=#FFFFFF
|128—255||10 111 1xxxxxxx 0||14
|-align="center" bgcolor=#FFFFFF
|256—511||11 1000 1xxxxxxxx 0||16
|-align="center" bgcolor=#FFFFFF
|511—1023||11 1001 1xxxxxxxxx 0||17
|}

== Источники информации ==
*Д. Ватолин, Ратушняк, М. Смирнов,  В. Юкин "Методы сжатия данных"
*[http://rain.ifmo.ru/cat/view.php/theory/coding/integer-2005 Кодирование целых чисел]
*[https://ru.wikipedia.org/wiki/%D0%93%D0%B0%D0%BC%D0%BC%D0%B0-%D0%BA%D0%BE%D0%B4_%D0%AD%D0%BB%D0%B8%D0%B0%D1%81%D0%B0 Википедия {{---}} Гамма-код Элиаса]
*[https://ru.wikipedia.org/wiki/%D0%94%D0%B5%D0%BB%D1%8C%D1%82%D0%B0-%D0%BA%D0%BE%D0%B4_%D0%AD%D0%BB%D0%B8%D0%B0%D1%81%D0%B0 Википедия {{---}} Дельта-код Элиаса]
*[https://ru.wikipedia.org/wiki/%D0%9E%D0%BC%D0%B5%D0%B3%D0%B0-%D0%BA%D0%BE%D0%B4_%D0%AD%D0%BB%D0%B8%D0%B0%D1%81%D0%B0 Википедия {{---}} Омега-код Элиаса]
*[https://ru.wikipedia.org/wiki/%D0%A3%D0%BD%D0%B8%D0%B2%D0%B5%D1%80%D1%81%D0%B0%D0%BB%D1%8C%D0%BD%D1%8B%D0%B9_%D0%BA%D0%BE%D0%B4 Википедия {{---}} Универсальный код]

[[Категория: Дискретная математика и алгоритмы]]

[[Категория: Алгоритмы сжатия ]]