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

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

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