• Метод Хаффмана построения оптимального префиксного двоичного кода.

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

Код называется префиксным, если ни одно кодовое слово не является началом (префиксом) никакого другого кодового слова

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

Дерево кодирования Хаффмана - двоичное дерево, у которого каждый узел имеет вес, и при этом вес родителя равен суммарному весу его детей. Алгоритм построения дерева кодирования Хаффмана таков:

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

Двигаясь по кодовому дереву сверху вниз и последовательно выписывая двоичные цифры, соответствующие дугам, можно получить коды букв входного алфавита.