Алфавит передаваемых сообщений состоит из независимых букв Si

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