Принцип кодирования по хаффману

Сжатие данных производится в два этапа. На первом этапе считываются данные, которые должны подвергнуться сжатию; на втором определяется частота встречаемости отдельных байтов данных, которые могут принимать значения от 0 до 255.

Рассмотрим пример. Пусть требуется сжать словосочетание:

ПРОГРАММИРОВАНИЕ КОМПРЕССИИ БЕЗ ПОТЕРЬ

До сжатия данных каждая буква представляется числом, которое лежит между 0 и 255. Если применяется так называемая альтернативная кодовая таблица (содержащая знаки русского алфавита), то буквы имеют значения между 128 и 159 (а-я), между 160 и 175 (а-п) и между 224 и 239 (Р-я), а пробел - значение 32. Запись приведенного словосочетания потребовала бы 38 байт - по одному байту на букву или пробел. Чтобы снизить размеры файла при записи, определим вначале частоту встречаемости отдельных букв:

Буква Частота П Р О Г А М И В Н Е К С Б З T Ь Пробел

№ п/п Символ Повтор Частота Р 0.132 О 0.105 И 0.105 Е 0.105 П 0.079 М 0.079 ПРОБЕЛ 0.079 А 0.0526 С 0.0526 Г 0.0263 В 0.0263 К 0.0263 Б 0.0263 З 0.0263 Т 0.0263 Ь 0.0263 Н 0.0263

Очевидно, что наиболее часто встречается буква Р. Другие буквы встречаются реже, а многие вообще не встречаются. Конечно, весьма расточительно кодировать каждую букву одинаковым числом бит. Было бы гораздо экономичнее кодировать наиболее часто встречающиеся буквы короткими кодами, например, 0 или 1. При этом на кодирование затрачивался бы всего один бит, т.е. в 8 раз меньше, чем согласно использованной кодовой таблице. Соответственно, по мере снижения частоты букв для их кодирования можно было бы использовать все более длинные численные значения. В этом заключается принцип кодирования по Хаффману.

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

Рассмотрим пример реализации алгоритма кодирования.

Построим таблицу частоты повторяемости символов, деля число повторений символа на длину сообщения (38):

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

Шаг 1 0.132 0.105 0.105 0.105 0.079 0.079 0.079 0.0526 0.0526 10,11 0.0526 12,13 0.0526 14,15 0.0526 16,17 0.0526	Шаг 2 0.132 0.105 0.105 0.105 8,9 0.105 10,11,12,13 0.105 14,15,16,17 0.105 0.079 0.079 0.079	Шаг 3 6,7 0.158 0.132 0.105 0.105 0.105 8,9 0.105 10,11,12,13 0.105 14,15,16,17 0.105 0.079
Шаг 4 5,14,15,16,17 0.184 6,7 0.158 0.132 0.105 0.105 0.105 8,9 0.105 10,11,12,13 0.105	Шаг 5 8,9,10,11,12,13 0.210 3,4 0.210 5,14,15,16,17 0.184 6,7 0.158 0.132 0.105	Шаг 6 1,2 0.237 8,9,10,11,12,13 0.210 3,4 0.210 5,14,15,16,17 0.184 6,7 0.158
Шаг 7 5,6,7,14,15,16,17 0.342 1,2 0.237 8,9,10,11,12,13 0.210 3,4 0.210	Шаг 8 3,4,8,9,10,11,12,13 0.420 5,6,7,14,15,16,17 0.342 1,2 0.237	Шаг 9 1,2,5,6,7,14,15,16,17 0.579 3,4,8,9,10,11,12,13 0.420

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

Ветви помечаются значениями 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-формате (количество байт в файле должно в точности соответствовать числу знаков – букв, цифр и служебных символов – в строке.

Примените к файлу любой архиватор и сравните его степень сжатия с алгоритмом Хаффмана.