Первая страница / Теория / Кодирование /

Кодирование целых чисел

Голосование: 8, 6

Введение

Компактное представление информации — очень важная проблема в областях, где приходится работать со сжатием данных. Цель — сжатие потока R-битовых элементов. В общем случае никаких предположений о свойствах значений элементов не делается, поэтому можно говорить об описании способов представления целых чисел (Representation of Integers).

Основная идея состоит в том, чтобы отдельно хранить порядок значения элемента Xi («экспоненту» Ei) и отдельно — значащие цифры значения («мантиссу» Mi).

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

Рассматриваемые в статье коды

Некоторые обозначения

  • α(n) — унарное представление числа nn подряд идущих единиц, заканчивающихся контрольным нулем (иногда наоборот: n нулей, за которыми следует контрольная единица). Более наглядно унарные коды можно представить в виде двоичного дерева, которое устроено следующим образом: каждому ребру, ведущему из вершины к правому ребенку, соответствует единица, иначе ноль, причем левый ребенок уже не имеет детей. Например, если нужно закодировать число m, нужно m раз пройти по правым вершинам и затем остановиться на левой.
    Унарное представление числа n
  • β(n) — обычное представление числа n в двоичной системе cчисления.
  • часто при кодировании целого числа x записывают порядок значения элемента (называемый «экспонентой» E) и отдельно значащие цифры («мантиссу» M).

Гамма-коды Левенштейна (Levenstein γ codes)

Данный код для числа n получается путем обращения последовательности битов в двоичной записи этого числа и добавления перед каждым битом, кроме последнего, флагового (flag bit) бита 0. Последним флаговым битом является бит 1, который совпадает с самым старшим битом в исходной двоичной записи числа n.

Рассмотрим несколько примеров кодов Левенштейна:

n γ code
1 1
5 01001
13 0100011
63 01010101011
129 010000000000001

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

Гамма- и дельта-коды Элиаса (Elias γ and δ codes)

Данный код формируется в зависимости от диапазона числа. Допустим, кодируется число n, которое принадлежит диапазону [2k, 2k+1−1], тогда гамма-кодом Элиаса для числа n будет его обыкновенное бинарное представление β(n) без старшей единицы, дополненное слева унарным представлением числа k: γ(n) = α(n) : β(n−2k).

Дельта-кодами Элиаса называются гамма-коды, в которых унарная часть также закодирована гамма-кодами. То есть для получения дельта-кода из гамма-кода, нужно лишь применить гамма-кодирование к унарной части гамма-кода (экспоненте): δ(n) = γ(α(n)) : β(n−2k).

В данных кодах унарную часть принято записывать нулями, завершающимися контрольной единицей.

Рассмотрим несколько примеров γ и δ кодов Элиаса:

n γ code δ code
0 - 1
1 1 0 1
2..3 01x 0 01x
4..7 001xx 0 001xx
8..15 0001xxx 0 0001xxx
16..31 00001xxxx 0 00001xxxx
32..63 000001xxxxx 0 000001xxxxx

Каждый символ x соответствует биту в записи β(n−2floor(logn)).

Коды Голомба (Golomb codes)

Коды Голомба имеют параметр m. Если m — степень 2, то кодом для n будет простое соединение α(n div m) как префикса и двоичного представления β(n mod m) в logm битах (весь код будет иметь вид α(n div m) : β(n mod m)). Для других значений m, возьмем наименьшее положительное k такое, что 2k ≥ 2m. Словарь содержит ровно m кодов для каждого слова длины не меньше k, плюс 2k−1m кодов длины k−1.

Пусть j = 2(k−1)m. Бинарное представление первых j кодов представляются (k−1) битами, а следующие m кодов k битами. Большие значения n представляются префиксом α((nj) div m), за которым идет β((nj) mod m+2j) в k битах. Случай степени 2 — это частный случай основного правила.

Таким образом, если j = 2(k−1)m, код Голомба для n с заданным параметром m, дается соединением двух кодов:

Golomb(n,m) = α((nj) div m) : β((nj) mod m+2j)

Рассмотрим несколько примеров кодов Голомба для различного параметра m:

n \ m 1 2 3 4 5
0 0 00 00 000 000
1 10 01 010 001 001
2 110 100 011 010 010
3 1110 101 100 011 0110
4 11110 1100 1010 1000 0111
5 111110 1101 1011 1001 1000
6 1111110 11100 1100 1010 1001
7 11111110 11101 11010 1011 1010
8 111111110 111100 11011 11000 10110
9 1111111110 111101 11100 11001 10111
10 11111111110 1111100 111010 11010 11000
11 111111111110 1111101 111011 11011 11001
12 1111111111110 11111100 111100 111000 11010
13 11111111111110 11111101 1111010 111001 110110
14 111111111111110 111111100 1111011 111010 110111
15 1111111111111110 111111101 1111100 111011 111000
16 11111111111111110 1111111100 11111010 1111000 111001
17 111111111111111110 1111111101 11111011 1111001 111010

Ниже приводится таблица, поясняющая устройство данных кодов: как именно двоичное представление остатка (мантисса) следует за унарным кодом (экспонентой):

Пример кодов Голомба для m=1,2 и 4

Коды Райса (Rice codes)

Код Райса идентичен коду Голомба, когда m является степенью двойки. На самом деле данные коды имеют параметр k, по которому вычисляется значение m = 2k. Тогда код Райса для числа n с заданным параметром k будет выглядеть следующим образом:

Rice(n,k) = α(n div m) : β(n mod m)

Для числа n данный код представляется в (n ⁄ m + k + 1) битами.

Рассмотрим несколько примеров кодов Райса для различного параметра k:

n \ k 1 2 3 4 5 6
0 0 000 0000 00000 000000 0000000
1 10 001 0001 00001 000001 0000001
2 110 010 0010 00010 000010 0000010
3 1110 011 0011 000011 000011 0000011
4 11110 1000 0100 000100 000100 0000100
5 111110 1001 0101 000101 000101 0000101
6 1111110 1010 0110 000110 000110 0000110
7 11111110 1011 0111 000111 000111 0000111
8 111111110 11000 10000 001000 001000 0001000
9 1111111110 11001 10001 001001 001001 0001001
10 11111111110 11010 10010 001010 001010 0001010
11 111111111110 11011 10011 001011 001011 0001011
12 1111111111110 111000 10100 001100 001100 0001100
13 11111111111110 111001 10101 001101 001101 0001101
14 111111111111110 111010 10110 001110 001110 0001110
15 1111111111111110 111011 10111 001111 001111 0001111

Омега-коды Элиаса и коды Ивэн-Родэ (Elias ω and Even-Rodeh codes)

Данные коды состоят из последовательности групп длинной L1, L2, L3, …, Lm бит, которые начинаются с бита 1. В конце последовательности следует 0. Длина каждой следующей (n+1)-й группы задается значением битов предыдущей n-й группы. Значение битов последней группы является итоговым значением всего кода, то есть всей последовательности групп. В сущности, все первые m−1 групп служат лишь для указания длины последней группы.

В омега-кодах Элиаса длина первой группы — 2 бита. Длина следующей группы на единицу больше значения предыдущей. Первое значение задается отдельно.

В Ивэн-Родэ-кодах длина первой группы — 3 бита, а длина каждой последующей группы равна значению предыдущей. Первые три значения заданы особым образом.

При кодировании формируется сначала последняя группа, следующая непосредственно перед нулем, а потом по очереди восстанавливаются все предыдущие группы одна за другой, пока процесс не будет завершен.

При декодировании, наоборот, группы получаются, начиная с первой, одна за другой, то есть по значению битов уже найденной группы определяется длина последующей и так далее, пока не будет найдена итоговая группа, после которой идет ноль.

Рассмотрим несколько примеров омега-кодов Элиаса и Ивэн-Родэ кодов:

n Elias ω code Even-Rodeh-code
0 - 000
1 0 001
2 10 0 010
3 11 0 011
4 10 100 0 100 0
7 10 111 0 111 0
8 11 1000 0 100 1000 0
15 11 1111 0 100 1111 0
16 10 100 10000 0 101 10000 0
32 10 101 100000 0 110 100000 0
100 10 110 1100100 0 111 1100100 0

Старт-шаг-стоп коды (Start-step-stop codes)

Эти коды определяются тремя параметрами {ijk}. Код определяет серии блоков кодовых слов (код β) возрастающей длины: первый блок с числовой частью длиной i битов, второй — i + j битов, затем — i + 2j битов, и так далее до длины k битов. Группы кодовых слов имеют унарный префикс, дающий номер группы. Таким образом, код {3, 2, 9} имеет кодовые слова с числовой частью 3, 5, 7 и 9 бит и префиксы 0, 10, 110 и 111 (опуская последний 0 в последнем префиксе). Данные коды выглядят так:

Кодовое слово Диапазон
0xxx 0-7
10xxxxx 8-39
110xxxxxxx 40-167
111xxxxxxxxx 168-679

Кодовые значения для {3, 2, 9} start-step-stop кода.

Далее приводится общая формула для восстановления числа по коду, а также алгоритм, позволяющий получить код по заданному числу n.

Восстановление числа n по заданному {ijk}-start-step-stop коду

Пусть дан {ijk}-код и пусть количество единиц в унарной части (экспоненты) равно Q. Тогда число n (закодированное число) равно:

где β — мантисса записанного кода, Dec(x) — функция, переводящая x в десятичную систему счисления.

Получение {ijk}-start-step-stop кода по заданному числу n

Теперь наоборот, пусть задано число n. Для получения его кода необходимо найти такое минимальное положительное число Q0, чтобы выполнялось неравенство:

при этом сам код будет выглядеть так:

α(Q0 − 1) : β(n + 2IQ0 − S).

Замечание

В качестве частных случаев Start-step-stop кодов могут быть получены следующие коды:

{ijk} Диапазон
k, 1, k простой бинарный код для целых чисел
0, 1, ∞ γ-код Элиаса
kk, ∞ γ-код Элиаса по основанию 2k

Коды Фибоначчи (Fibonacci codes)

В данном кодировании исходное число n раскладывается в сумму чисел Фибоначчи fi (f1 = 1; f2 = 2; fi = fi−1 + fi−2). Известно, что любое натуральное число однозначно представимо в виде суммы чисел Фибоначчи. Поэтому можно построить код числа как последовательность битов, каждый из которых указывает на факт наличия в n определенного числа Фибоначчи.

Заметим также, что если в разложении числа n присутствует fi, то в этом разложении не может быть числа fi+1. Поэтому логично для конца кода использовать дополнительную единицу. Тогда две идущие подряд единицы будут означать окончание кодирования текущего числа.

Рассмотрим несколько примеров кодов Фибоначчи:

n \ fi 1 2 3 5 8 13
1 1 (1)        
2 0 1 (1)      
3 0 0 1 (1)    
4 1 0 1 (1)    
5 0 0 0 1 (1)  
6 1 0 0 1 (1)  
7 0 1 0 1 (1)  
8 0 0 0 0 1 (1)

Заключение

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

Литература

  1. Ватолин Д., Ратушняк А., Смирнов М., Юкин В. Методы сжатия данных. — М.: ДИАЛОГ-МИФИ, 2002.
  2. Fenwick P., Punctured Elias Codes for variable-length coding of the integers, Technical Report 137, December 5, 1996.

Евгений Решетников


Дмитрий Шевченко / 2010-06-20 17:48:06

Небольшая опечатка:

"гамма-кодом Элиаса для числа n будет его обыкновенное бинарное представление β(n) без старшей единицы, дополненное слева унарным представлением числа k: γ(n) = α(n) : β(n−2^k)"

надо полагать, нужно α(k) вместо α(n).

Шевченко Дмитрий / 2010-06-20 17:52:14

То же самое и для дельта-кодов Элиаса:

δ(n) = γ(α(k)) : β(n−2^k)

вместо

δ(n) = γ(α(n)) : β(n−2^k).

Дмитрий Шевченко / 2010-06-20 18:22:24

Также хотел бы отметить, что приведенная форма дельта-кодов Элиаса не соответствует приведенным в таблице примерам. Возьмем для примера число 13, для него k = 3.

α(3) = 0001;

δ(n) = γ(α(k)) : β(n−2^k) = γ(1) : 101 = α(0) : β(1 - 2 ^ 0) : 101 = 1 101 (т. к. при удалении ведущей единицы из числа "1" не остается ничего).

Очень похоже, что результат всегда соответствует двоичной записи взятого числа N (в данном случае, 13).

В Википедии есть другая, более вероятная версия дельта-кодов Элиаса:

δ(n) = γ(k + 1) : β(n−2^k),

которая также не соответствует приведенной выше таблице. Да и не ясно, зачем нужен дельта-код, если для положительных чисел каждый раз к гамма-коду прибавляется один лишний нулевой бит слева.

Если я где-то ошибаюсь, пожалуйста, напишите.

Алексей Цыпленков / 2010-06-29 21:47:26

В описании гамма- и дельта-кода Элиаса действительно вместо alpha(n) должно быть alpha(k).

Описание дельта-кода Элиаса верно(статья в Википедии говорит тоже самое), примеры неверны.

Приведенный выше пример для 13 неверен:

бинарный вид мантиссы - 1101,

гамма-код экспоненты имеет вид 00100 ->

гамма-код имеет вид 00100|101

Ваше имя
Email
Текущий день недели (строчными буквами)
Комментарий