- Метод Хаффмана построения оптимального префиксного двоичного кода.
Алфавитом называется конечное множество символов. Сообщением называется конечная последовательность символов. Множество всех сообщений алфавита А обозначается А*.

Код называется префиксным, если ни одно кодовое слово не является началом (префиксом) никакого другого кодового слова
- В дереве префиксного кода коды всех символов заканчиваются в листьях
- Префиксный код позволяет выделять коды символов без использования разделителей
- Префиксный код декодируется однозначно



Дерево кодирования Хаффмана - двоичное дерево, у которого каждый узел имеет вес, и при этом вес родителя равен суммарному весу его детей. Алгоритм построения дерева кодирования Хаффмана таков:
-
- Буквы входного алфавита образуют список свободных узлов будущего дерева кодирования. Каждый узел в этом списке имеет вес, равный вероятности появления соответствующей буквы в сообщении.
-
- Выбираются два свободных узла дерева с наименьшими весами. Если имеется более двух свободных узлов с наименьшими весами, то можно брать любую пару.
-
- Создается их родитель с весом, равным их суммарному весу.
-
- Родитель добавляется в список свободных узлов, а двое его детей удаляются из этого списка.
-
- Одной дуге, выходящей из узла-родителя, ставится в соответствие бит 1, другой - 0.
-
- Пункты 2, 3, 4, 5 повторяются до тех пор, пока в списке свободных узлов не останется только один узел. Этот узел будет являться корнем дерева. Его вес получается равным единице - суммарной вероятности всех букв сообщения.
Двигаясь по кодовому дереву сверху вниз и последовательно выписывая двоичные цифры, соответствующие дугам, можно получить коды букв входного алфавита.
