Гамма-, дельта- и омега-код Элиаса — различия между версиями
Анна (обсуждение | вклад) (→Примеры) |
Анна (обсуждение | вклад) (→Сравнение гамма- и дельта-кодов Элиаса) |
||
Строка 212: | Строка 212: | ||
|} | |} | ||
и т. д. Символами "x" тут обозначены биты мантиссы без старшей единицы. | и т. д. Символами "x" тут обозначены биты мантиссы без старшей единицы. | ||
+ | |||
+ | Для диапазона [<tex>2^K</tex>,<tex>2^{K+1}</tex>- 1 ] коды формируются следующим образом: | ||
+ | |||
+ | Гамма-код: 00..(К раз)..01x..(К раз)..x; длина <tex>2\times{K} + 1</tex> бит; | ||
+ | |||
+ | Дельта-код: <tex>n...(2\times{L}+1</tex> раз)...nx..(K раз)..x; длина: <tex>2\times{L}+K+1</tex> бит, где L = <tex>[\log_2{(K+1)}]</tex> - целая часть логарифма числа (K+1) по основанию 2; n - биты, относящиеся к записи экспоненты дельта-кода, их число <tex>2\times{L} + 1</tex>. |
Версия 01:41, 29 ноября 2014
Содержание
Коды без памяти
Простейшими кодами, на основе которых может выполняться сжатие данных, являются коды без памяти. В коде без памяти каждый символ в кодируемом векторе данных заменяется кодовым словом из префиксного множества двоичных последовательностей или слов.
К примеру, множество двоичных слов
= является префиксным множеством двоичных последовательностей, поскольку, если проверить любую из 30 возможных совместных комбинаций ( , ) из , то видно, что никогда не явится префиксом (или началом) . С другой стороны, множество = не является префиксным множеством двоичных последовательностей, так как последовательность 00 является префиксом (началом) другой последовательности из этого множества — 001. Соответственно, множество может быть множеством кодовых слов для вектора данных в коде без памяти, а — нет.Разделение мантисс и экспонент
Английское название метода - Separate Exponents and Mantissas (SEM).
Цель — сжатие потока R-битовых элементов.
Основная идея состоит в том, чтобы отдельно описывать порядок значения элемента ("экспоненту"
) и отдельно — значащие цифры значения ("мантиссу" ).Значащие цифры начинаются со старшей ненулевой цифры: например, в числе
= = 13 это последние 4 цифры. Порядок числа определяется позицией старшей ненулевой цифры в записи числа. Как и при обычной записи в десятичной системе, он равен числу цифр в записи числа без предшествующих незначащих нулей. В данном примере порядок равен четырем.Методы данной группы являются трансформирующими и поточными, то есть могут применяться даже в том случае, когда объем входных данных заранее не известен. В общем случае скорость работы компрессора (содержащего прямое, «сжимающее» преобразование) равна скорости декомпрессора (реализующего обратное, «разжимающее» преобразование) и зависит только от объема исходных данных. Памяти потребуется всего несколько байтов.
В самом простом случае под запись экспонент и мантисс отводится фиксированное число битов: Е и М. Причем
, , 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 в двоичном представлении
;2. Дописать перед числом три нуля 0001111.
Пример декодирования последовательности битов 000010001
1. Считываем нули до первой единицы, N = 4;
2. Считываем единицу и N = 4 бит. Получаем
+ = 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 без старшей единицы (
).Способ второй:
1. Сосчитать L — количество значащих битов в двоичном представлении числа N;
2. Закодировать L с помощью гамма-кода Элиаса;
3. Дописать к L справа двоичное представление числа N без старшей единицы.
Декодирование
1. Сосчитать M — количество нулей во входном потоке до первой единицы;
2. Не включая единицу считать M битов. Считанное число в сумме с
дает L;3. Далее идут L — 1 младших битов числа N. Считать их и к считанному числу прибавить
.Примеры
Пример кодирования числа 10
1. В двоичном представлении числа N = 10 =
4 значащих бита (L = 4);2. В двоичном представлении числа L = 4 =
3 значащих бита (M = 3);3. Пишем M — 1 ноль и одну единицу 001;
4. Дописываем справа биты числа L без старшей единицы 00100;
5. Дописываем с правой стороны биты числа N без старшей единицы 00100010.
Пример декодирования последовательности битов 00100010
1. Считаем количество нулей до первой единицы во входном потоке (M = 2);
2. Читаем из потока следующие M бит (00). Это дает нам L =
+ = 4;3. Читаем из потока следующие L — 1 бит (010). N =
+ = 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" тут обозначены биты мантиссы без старшей единицы.
Для диапазона [
, - 1 ] коды формируются следующим образом:Гамма-код: 00..(К раз)..01x..(К раз)..x; длина
бит;Дельта-код:
раз)...nx..(K раз)..x; длина: бит, где L = - целая часть логарифма числа (K+1) по основанию 2; n - биты, относящиеся к записи экспоненты дельта-кода, их число .