Изменения
мСтрока 7:
Строка 7: + + + + + + + + + + + + + + + + + + + + + + + + + + +
← Правки 95.24.165.157 (обсуждение) откачены к версии Mstislavl
# Построение оптимального кодового дерева.
# Построение оптимального кодового дерева.
# Построение отображения код-символ на основе построенного дерева.
# Построение отображения код-символ на основе построенного дерева.
== Алгоритм ==
# Подсчитываются вероятности появления символов [[первичный алфавит|первичного алфавита]] в исходном тексте (если они не заданы заранее)
# Символы первичного алфавита m<sub>1</sub> выписывают в порядке убывания вероятностей.
# Последние n<sub>0</sub> символов объединяют в новый символ, вероятность которого равна суммарной вероятности этих символов, удаляют эти символы и вставляют новый символ в список остальных на соответствующее место (по вероятности). n<sub>0</sub> вычисляется из системы:<br /><math>
\left\{\begin{matrix} 2 \le n_0 \le m_2
\\ n_0 = m_1 - a(m_2-1) \end{matrix}\right.
</math>,<br />где a — целое число, m<sub>1</sub> и m<sub>2</sub> — мощность первичного и вторичного алфавита соответственно.
# Последние m<sub>2</sub> символов снова объединяют в один и вставляют его в соответствующей позиции, предварительно удалив символы, вошедшие в объединение.
# Предыдущий шаг повторяют до тех пор, пока сумма всех m<sub>2</sub> символов не станет равной 1.
Этот процесс можно представить как построение [[Дерево (теория графов)|дерева]], корень которого — символ с вероятностью 1, получившийся при объединении символов из последнего шага, его m<sub>2</sub> потомков — символы из предыдущего шага и т. д.
Каждые m<sub>2</sub> элементов, стоящих на одном уровне, нумеруются от 0 до m<sub>2</sub>-1. Коды получаются из путей (от первого потомка корня и до листка). При декодировании можно использовать то же самое дерево, считывается по одной цифре и делается шаг по дереву, пока не достигается лист — тогда выводится символ, стоящий в листе и производится возврат в корень.
== Построение дерева Хаффмана ==
Бинарное дерево, соответствующее коду Хаффмана, называют деревом Хаффмана.
Задача построения кода Хаффмана равносильна задаче построения соответствующего ему дерева.
Общая схема построения дерева Хаффмана:
# Составим список кодируемых символов (при этом будем рассматривать каждый символ как одноэлементное бинарное дерево, вес которого равен весу символа).
# Из списка выберем 2 узла с наименьшим весом (под весом можно понимать частоту использования символа — чем чаще используется, тем больше весит).
# Сформируем новый узел и присоединим к нему, в качестве дочерних, два узла выбранных из списка. При этом вес сформированного узла положим равным сумме весов дочерних узлов.
# Добавим сформированный узел к списку.
# Если в списке больше одного узла, то повторить 2-5.
== Пример реализации ==
== Пример реализации ==