Алгоритм Хаффмена реализует общую идею статистического кодирования с использованием префиксных множеств и работает следующим образом:1. Выписываем в ряд все символы алфавита в порядке не возрастания вероятности их появления в тексте.2. Последовательно объединяем два символа с наименьшими вероятностями появления в новый составной символ. Каждому символу из составного символа приписываем: одному «0», а второму «1». Вероятность появления составного символа полагаем равной сумме вероятностей составляющих его символов. Составной символ переставляем в ряде в соответствии с новой суммарной вероятностью. В конце концов, построим дерево, каждый узел которого имеет суммарную вероятность всех узлов, находящихся ниже него.3. Прослеживаем путь к каждому листу дерева, помечая направление к каждому узлу (например, направо - 1, налево - 0). Полученная последовательность дает кодовое слово, соответствующее каждому символу. Построим кодовое дерево для сообщения со следующим алфавитом табл. 8.8. Таблица 8.8. Символы алфавита в порядке не возрастания вероятности их появления в тексте
| |
| |  |
1. Объединяем Е и F как символы с наименьшими вероятностями и приписываем символу Е – «0», а F – «1». Суммарная вероятность двух символов 0,2. Составной символ Е F переставляем в ряде в соответствии с новой суммарной вероятностью.
Продолжение табл.8.8
2. Объединяем С и D как символы с наименьшими вероятностями на данном шаге и приписываем символу С – «0», а D – «1». Суммарная вероятность двух символов 0,25. Составной символ С D переставляем в ряде в соответствии с новой суммарной вероятностью.
Продолжение табл.8.8
3. Объединяем В и Е F как символы с наименьшими вероятностями на данном шаге и приписываем символу В – «0», а Е F – «1». Суммарная вероятность символов 0,4. Составной символ В Е F переставляем в ряде в соответствии с новой суммарной вероятностью.
Продолжение табл.8.8
4. Объединяем А и С D как символы с наименьшими вероятностями на данном шаге и приписываем символу A – «0», а С D – «1». Суммарная вероятность символов 0,6. Составной символ А С D переставляем в ряде в соответствии с новой суммарной вероятностью.
Продолжение табл.8.8
5. На последнем шаге объединяем А С D и B E F и приписываем символу А С D – «0», а B E F – «1». Суммарная вероятность символов 1.
На рис.8.6 представлено дерево кода Хаффмена.
Рис. 8.6. Дерево кода Хаффмена
