Материал: Методические указания к выполнению курсовой работы по дисциплине «Теория информации» для студентов специальности «Компьютерная безопасность». Поздышева О.В., Остапенко А.Г

8

( ) = − ∑ log2 =

=1

= −(2 0,25 log2 0,25 + 2 0,15

log2 0,15 + 4 0,05 log2 0,05) = 2,7 бит

= (̅) = ,, = .

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

2.2. Метод кодирования Хаффмана

Алгоритм Хаффмана изящно реализует общую идею статистического кодирования с использованием префиксных множеств и работает следующим образом [2]:

1. Выписываем в ряд все символы алфавита в порядке возрастания или убывания вероятности их появления в тексте.

2.Последовательно объединяем два символа с наименьшими вероятностями появления в новый составной символ, вероятность появления которого полагаем равной сумме вероятностей составляющих его символов. В конце концов построим дерево, каждый узел которого имеет суммарную вероятность всех узлов, находящихся ниже него.

3. Прослеживаем путь к каждому листу дерева, помечая направление к каждому узлу (например, направо - 1, налево – 0) . Полученная последовательность дает кодовое слово, соответствующее каждому символу.

24

Этот метод всегда дает оптимальное кодирование в отличие от предыдущего, так как получаемая средняя длина кодового слова является минимальной.

Буквы алфавита сообщения располагают в порядке убывания вероятностей(для букв русского алфавита - см. приложение 1). Две последние буквы объединяют в один составной символ, которому приписывают суммарную вероятность. Далее заново переупорядочивают символы и снова объединяют пару с наименьшими вероятностями. Продолжают эту процедуру до тех пор, пока все значения не будут объединены. Это называется редукцией. Затем строится кодовое дерево из точки, соответствующей вероятности 1 (это корень дерева), причем ребрам с большей вероятностью присваивают 1,а с меньшей – 0. Двигаясь по кодовому дереву от корня к оконечному узлу, можно записать кодовое слово для каждой буквы исходного алфавита.

Пример 3.

Расположим буквы алфавита А1 в порядке убывания их вероятностей и подвергнем сжатию алфавит А1; при этом мы придём к алфавиту А2, который получается из первоначального алфавитаА с помощью двукратного сжатия (а из алфавита А1 ─ с помощью простого или однократного сжатия). Ясно, что алфавит А2 будет содержать уже всего n-2 буквы. Продолжая эту процедуру, мы будем приходить к всё более коротким алфавитам; после (n-2)- кратного сжатия мы придём к алфавиту Аn-2, содержащему уже всего две буквы.

Вот, например, как преобразуется с помощью последовательных сжатий рассмотренный выше алфавит, содержащий 6 букв, вероятности которых равны

x1 = 0,4;x2 = 0,2;x3 = 0,2;x4 = 0,1;x5 = 0,05 и x6 = 0,05(табл. 2).

25

Таблица 2

Преобразование алфавита с помощью последовательных сжатий

Условимся теперь приписывать двум буквам последнего алфавита Аn-2 кодовые обозначения 1 и 0. Далее, если кодовые обозначения уже приписаны всем буквам алфавита Аj, то буквам «предыдущего» алфавита Аj-1 (где, разумеется, А1-1 = А0 ─это исходный алфавит А), сохранившимся и в алфавите Аj, мы пишем те же кодовые обозначения, которые они имели в алфавите Аj-1; двум же буквам а’ и а’’ алфавита Аj, «слившимся» в одну букву b алфавита Аj-1, мы припишем обозначения, получившиеся из кодового обозначения буквы b добавлением цифр 1 и 0 в конце (Табл. 3).

26

Таблица 3

Алгоритм приписывания «0» и «1»

Легко видеть, что из самого построения получаемого таким образом кода Хаффмана вытекает, что он удовлетворяет общему условию: никакое кодовое обозначение не является здесь началом другого, более длинного кодового обозначения.

Заметим ещё, что кодирование некоторого алфавита по методу Хаффмана (так же, впрочем, как и по методу Шеннона − Фано) не является однозначной процедурой.

Так, например, на любом этапе построения кода можно, разумеется, заменить цифру 1 на цифру 0 и наоборот; при этом мы получим два разных кода (отличающихся весьма несущественно друг от друга). Но помимо того в некоторых случаях можно построить и несколько существенно различающихся кодов Хаффмана; так, например, в разобранном выше примере можно строить код и в соответствии со следующей таблицей (табл. 4):

27

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

1 · 0,4 + 2 · 0,2 + 3 · 0,2 + 4 · 0,1 + 5 · (0,05 + 0,05) = 2,3, а во втором ─ равно 1 · (0,4 + 0,2 + 0,2) + 3 · 0,1 + 4 · (0,05 + 0,05) = 2,3.

28