12 Кодирование и сжатие информаци

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

12.1 Коды переменной длины

Первое правило построения кодов переменной длины, состоит в том, что короткие коды следует присваивать часто встречающимся символам, а длинные – редко встречающимся. При этом коды следует назначать так, чтобы из можно было декодировать однозначно, а не двусмысленно. Например, рассмотрим четыре символа a₁,a₂,a₃,a₄. Если они появляются в сообщении с равной вероятностью (p=0,25), то присвоим им четыре двухбитовых кода: 00, 01, 10, 11. Все вероятности равны, поэтому коды переменной длины не сожмут данные. Для каждого символа с коротким кодом найдётся символ с длинным кодом и среднее число битов на символ будет не меньше 2. Избыточность данных равновероятными символами равна 0, и строку таких символов невозможно сжать с помощью кодов переменной длины (или какого-либо другого метода).

Пусть теперь эти четыре символа появляются с разными вероятностями (см. табл. 12.1). В этом случае имеется избыточность, которую можно удалить с помощью кодов переменной длины и сжать данные так, чтобы потребуется меньше 2 бит на символ. Наименьшее среднее число бит на символ равно 1,57, то есть энтропии этого множества символов.

В таблице 12.1 предложен код Код_1, который присваивает самому часто встречающемуся символу самый короткий код. Среднее число бит на символ равно 1,77. Это число близко к теоретическому минимуму.

Таблица 12.1

Символ	Вероятность	Код_1	Код_2
a1	0,49	1	1
a2	0,25	01	01
a3	0,25	010	000
a4	0,01	001	001

Рассмотрим последовательность из 20 символов

a₁ a₃ a₂ a₁ a₃ a₃ a₄ a₂ a₁ a₁ a₂ a₂ a₁ a₁ a₃ a₁ a₁ a₃ a₁,

в которой четыре символа появляются, примерно, с одинаковыми частотами. Этой строке будет соответствовать кодовое слово длины 37 бит:

1|010|01|1|010|010|001|01|1|1|01|01|1|1|010|1|1|01|010|1.

Среднее число бит на символ составляет 1,85, что не слишком далеко от вычисленной минимальной средней длины. Однако если попытаться декодировать последовательность, то окажется, что Код_1 имеет существенный недостаток. Первый бит кодового слова равен 1, поэтому первым символом последовательности может быть только a₁, так как код никакого другого символа не начинается с 1. Следующий символ равен 0, но коды для символов a₂,a₃,a₄ все начинаются с 0, поэтому декодер должен считать следующий символ. Он равен 1, но коды для a₂ и a₃ оба имеют в начале 01. Поэтому декодер не знает, как действовать дальше: декодировать строку как 1|010|01…, то есть a₁a₃a₂…, или как 1|01|001…, то есть a₁a₂a₄.... Дальнейшие биты последовательности не могут исправить положения. Поэтому Код­_1 является двусмысленным. От этого недостатка свободен Код_2.

Код_2 обладает так называемым префиксным свойством, которое можно сформулировать так: если некоторая последовательность битов выбрана в качестве кода какого-либо символа, то ни один код какого-либо другого символа не должен иметь в начале эту последовательность (код символа не может быть префиксом кода другого символа). Если строка 01 является кодом для a₂, то другие коды не должны начинаться с 01. Поэтому коды для a₃ и a₄ должны начинаться с 00. Естественно для этого выбрать 000 и 001.

Следовательно, выбирая множество кодов переменной длины необходимо соблюдать два принципа: 1) следует назначать более короткие кодовые последовательности часто встречающимся символам; 2) полученные коды должны обладать префиксным свойством. Следуя этим принципам можно построить короткие, однозначно декодируемые коды, но необязательно наилучшие (то есть самые короткие) коды. В дополнение к этим принципам необходим алгоритм, который всегда порождает множество самых коротких кодов (имеющих наименьшую среднюю длину). Исходными данными этого алгоритма должны быть частоты (или вероятности) символов алфавита. Таким алгоритмом является кодирование по методу Хаффмана.

Следует отметить, что не только статистические методы компрессии используют коды переменной длины для кодирования индивидуальных символов. Такой подход используется, в частности, и в арифметическом кодировании.

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

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

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