Приложение 3. СТАТИСТИЧЕСКОЕ КОДИРОВАНИЕ

В этом приложении описываются два основных метода статистического кодирования: Шеннона-Фано и Хаффмена.

Рис. 1 иллюстрирует метод кодирования Шеннона-Фано. Согласно этому методу, символы, образующие исходное сообщение, вместе с их вероятностями появления представляются в виде таблицы в порядке убывания вероятностей. Затем символы делятся на две группы с наиболее близкими друг к другу суммарными вероятностями. Первым разрядам кодовых слов первой группы присваивается значение нуль, а второй группы - единица. В результате последующего деления групп символов на подгруппы определяются следующие разряды кодовых слов. Средняя длина кодовых слов и энтропия источника сообщений указаны на рисунке.

Рис. 1. Пример кодирования методом Шеннона-Фано.

Метод кодирования Хаффмена поясняется примером, приведенным на рис. 2. Два символа с наименьшими вероятностями объединяются в узел кодового дерева. Вероятности символов суммируются и приписываются узлу. Затем объединяются следующие символы или узлы с наименьшей вероятностью, как показано на рисунке. Этот процесс продолжается, пока ветви дерева не сойдутся к одному узлу - вершине. Ветви дерева, сходящиеся к узлу, обозначаются нулем и единицей. Чтобы получить кодовое слово, соответствующее данному символу, идут по дереву в обратном направлении от вершины к символу, записывая нули или единицы, которыми обозначены пройденные ветви.

Рис. 2. Пример кодирования методом Хаффмена.

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