Сжатие данных производится в два этапа. На первом этапе считываются данные, которые должны подвергнуться сжатию; на втором определяется частота встречаемости отдельных байтов данных, которые могут принимать значения от 0 до 255.
Рассмотрим пример. Пусть требуется сжать словосочетание:
ПРОГРАММИРОВАНИЕ КОМПРЕССИИ БЕЗ ПОТЕРЬ
До сжатия данных каждая буква представляется числом, которое лежит между 0 и 255. Если применяется так называемая альтернативная кодовая таблица (содержащая знаки русского алфавита), то буквы имеют значения между 128 и 159 (а-я), между 160 и 175 (а-п) и между 224 и 239 (Р-я), а пробел - значение 32. Запись приведенного словосочетания потребовала бы 38 байт - по одному байту на букву или пробел. Чтобы снизить размеры файла при записи, определим вначале частоту встречаемости отдельных букв:
|
|
Очевидно, что наиболее часто встречается буква Р. Другие буквы встречаются реже, а многие вообще не встречаются. Конечно, весьма расточительно кодировать каждую букву одинаковым числом бит. Было бы гораздо экономичнее кодировать наиболее часто встречающиеся буквы короткими кодами, например, 0 или 1. При этом на кодирование затрачивался бы всего один бит, т.е. в 8 раз меньше, чем согласно использованной кодовой таблице. Соответственно, по мере снижения частоты букв для их кодирования можно было бы использовать все более длинные численные значения. В этом заключается принцип кодирования по Хаффману.
После определения частоты встречаемости знаков строится схема кодирования, в которой наиболее часто встречаемые символы кодируются меньшим числом бит, и, наоборот, символы, частота встречаемости которых меньше, кодируются большим числом бит. Задача состоит в том, чтобы найти эффективную схему кодирования /декодирования. В сжатый файл необходимо записать поток битов и информацию о том, как этот поток следует интерпретировать. В этом потоке битов отдельные знаки представляются уже не фиксированным, а переменным числом битов, причем количество кодирующих битов уменьшается с ростом частоты встречаемости символа.
Рассмотрим пример реализации алгоритма кодирования.
Построим таблицу частоты повторяемости символов, деля число повторений символа на длину сообщения (38):
Произведем ряд последовательных преобразований исходной таблицы, складывая строки с наименьшей частотой и проводя их сортировку по убыванию:
|
|
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
Теперь, пользуясь таблицами в обратной последовательности, построим дерево кодирования. Из вершины начинаются две ветви, соответствующие значениям вероятности появления в сообщении данной группы символов.
Ветви помечаются значениями 0 (левая, с меньшим значением слагаемого вероятности) и 1 (правая, с большим). Дерево закончится каждым символом алфавита сообщения, а значения, приписанные ветвям дерева на пути от вершины к данному символу, образуют двоичный код данного символа.
 
|
По результатам данных операций можно составить таблицу кодирования.
|
Подсчитаем полученную степень сжатия, умножая длину кода на сумму символов, кодируемых кодом данной длины:
3(5+4+4+4) + 4(3+3+3+2+2) +5(1+1+1+1) + 6(1+1+1+1) = 147 бит (18.4 байт)
Таким образом, имеем коэффициент сжатия К=38/19=2
Проверим декодирование сообщения. Например, кодируется слово ПРОГРАММА:
При декодировании просмотр начинается слева на выявление возможных 3-битовых комбинаций, затем 4-, 5-, и 6-. В нашем случае комбинация 111 отсутствует в кодовой таблице, а в списке 4-битовых имеется комбинация 1110, которая декодируется как буква П. Просмотр следующих битов в сообщении производится аналогичным образом.
Граница применимости этой схемы сжатия очевидна: данные можно сжимать, только если отдельные элементы данных различаются по частоте встречаемости. Если же элементы данных распределены статистически равномерно, то сжатие невозможно.
Применительно к растровой графике: если изображение имеет равномерно окрашенные области – выигрыш будет значительным.
Задание
Закодируйте по алгоритму Хаффмана строку с вашим именем, отчеством, фамилией, датой и местом рождения (например, «Иванова Наталья Николаевна, 1 января 1990 года, город Тверь»).
При кодировании не округляйте частоты менее, чем четыре знака после запятой – сокращение точности понижает эффективность кодирования.
Подсчитайте коэффициент сжатия.
Наберите эту же строку в редакторе «Блокнот» и сохраните текст в txt-формате (количество байт в файле должно в точности соответствовать числу знаков – букв, цифр и служебных символов – в строке.
Примените к файлу любой архиватор и сравните его степень сжатия с алгоритмом Хаффмана.
