Файл: Технологии программирования (Возникновение теории кодирования).pdf

2. Основные методы кодирования данных

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

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

Каждому целому числу из определенного диапазона ставится в соответствие свое кодовое слово. Поэтому эту группу методов также называют представлением целых чисел (representation of integers).

Основная идея кодирования целых чисел: отдельно кодировать порядок значения элемента («экспоненту» ) и отдельно – значащие цифры значения («мантиссу» i).

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

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

Пример:

Двоичное число 000001101
Порядок равен 4, мантисса – 1101

Рассмотрим две группы методов кодирования целых чисел. Условно их можно обозначить так:

• Fixed + Variable (фиксированная длина порядка + переменная длина мантиссы)
• Variable + Variable (переменная длина порядка + переменная длина мантиссы)

В кодах класса Fixed + Variable под запись значения порядка числа отводится фиксированное количество бит, а значение порядка числа определяет, сколько бит потребуется под запись мантиссы.

Для кодирования целого числа необходимо произвести с числом две операции:

• определение порядка числа
• выделение бит мантиссы

Можно также хранить в памяти заранее построенную таблицу кодовых слов и по ней получать код числа.

2.1.1 Код класса Fixed + Variable

Пусть R = 15 – количество бит исходного числа.

Отведем E = 4 бита под порядок, т.к. R ≤ 2⁴.

При записи мантиссы можно сэкономить 1 бит: не писать первую единицу, т.к. это всегда будет только единица.

Таким образом, количество бит мантиссы меньше на один бит, чем значение порядка числа.

Таблица 1

Коды чисел класса Fixed + Variable

2.1.2 Код класса Variable + Variable

В качестве кода числа берется двоичная последовательность, построенная следующим образом: несколько нулей (количество нулей равно значению порядка числа), затем мантисса переменной длины.

Таблица 2

Коды чисел класса Variable + Variable

Если в рассмотренном выше коде исключить кодовое слово для нуля, то можно уменьшить длины кодовых слов на 1 бит, убрав первый нуль во всех кодовых словах. Таким образом строится гамма-код Элиаса (γ-код Элиаса).

Таблица 3

γ-код Элиаса

Другим примером кода класса Variable + Variable является омега-код Элиаса (ω-код Элиаса).

В нем первое значение (кодовое слово для единицы) задается отдельно. Другие кодовые слова состоят из последовательности групп длиной L₁ L₂ …L_m , начинающихся с единицы.

Конец всей последовательности задается нулевым битом.

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

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

Таблица 4

ω-код Элиаса

В омега-коде Элиаса (P. Elias):

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

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

• Рассмотренные типы кодов могут быть эффективны в следующих случаях:
• Вероятности чисел убывают с ростом значений элементов и их распределение близко к такому: P(x) ≥ P(x+1), при любом x, т.е. маленькие числа встречаются чаще, чем большие.
• Диапазон значений входных элементов не ограничен или неизвестен.
  Например, при кодировании 32-битовых чисел реально большинство чисел маленькие, но могут быть и большие.
• При использовании в составе других схем кодирования, например, кодировании длин серий.

2.2 Кодирование длин серий

Метод кодирования длин серий (RLE), предложенный П. Элиасом (P.Elias), при построении использует коды целых чисел. Входной поток для кодирования рассматривается как последовательность из нулей и единиц.

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

Последовательность одинаковых элементов называется серией, количество элементов в ней – длиной серии.

2.2.1 Пример кодирования длин серий

Входную последовательность (31 бит) можно разбить на серии, а затем закодировать их длины.

000000 1 00000 1 0000000 1 1 00000000 1

Длины серий нулей: 6 5 7 0 8

Используем, например, γ-код Элиаса.

Поскольку в γ-коде Элиаса нет кодового слова для нуля,то будем кодировать длину серии +1: 65708 ⇒ 76819

7 6 8 1 9 ⇒ 00111 00110 0001000 1 0001001

Длина полученной кодовой последовательности 25 бит.

Метод длин серий актуален для кодирования данных, в которых есть длинные последовательности одинаковых бит. В нашем примере, если P(0)>>P(1).

2.3 Код Хафмана

Код Хаффмана (англ. Huffman's algorithm) — алгоритм оптимального префиксного кодирования алфавита. Разработан в 1952 году аспирантом Массачусетского технологического института Дэвидом Хаффманом при написании им курсовой работы. [7]

Кодирование Хаффмана широко применяется при сжатии данных, в том числе при сжатии фото- и видеоизображений (JPEG, MPEG), в популярных архиваторах (PKZIP, LZH и др.), в протоколах передачи данных HTTP (Deflate), MNP5 и MNP7 и других. [3]

В 2013 году была предложена модификация алгоритма Хаффмана, позволяющая кодировать символы дробным количеством бит — ANS. На базе данной модификации реализованы алгоритмы сжатия Zstandard (Zstd, Facebook, 2015—2016) и LZFSE[fr] (Apple, OS X 10.11, iOS 9, 2016).

2.3.1 Определение

Пусть A={a₁,a₂,…,a_n} — алфавит из n различных символов, W={w₁,w₂,…,w_n} — соответствующий ему набор положительных целых весов. Тогда набор бинарных кодов C={c₁,c₂,…,c_n}, где c_i является кодом для символа a_i, такой, что:

c_i не является префиксом для c_j, при i≠j,

cумма ∑_i∈[1,n]w_i⋅|c_i| минимальна (|c_i| — длина кода c_i),

называется кодом Хаффмана.[7]

2.3.2 Алгоритм построения бинарного кода Хаффмана

Построение кода Хаффмана сводится к построению соответствующего бинарного дерева по следующему алгоритму:

1. Составим список кодируемых символов, при этом будем рассматривать один символ как дерево, состоящее из одного элемента c весом, равным частоте появления символа в строке.
2. Из списка выберем два узла с наименьшим весом.
3. Сформируем новый узел с весом, равным сумме весов выбранных узлов, и присоединим к нему два выбранных узла в качестве детей.
4. Добавим к списку только что сформированный узел вместо двух объединенных узлов.
5. Если в списке больше одного узла, то повторим пункты со второго по пятый.

2.3.3 Время работы

Если сортировать элементы после каждого суммирования или использовать приоритетную очередь, то алгоритм будет работать за время O(N log N).Такую асимптотику можно улучшить до O(N), используя обычные массивы.

2.3.4 Пример выполнения алгоритма

Закодируем слово abracadabra. Тогда алфавит будет A={a,b,r,c,d} а набор весов (частота появления символов алфавита в кодируемом слове) W={5,2,2,1,1}. Графическое представление можно посмотреть в приложении на рисунке 4.