Алгоритм Хаффмана
Алгоритм Хаффмана (англ. Huffman) — жадный алгоритм оптимального префиксного кодирования алфавита с минимальной избыточностью. Был разработан в 1952 году доктором Массачусетского технологического института Дэвидом Хаффманом. Используется в программе bzip2 на последнем этапе сжатия данных.
В отличие от алгоритма Шеннона-Фано, алгоритм Хаффмана остаётся всегда оптимальным и для вторичных алфавитов m2 с более чем двумя символами.
Этот метод кодирования состоит из двух основных этапов:
- Построение оптимального кодового дерева.
- Построение отображения код-символ на основе построенного дерева.
Алгоритм
- Символы первичного алфавита m1 выписывают в порядке убывания вероятностей.
- Последние n0 символов объединяют в новый символ, вероятность которого равна сумме этих символов, удаляют эти символы и вставляют новый символ в список остальных на соответствующее место (по вероятности). n0 вычисляется из системы:
\left\{\begin{matrix} 2 \le n_0 \le m_2 \\ n_0 = m_1 - a(m_2-1) \end{matrix}\right.,
где a — целое число, m1 и m2 — мощность первичного и вторичного алфавита соответственно. - Последние m2 символов снова объединяют в один и вставляют его в соответствующей позиции, предварительно удалив символы, вошедшие в объединение.
- Предыдущий шаг повторяют до тех пор, пока сумма всех m2 символов не станет равной 1.
Этот процесс можно представить как построение дерева, корень которого — символ с вероятностью 1, получившийся при объединении символов из последнего шага, его m2 потомков — символы из предыдущего шага и т.д.
Каждые m2 элементов, стоящих на одном уровне, нумеруются от 0 до m2-1. Коды получаются из путей (от первого потомка корня и до листка). При декодировании можно использовать то же самое дерево, считывается по одной цифре и делается шаг по дереву, пока не достигается лист — тогда выводится символ, стоящий в листе и производится возврат в корень.
Начальная страница