Гамма-, дельта- и омега-код Элиаса — различия между версиями
Анна (обсуждение | вклад) (→Разделение мантисс и экспонент) |
Анна (обсуждение | вклад) (→Разделение мантисс и экспонент) |
||
Строка 17: | Строка 17: | ||
Методы данной группы являются трансформирующими и поточными, то есть могут применяться даже в том случае, когда объем входных данных заранее не известен. В общем случае скорость работы компрессора (содержащего прямое, «сжимающее» преобразование) равна скорости декомпрессора (реализующего обратное, «разжимающее» преобразование) и зависит только от объема исходных данных. Памяти потребуется всего несколько байтов. | Методы данной группы являются трансформирующими и поточными, то есть могут применяться даже в том случае, когда объем входных данных заранее не известен. В общем случае скорость работы компрессора (содержащего прямое, «сжимающее» преобразование) равна скорости декомпрессора (реализующего обратное, «разжимающее» преобразование) и зависит только от объема исходных данных. Памяти потребуется всего несколько байтов. | ||
− | В самом простом случае под запись экспонент и мантисс отводится фиксированное число битов: <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> {{---}} число битов в записи исходного числа. |
Этот первый из четырех вариантов метода условно обозначим | Этот первый из четырех вариантов метода условно обозначим |
Версия 20:56, 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)
Определение: |
Унарное представление числа n (англ. unary code) — n подряд идущих единиц, заканчивающихся контрольным нулем (иногда наоборот: n нулей, за которыми следует контрольная единица). Более наглядно унарные коды можно представить в виде двоичного дерева, которое устроено следующим образом: каждому ребру, ведущему из вершины к правому ребенку, соответствует единица, иначе ноль, причем левый ребенок уже не имеет детей. Например, если нужно закодировать число m, нужно m раз пройти по правым вершинам и затем остановиться на левой. |
Например, унарный код нуля — 0, единицы — 10, двойки — 110 и т. д.
Гамма-код Элиаса
Определение: |
Гамма-код Элиаса (англ. Elias gamma code) — это универсальный код для кодирования положительных целых чисел, разработанный Питером Элиасом. Он обычно используется при кодировании целых чисел, максимальное значение которых не может быть определено заранее, или чтобы сжать данные, в которых маленькие значения встречаются более часто, чем большие. |
Алгоритм построения гамма-кода Элиаса
Способ первый:
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, …).
Дельта-код Элиаса
Определение: |
Дельта-код Элиаса (англ. Elias delta code) — это универсальный код для кодирования положительных целых чисел, разработанный Питером Элиасом. Как далее будет видно, дельта-код с некоторого числа короче гамма-кода. |
Алгоритм построения дельта-кода Элиаса
Способ первый:
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; длина
бит;Дельта-код: n...(
раз)...nx..(K раз)..x; длина: бит, где L = - целая часть логарифма числа (K+1) по основанию 2; n - биты, относящиеся к записи экспоненты дельта-кода, их число .Единственное отличие между гамма- и дельта-кодами состоит в том, что в гамма-кодах экспоненты записываются в унарном виде, а в дельта-кодах к ним еще раз применяется гамма-кодирование.
Можно видеть, что для чисел 2, 3, 8…15 дельта-код длиннее гамма-кода, для чисел 1, 4…7, 16…31 длина дельта-кода совпадает с длиной гамма-кода, для всех остальных чисел дельта-код короче гамма-кода.
Омега-код Элиаса
Определение: |
Омега-код Элиаса (англ. Elias omega code) — — это универсальный код для кодирования положительных целых чисел, разработанный Питером Элиасом. Так же, как гамма- и дельта-код Элиаса, он приписывает к началу целого числа порядок его величины в универсальном коде. Однако, в отличие от двух других указанных кодов, омега-код рекурсивно кодирует префикс, именно поэтому он также известен, как рекурсивный код Элиаса. |
Омега-кодирование используется в приложениях, где самое большое кодируемое значение неизвестно заранее, или для сжатия данных, в которых маленькие значения встречаются намного чаще, чем большие.
Данные коды состоят из последовательности групп длинной
бит, которые начинаются (слева) с бита 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 (
− 1) — 1 группа;3. 4 ... 15 (
− 1) — 2 группы;4. 16 ... 65536 (
− 1) — 3 группы;5. 65536 ...
− 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 |
Ссылки
- Д. Ватолин, Ратушняк, М. Смирнов, В. Юкин "Методы сжатия данных"
- Кодирование целых чисел
- Гамма-код Элиаса - Википедия
- Дельта-код Элиаса - Википедия
- Омега-код Элиаса - Википедия