Условие:
Пусть алфавит А содержит 6 букв, вероятности которых равны 0,4;
0,2; 0,2; 0,1; 0,05 и 0,05. Произведите кодирование кодом Хаффмана.
Решение:
Нам задан алфавит из 6 символов с вероятностями 0,4; 0,2; 0,2; 0,1; 0,05; 0,05 для букв, обозначим их, например, так: A – 0,4, B – 0,2, C – 0,2, D – 0,1, E – 0,05, F – 0,05.
Наша цель – построить оптимальное префиксное кодирование по алгоритму Хаффмана. Опишем пошагово процесс построения дерева Хаффмана и получение кодов.
ШАГ 1. Инициализация Начинаем с листьев, каждому присвоена его вероятность: A: 0,4 B: 0,2 C: 0,2 D: 0,1 E: 0,05 F: 0,05
ШАГ 2. Первое объединение Выбираем два наименьших по вероятности элемента – это E и F (0,05 и 0,05). Объединяем их в новый узел, которы...