Гамма-, дельта- и омега-код Элиаса — различия между версиями
Анна (обсуждение | вклад) (→Разделение мантисс и экспонент) |
Анна (обсуждение | вклад) (→Коды переменной длины (Variable + Variable)) |
||
Строка 35: | Строка 35: | ||
{{Определение | {{Определение | ||
|id = def1 | |id = def1 | ||
− | |definition ='''Унарное представление числа n ''' (англ. ''unary code'') {{---}} n подряд идущих единиц, заканчивающихся контрольным нулем (иногда наоборот: n нулей, за которыми следует контрольная единица). Более наглядно унарные коды можно представить в виде двоичного дерева, которое устроено следующим образом: каждому ребру, ведущему из вершины к правому ребенку, соответствует единица, иначе ноль, причем левый ребенок уже не имеет детей. Например, если нужно закодировать число m, нужно m раз пройти по правым вершинам и затем остановиться на левой.}} | + | |definition ='''Унарное представление числа <tex>n</tex> ''' (англ. ''unary code'') {{---}} <tex>n</tex> подряд идущих единиц, заканчивающихся контрольным нулем (иногда наоборот: <tex>n</tex> нулей, за которыми следует контрольная единица). Более наглядно унарные коды можно представить в виде двоичного дерева, которое устроено следующим образом: каждому ребру, ведущему из вершины к правому ребенку, соответствует единица, иначе ноль, причем левый ребенок уже не имеет детей. Например, если нужно закодировать число m, нужно m раз пройти по правым вершинам и затем остановиться на левой.}} |
− | Например, унарный код нуля {{---}} 0, единицы {{---}} 10, двойки {{---}} 110 и т. д. | + | Например, унарный код нуля {{---}} <tex>0</tex>, единицы {{---}} <tex>10</tex>, двойки {{---}} <tex>110</tex> и т. д. |
=== Гамма-код Элиаса === | === Гамма-код Элиаса === | ||
Строка 53: | Строка 53: | ||
'''Способ второй:''' | '''Способ второй:''' | ||
− | 1. Выделить из целого числа старший значащий бит (самую большую степень 2, которую число включает — | + | 1. Выделить из целого числа старший значащий бит (самую большую степень <tex>2</tex>, которую число включает — <tex>2\timesN</tex>) и младшие <tex>N</tex> бит; |
− | 2. Записать N в унарном коде, то есть N нулей, за которыми следует единица; | + | 2. Записать <tex>N</tex> в унарном коде, то есть <tex>N</tex> нулей, за которыми следует единица; |
− | 3. Дописать N младших двоичных цифр числа следом за этим унарным кодом. | + | 3. Дописать <tex>N</tex> младших двоичных цифр числа следом за этим унарным кодом. |
==== Декодирование ==== | ==== Декодирование ==== | ||
− | 1. Считать все нули, встречающиеся до первой 1. Пусть N — количество этих нулей; | + | 1. Считать все нули, встречающиеся до первой <tex>1</tex>. Пусть <tex>N</tex> — количество этих нулей; |
− | 2. Принимая во внимание единицу, которая станет первым битом целого числа, со значением 2^N, считать оставшиеся N цифр целого числа. | + | 2. Принимая во внимание единицу, которая станет первым битом целого числа, со значением <tex>2^N</tex>, считать оставшиеся <tex>N</tex> цифр целого числа. |
==== Примеры ==== | ==== Примеры ==== | ||
− | ''' Пример кодирования числа 15 ''' | + | ''' Пример кодирования числа <tex>15</tex> ''' |
− | 1. Записать число 15 в двоичном представлении <tex>1111_2</tex>; | + | 1. Записать число <tex>15</tex> в двоичном представлении <tex>1111_2</tex>; |
− | 2. Дописать перед числом три нуля '''0001111'''. | + | 2. Дописать перед числом три нуля '''<tex>0001111</tex>'''. |
− | ''' Пример декодирования последовательности битов 000010001 ''' | + | ''' Пример декодирования последовательности битов <tex>000010001</tex> ''' |
− | 1. Считываем нули до первой единицы, N = 4; | + | 1. Считываем нули до первой единицы, <tex>N = 4</tex>; |
− | 2. Считываем единицу и N = 4 бит. Получаем <tex>2^4</tex> + <tex>0001_2</tex> = '''17'''. | + | 2. Считываем единицу и <tex>N = 4</tex> бит. Получаем <tex>2^4</tex> + <tex>0001_2</tex> = '''<tex>17</tex>'''. |
Приведем примеры нескольких первых гамма-кодов Элиаса: | Приведем примеры нескольких первых гамма-кодов Элиаса: | ||
Строка 103: | Строка 103: | ||
|} | |} | ||
− | Гамма-код Элиаса не подходит для кодирования нулевых значений или отрицательных чисел. Для того, чтобы закодировать ноль нужно прибавить к нему 1 до кодирования и отнять после декодирования. Чтобы закодировать все целые числа можно установить биекцию (соответствие), отображая целые числа из (0, 1, −1, 2, −2, 3, −3, …) в (1, 2, 3, 4, 5, 6, 7, …). | + | Гамма-код Элиаса не подходит для кодирования нулевых значений или отрицательных чисел. Для того, чтобы закодировать ноль нужно прибавить к нему <tex>1</tex> до кодирования и отнять после декодирования. Чтобы закодировать все целые числа можно установить биекцию (соответствие), отображая целые числа из <tex>(0, 1, −1, 2, −2, 3, −3, …)</tex> в <tex>(1, 2, 3, 4, 5, 6, 7, …)</tex>. |
=== Дельта-код Элиаса === | === Дельта-код Элиаса === | ||
Строка 113: | Строка 113: | ||
'''Способ первый:''' | '''Способ первый:''' | ||
− | 1. Сосчитать L {{---}} количество значащих битов в двоичном представлении числа N; | + | 1. Сосчитать <tex>L</tex> {{---}} количество значащих битов в двоичном представлении числа <tex>N</tex>; |
− | 2. Сосчитать M {{---}} количество значащих битов в двоичном представлении числа L; | + | 2. Сосчитать <tex>M</tex> {{---}} количество значащих битов в двоичном представлении числа <tex>L</tex>; |
− | 3. Записать M {{---}} 1 нулей и одну единицу; | + | 3. Записать <tex>M</tex> {{---}} <tex>1</tex> нулей и одну единицу; |
− | 4. С правой стороны дописать биты числа L без старшей единицы; | + | 4. С правой стороны дописать биты числа <tex>L</tex> без старшей единицы; |
− | 5. С правой стороны дописать биты числа N без старшей единицы (<tex>N_2</tex>). | + | 5. С правой стороны дописать биты числа <tex>N</tex> без старшей единицы (<tex>N_2</tex>). |
'''Способ второй:''' | '''Способ второй:''' | ||
− | 1. Сосчитать L {{---}} количество значащих битов в двоичном представлении числа N; | + | 1. Сосчитать <tex>L</tex> {{---}} количество значащих битов в двоичном представлении числа <tex>N</tex>; |
− | 2. Закодировать L с помощью гамма-кода Элиаса; | + | 2. Закодировать <tex>L</tex> с помощью гамма-кода Элиаса; |
− | 3. Дописать к L справа двоичное представление числа N без старшей единицы. | + | 3. Дописать к <tex>L</tex> справа двоичное представление числа <tex>N</tex> без старшей единицы. |
==== Декодирование ==== | ==== Декодирование ==== | ||
− | 1. Сосчитать M {{---}} количество нулей во входном потоке до первой единицы; | + | 1. Сосчитать <tex>M</tex> {{---}} количество нулей во входном потоке до первой единицы; |
− | 2. Не включая единицу считать M битов. Считанное число в сумме с <tex>2^M</tex> дает L; | + | 2. Не включая единицу считать <tex>M</tex> битов. Считанное число в сумме с <tex>2^M</tex> дает <tex>L</tex>; |
− | 3. Далее идут L {{---}} 1 младших битов числа N. Считать их и к считанному числу прибавить <tex>2^{L-1}</tex>. | + | 3. Далее идут <tex>L {{---}} 1</tex> младших битов числа <tex>N</tex>. Считать их и к считанному числу прибавить <tex>2^{L-1}</tex>. |
==== Примеры ==== | ==== Примеры ==== | ||
− | '''Пример кодирования числа 10''' | + | '''Пример кодирования числа <tex>10</tex>''' |
− | 1. В двоичном представлении числа N = 10 = | + | 1. В двоичном представлении числа <tex>N = 10 = 1010_2 4</tex> значащих бита <tex>(L = 4)</tex>; |
− | 2. В двоичном представлении числа L = 4 = | + | 2. В двоичном представлении числа <tex>L = 4 = 100_2 3</tex> значащих бита <tex>(M = 3)</tex>; |
− | 3. Пишем M {{---}} 1 ноль и одну единицу 001; | + | 3. Пишем <tex>M {{---}} 1</tex> ноль и одну единицу <tex>001</tex>; |
− | 4. Дописываем справа биты числа L без старшей единицы 00100; | + | 4. Дописываем справа биты числа <tex>L</tex> без старшей единицы <tex>00100</tex>; |
− | 5. Дописываем с правой стороны биты числа N без старшей единицы '''00100010'''. | + | 5. Дописываем с правой стороны биты числа <tex>N</tex> без старшей единицы '''<tex>00100010</tex>'''. |
− | '''Пример декодирования последовательности битов 00100010''' | + | '''Пример декодирования последовательности битов <tex>00100010</tex>''' |
− | 1. Считаем количество нулей до первой единицы во входном потоке (M = 2); | + | 1. Считаем количество нулей до первой единицы во входном потоке <tex>(M = 2);<tex> |
− | 2. Читаем из потока следующие M бит (00). Это дает нам | + | 2. Читаем из потока следующие <tex>M</tex> бит <tex>(00)</tex>. Это дает нам <tex>L = 2^M + 00_2</tex> = 4; |
− | 3. Читаем из потока следующие L {{---}} 1 бит (010). | + | 3. Читаем из потока следующие <tex>L {{---}} 1</tex> бит <tex>(010)</tex>. <tex>N = 2^{L- 1} + 010_2 = '''10'''</tex>. |
Приведем примеры нескольких первых дельта-кодов Элиаса: | Приведем примеры нескольких первых дельта-кодов Элиаса: | ||
Строка 215: | Строка 215: | ||
и т. д. Символами "x" тут обозначены биты мантиссы без старшей единицы. | и т. д. Символами "x" тут обозначены биты мантиссы без старшей единицы. | ||
− | Для диапазона | + | Для диапазона <tex>[2^K,2^{K+1}- 1]</tex> коды формируются следующим образом: |
− | '''Гамма-код''': 00..(К раз)..01x..(К раз)..x; длина <tex>2\times{K} + 1</tex> бит; | + | '''Гамма-код''': <tex>00..(К</tex> раз<tex>)..01x..(К</tex> раз<tex>)..x</tex>; длина <tex>2\times{K} + 1</tex> бит; |
− | '''Дельта-код''': n...( | + | '''Дельта-код''': <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>. |
Единственное отличие между гамма- и дельта-кодами состоит в том, что в гамма-кодах экспоненты записываются в унарном виде, а в дельта-кодах к ним еще раз применяется гамма-кодирование. | Единственное отличие между гамма- и дельта-кодами состоит в том, что в гамма-кодах экспоненты записываются в унарном виде, а в дельта-кодах к ним еще раз применяется гамма-кодирование. | ||
− | Можно видеть, что для чисел 2, 3, 8…15 дельта-код длиннее гамма-кода, для чисел 1, 4…7, 16…31 длина дельта-кода совпадает с длиной гамма-кода, для всех остальных чисел дельта-код короче гамма-кода. | + | Можно видеть, что для чисел <tex>2, 3, 8…15</tex> дельта-код длиннее гамма-кода, для чисел <tex>1, 4…7, 16…31</tex> длина дельта-кода совпадает с длиной гамма-кода, для всех остальных чисел дельта-код короче гамма-кода. |
=== Омега-код Элиаса === | === Омега-код Элиаса === | ||
Строка 232: | Строка 232: | ||
Омега-кодирование используется в приложениях, где самое большое кодируемое значение неизвестно заранее, или для сжатия данных, в которых маленькие значения встречаются намного чаще, чем большие. | Омега-кодирование используется в приложениях, где самое большое кодируемое значение неизвестно заранее, или для сжатия данных, в которых маленькие значения встречаются намного чаще, чем большие. | ||
− | Данные коды состоят из последовательности групп длинной <tex>L_1, L_2, L_3, …, L_m</tex> бит, которые начинаются (слева) с бита 1. В конце последовательности (справа) всегда 0. Длина каждой следующей (n+1)-й группы задается значением битов предыдущей n-й группы. | + | Данные коды состоят из последовательности групп длинной <tex>L_1, L_2, L_3, …, L_m</tex> бит, которые начинаются (слева) с бита <tex>1</tex>. В конце последовательности (справа) всегда <tex>0</tex>. Длина каждой следующей <tex>(n+1)</tex>-й группы задается значением битов предыдущей <tex>n</tex>-й группы. |
− | В омега-кодах Элиаса длина первой группы | + | В омега-кодах Элиаса длина первой группы {{---}} <tex>2</tex> бита. Длина следующей группы на единицу больше значения предыдущей. Первое значение задается отдельно. |
==== Алгоритм построения омега-кода Элиаса ==== | ==== Алгоритм построения омега-кода Элиаса ==== | ||
− | 1. В конец представления записать 0; | + | 1. В конец представления записать <tex>0</tex>; |
− | 2. Если число не единица (N <> 1), слева от построенной последовательности добавить его двоичное представление; | + | 2. Если число не единица <tex>(N <> 1)</tex>, слева от построенной последовательности добавить его двоичное представление; |
− | 3. В N записать новое значение - количество только что записанных цифр(бит), минус один; | + | 3. В <tex>N</tex> записать новое значение - количество только что записанных цифр(бит), минус один; |
4. Вернуться к шагу 2. | 4. Вернуться к шагу 2. | ||
Строка 246: | Строка 246: | ||
==== Декодирование ==== | ==== Декодирование ==== | ||
− | 1. Записываем в переменную N единицу; | + | 1. Записываем в переменную <tex>N</tex> единицу; |
− | 2. Считываем первый слева бит. Если он равен единице, то считываем группу бит длиной (N + 1). Записываем в N число, двоичное представление которого равно этой группе бит. Если он равен нулю, то N и есть наше число; | + | 2. Считываем первый слева бит. Если он равен единице, то считываем группу бит длиной <tex>(N + 1)</tex>. Записываем в <tex>N</tex> число, двоичное представление которого равно этой группе бит. Если он равен нулю, то <tex>N</tex> и есть наше число; |
3. Удаляем считанную группу из последовательности и переходим к шагу 2. | 3. Удаляем считанную группу из последовательности и переходим к шагу 2. | ||
==== Примеры ==== | ==== Примеры ==== | ||
− | '''Пример кодирования числа N = 12''' | + | '''Пример кодирования числа <tex>N = 12</tex>''' |
− | 1. Записываем 0; | + | 1. Записываем <tex>0</tex>; |
− | 2. Добавляем справа от нуля двоичное представление 12 (1100 0); | + | 2. Добавляем справа от нуля двоичное представление <tex>12 (1100 0)</tex>; |
− | 3. N = 4 - 1 = 3 (длина последовательности 1100 минус 1); | + | 3. <tex>N = 4 - 1 = 3</tex> (длина последовательности <tex>1100</tex> минус <tex>1</tex>); |
− | 4. Добавляем справа двоичное представление N (11 1100 0); | + | 4. Добавляем справа двоичное представление <tex>N (11 1100 0)</tex>; |
− | 5. N = 1, значит 12 кодирует последовательность '''11 1100 0'''. | + | 5. <tex>N = 1</tex>, значит <tex>12</tex> кодирует последовательность '''<tex>11 1100 0</tex>'''. |
− | '''Пример декодирования последовательности 10 100 10001 0''' | + | '''Пример декодирования последовательности <tex>10 100 10001 0</tex>''' |
− | 1. N = 1; | + | 1. <tex>N = 1</tex>; |
− | 2. Считываем группу 10. N = 2; | + | 2. Считываем группу <tex>10. N = 2</tex>; |
− | 3. Считываем группу 100. N = 4; | + | 3. Считываем группу <tex>100. N = 4</tex>; |
− | 4. Считываем группу 10001. N = 17; | + | 4. Считываем группу <tex>10001. N = 17</tex>; |
− | 5. Следующий бит = 0, поэтому закодированное число {{---}} '''17'''. | + | 5. Следующий бит <tex>= 0</tex>, поэтому закодированное число {{---}} '''<tex>17</tex>'''. |
Приведем примеры нескольких первых омега-кодов Элиаса: | Приведем примеры нескольких первых омега-кодов Элиаса: | ||
Строка 321: | Строка 321: | ||
Количество групп в коде возрастает быстро вначале, но далее — очень медленно: | Количество групп в коде возрастает быстро вначале, но далее — очень медленно: | ||
− | 1. для 1 будет 0 групп; | + | 1. для <tex>1</tex> будет <tex>0</tex> групп; |
− | 2. 2 ... 3 ( | + | 2. <tex>2 ... 3 (2^1 ... 2^2 − 1) {{---}} 1</tex> группа; |
− | 3. 4 ... 15 ( | + | 3. <tex>4 ... 15 (2^2 ... 2^{2^2} − 1) {{---}} 2<tex> группы; |
− | 4. 16 ... 65536 ( | + | 4. <tex>16 ... 65536 (2^{2^2} ... 2^{2^{2^2}} − 1) {{---}} 3</tex> группы; |
− | 5. 65536 ... | + | 5. <tex>65536 ... 2\times10^{19728} (2^{2^{2^2}} ... 2^{2^{2^{2^2}}} − 1) {{---}}</tex> всего <tex>4</tex> группы. |
{| border="1" | {| border="1" |
Версия 21:14, 29 ноября 2014
Содержание
Коды без памяти
Простейшими кодами, на основе которых может выполняться сжатие данных, являются коды без памяти (англ. code without memory). В коде без памяти каждый символ в кодируемом векторе данных заменяется кодовым словом из префиксного множества двоичных последовательностей или слов.
К примеру, множество двоичных слов
= является префиксным множеством двоичных последовательностей, поскольку, если проверить любую из 30 возможных совместных комбинаций ( , ) из , то видно, что никогда не явится префиксом (или началом) . С другой стороны, множество = не является префиксным множеством двоичных последовательностей, так как последовательность 00 является префиксом (началом) другой последовательности из этого множества — 001. Соответственно, множество может быть множеством кодовых слов для вектора данных в коде без памяти, а — нет.Примерами кодов без памяти являются кодирование Хаффмана и кодирование Шеннона — Фано.
Разделение мантисс и экспонент
Английское название метода — Separate Exponents and Mantissas (SEM).
Цель — сжатие потока
-битовых элементов.Основная идея состоит в том, чтобы отдельно описывать порядок значения элемента ("экспоненту"
) и отдельно — значащие цифры значения ("мантиссу" ).Значащие цифры начинаются со старшей ненулевой цифры: например, в числе
= это последние цифры. Порядок числа определяется позицией старшей ненулевой цифры в записи числа. Как и при обычной записи в десятичной системе, он равен числу цифр в записи числа без предшествующих незначащих нулей. В данном примере порядок равен четырем.Методы данной группы являются трансформирующими и поточными, то есть могут применяться даже в том случае, когда объем входных данных заранее не известен. В общем случае скорость работы компрессора (содержащего прямое, «сжимающее» преобразование) равна скорости декомпрессора (реализующего обратное, «разжимающее» преобразование) и зависит только от объема исходных данных. Памяти потребуется всего несколько байтов.
В самом простом случае под запись экспонент и мантисс отводится фиксированное число битов:
и . Причем , , , где — число битов в записи исходного числа.Этот первый из четырех вариантов метода условно обозначим
1. Fixed
Fixed (Фиксированная длина экспоненты — Фиксированная длина мантиссы), а остальные три:2. Fixed
Variable (Фиксированная длина экспоненты — Переменная длина мантиссы),3. Variable
Variable (Переменная длина экспоненты — Переменная длина мантиссы) и4. Variable
Fixed (Переменная длина экспоненты — Фиксированная длина мантиссы).Есть несколько путей еще большего увеличения степени сжатия. Например, применение хорошо исследованных схем кодирования (Элиаса, Раиса, Голомба, Фибоначчи).
Коды переменной длины (Variable + Variable)
Определение: |
Унарное представление числа | (англ. unary code) — подряд идущих единиц, заканчивающихся контрольным нулем (иногда наоборот: нулей, за которыми следует контрольная единица). Более наглядно унарные коды можно представить в виде двоичного дерева, которое устроено следующим образом: каждому ребру, ведущему из вершины к правому ребенку, соответствует единица, иначе ноль, причем левый ребенок уже не имеет детей. Например, если нужно закодировать число m, нужно m раз пройти по правым вершинам и затем остановиться на левой.
Например, унарный код нуля —
, единицы — , двойки — и т. д.Гамма-код Элиаса
Определение: |
Гамма-код Элиаса (англ. Elias gamma code) — это универсальный код для кодирования положительных целых чисел, разработанный Питером Элиасом. Он обычно используется при кодировании целых чисел, максимальное значение которых не может быть определено заранее, или чтобы сжать данные, в которых маленькие значения встречаются более часто, чем большие. |
Алгоритм построения гамма-кода Элиаса
Способ первый:
1. Записать число в двоичном представлении;
2. Перед двоичным представлением дописать нули, количество нулей на единицу меньше количества битов двоичного представления числа.
Способ второй:
1. Выделить из целого числа старший значащий бит (самую большую степень
, которую число включает — ) и младшие бит;2. Записать
в унарном коде, то есть нулей, за которыми следует единица;3. Дописать
младших двоичных цифр числа следом за этим унарным кодом.Декодирование
1. Считать все нули, встречающиеся до первой
. Пусть — количество этих нулей;2. Принимая во внимание единицу, которая станет первым битом целого числа, со значением
, считать оставшиеся цифр целого числа.Примеры
Пример кодирования числа
1. Записать число
в двоичном представлении ;2. Дописать перед числом три нуля
.Пример декодирования последовательности битов
1. Считываем нули до первой единицы,
;2. Считываем единицу и
бит. Получаем + = .Приведем примеры нескольких первых гамма-кодов Элиаса:
Число | Гамма-код |
1 | 1 |
2 | 010 |
3 | 011 |
4 | 00100 |
5 | 00101 |
6 | 00110 |
7 | 00111 |
8 | 0001000 |
Гамма-код Элиаса не подходит для кодирования нулевых значений или отрицательных чисел. Для того, чтобы закодировать ноль нужно прибавить к нему
до кодирования и отнять после декодирования. Чтобы закодировать все целые числа можно установить биекцию (соответствие), отображая целые числа из в .Дельта-код Элиаса
Определение: |
Дельта-код Элиаса (англ. Elias delta code) — это универсальный код для кодирования положительных целых чисел, разработанный Питером Элиасом. Как далее будет видно, дельта-код с некоторого числа короче гамма-кода. |
Алгоритм построения дельта-кода Элиаса
Способ первый:
1. Сосчитать
— количество значащих битов в двоичном представлении числа ;2. Сосчитать
— количество значащих битов в двоичном представлении числа ;3. Записать
— нулей и одну единицу;4. С правой стороны дописать биты числа
без старшей единицы;5. С правой стороны дописать биты числа
без старшей единицы ( ).Способ второй:
1. Сосчитать
— количество значащих битов в двоичном представлении числа ;2. Закодировать
с помощью гамма-кода Элиаса;3. Дописать к
справа двоичное представление числа без старшей единицы.Декодирование
1. Сосчитать
— количество нулей во входном потоке до первой единицы;2. Не включая единицу считать
битов. Считанное число в сумме с дает ;3. Далее идут
младших битов числа . Считать их и к считанному числу прибавить .Примеры
Пример кодирования числа
1. В двоичном представлении числа
значащих бита ;2. В двоичном представлении числа
значащих бита ;3. Пишем
ноль и одну единицу ;4. Дописываем справа биты числа
без старшей единицы ;5. Дописываем с правой стороны биты числа
без старшей единицы .Пример декодирования последовательности битов
1. Считаем количество нулей до первой единицы во входном потоке
бит . Это дает нам = 4;3. Читаем из потока следующие
бит . .Приведем примеры нескольких первых дельта-кодов Элиаса:
Число | Дельта-код |
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" тут обозначены биты мантиссы без старшей единицы.
Для диапазона
коды формируются следующим образом:Гамма-код:
раз раз ; длина бит;Дельта-код:
раз раз ; длина: бит, где - целая часть логарифма числа по основанию ; - биты, относящиеся к записи экспоненты дельта-кода, их число .Единственное отличие между гамма- и дельта-кодами состоит в том, что в гамма-кодах экспоненты записываются в унарном виде, а в дельта-кодах к ним еще раз применяется гамма-кодирование.
Можно видеть, что для чисел
дельта-код длиннее гамма-кода, для чисел длина дельта-кода совпадает с длиной гамма-кода, для всех остальных чисел дельта-код короче гамма-кода.Омега-код Элиаса
Определение: |
Омега-код Элиаса (англ. Elias omega code) — — это универсальный код для кодирования положительных целых чисел, разработанный Питером Элиасом. Так же, как гамма- и дельта-код Элиаса, он приписывает к началу целого числа порядок его величины в универсальном коде. Однако, в отличие от двух других указанных кодов, омега-код рекурсивно кодирует префикс, именно поэтому он также известен, как рекурсивный код Элиаса. |
Омега-кодирование используется в приложениях, где самое большое кодируемое значение неизвестно заранее, или для сжатия данных, в которых маленькие значения встречаются намного чаще, чем большие.
Данные коды состоят из последовательности групп длинной
бит, которые начинаются (слева) с бита . В конце последовательности (справа) всегда . Длина каждой следующей -й группы задается значением битов предыдущей -й группы.В омега-кодах Элиаса длина первой группы —
бита. Длина следующей группы на единицу больше значения предыдущей. Первое значение задается отдельно.Алгоритм построения омега-кода Элиаса
1. В конец представления записать
;2. Если число не единица
, слева от построенной последовательности добавить его двоичное представление;3. В
записать новое значение - количество только что записанных цифр(бит), минус один;4. Вернуться к шагу 2.
Декодирование
1. Записываем в переменную
единицу;2. Считываем первый слева бит. Если он равен единице, то считываем группу бит длиной
. Записываем в число, двоичное представление которого равно этой группе бит. Если он равен нулю, то и есть наше число;3. Удаляем считанную группу из последовательности и переходим к шагу 2.
Примеры
Пример кодирования числа
1. Записываем
;2. Добавляем справа от нуля двоичное представление
;3.
(длина последовательности минус );4. Добавляем справа двоичное представление
;5.
, значит кодирует последовательность .Пример декодирования последовательности
1.
;2. Считываем группу
;3. Считываем группу
;4. Считываем группу
;5. Следующий бит
, поэтому закодированное число — .Приведем примеры нескольких первых омега-кодов Элиаса:
Число | Омега-код |
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. для
будет групп;2.
группа;3.
группы;5.
всего группы.Число | Омега-код | Длина |
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 |
Ссылки
- Д. Ватолин, Ратушняк, М. Смирнов, В. Юкин "Методы сжатия данных"
- Кодирование целых чисел
- Гамма-код Элиаса - Википедия
- Дельта-код Элиаса - Википедия
- Омега-код Элиаса - Википедия