Вероятностные методы сжатия

Согласно методу Шеннона-Фано для каждого символа формируется битовый код, причем символы с различными частостями появления имеют коды различной длины [16]. Чем меньше частость появления символов в файле, тем больше размер его битового кода. Соответственно, чаще появляющийся символ имеет меньший размер кода.

Код строится следующим образом. Все символы, встречающиеся в файле, выписывают в таблицу в порядке убывания частости их появления. Затем их разделяют на две группы так, чтобы в каждой из них были примерно равные суммы частостей символов. Первые биты кодов всех символов одной половины устанавливаются в 0, а второй – в 1. После этого каждую группу делят еще раз пополам и так до тех пор, пока в каждой группе не останется по одному символу. Допустим, файл состоит из некоторой символьной строки aaaaaaaaaabbbbbbbbccccccdddddeeeefff, тогда каждый символ этой строки можно закодировать так, как показано в табл. 8.1.

Таблица 8.1

Пример построения кода Шеннона – Фано

Можно видеть, что если раньше каждый символ кодировался 8 битами, то теперь требуется максимум три бита.

Однако способ Шеннона-Фано не всегда приводит к построению однозначного кода. Более удачен в данном отношении метод Хаффмена, позволяющий однозначно построить код с наименьшей средней длиной, приходящейся на символ.

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

Процесс кодирования по методу Хаффмена поясняется табл. 8.2. Для составления кода, соответствующего данному символу, необходимо проследить путь перехода знака по строкам и столбцам таблицы кода.

Таблица 8.2

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

Символ	Частость появления			Кодовое слово
c			22		32	42	58
e						32
h				20		26
i			16
a			16	16
k		10	10
m		6
b

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

Решением этой проблемы является статистический анализ кодируемых данных, выполняемый в ходе первого прохода по данным, и составление на его основе кодового дерева. Собственно кодирование при этом выполняется вторым проходом.

Существует, правда, динамическая версия сжатия Хаффмена, которая может строить дерево Хаффмена "на лету" во время чтения и активного сжатия. Дерево постоянно обновляется, чтобы отражать изменения вероятностей входных данных. Однако и она на практике обладает серьезными ограничениями и недостатками и, кроме того, обеспечивает меньшую эффективность сжатия.

Еще один недостаток кодов Хаффмена - это то, что минимальная длина кодового слова для них не может быть меньше единицы, тогда как энтропия сообщения вполне может составлять и 0,1, и 0,01 бит/букву. В этом случае код Хаффмена становится существенно избыточным. Проблема решается применением алгоритма к блокам символов, но тогда усложняется процедура кодирования/декодирования и значительно расширяется кодовое дерево, которое нужно в конечном итоге сохранять вместе с кодом.

Наконец, код Хаффмена обеспечивает среднюю длину кода, совпадающую с энтропией, только в том случае, когда вероятности символов источника являются целыми отрицательными степенями двойки: 1/2 = 0,5; 1/4 = 0,25; 1/8 = 0,125; 1/16 = 0,0625 и т.д. На практике же такая ситуация встречается очень редко или может быть создана блокированием символов со всеми вытекающими отсюда последствиями.