Изменения

'''Алгоритм Хаффмана''' ({{lang-en|Huffman}}) — [[Адаптивный алгоритм|адаптивный]] [[жадный алгоритм]] оптимального [[префиксный код|префиксного]] [[энтропийное кодирование|кодирования]] алфавита с минимальной [[избыточность]]ю. Был разработан в [[1952]] году доктором [[Массачусетский технологический институт|Массачусетского технологического института]] [[Хаффман, Дэвид|Дэвидом Хаффманом]]. В настоящее время используется во многих программах сжатия данных.

'''Алгоритм Хаффмана''' ({{lang-en|Huffman}}) — [[Адаптивный алгоритм|адаптивный]] [[жадный алгоритм]] оптимального [[префиксный код|префиксного]] [[энтропийное кодирование|кодирования]] алфавита с минимальной [[избыточность]]ю. Был разработан в [[1952]] году доктором [[Массачусетский технологический институт|Массачусетского технологического института]] [[Хаффман, Дэвид|Дэвидом Хаффманом]]. В настоящее время используется во многих программах сжатия данных.

В отличие от [[алгоритм Шеннона-Фано|алгоритма Шеннона-Фано]], алгоритм Хаффмана остаётся всегда оптимальным и для [[вторичный алфавит|вторичных алфавитов]] m₂ с более чем двумя символами.

В отличие от [[алгоритм Шеннона-Фано|алгоритма Шеннона-Фано]], алгоритм Хаффмана остаётся всегда оптимальным и для [[вторичный алфавит|вторичных алфавитов]] m₂ с более чем двумя символами.

\left\{\begin{matrix} 2 \le n_0 \le m_2

\left\{\begin{matrix} 2 \le n_0 \le m_2

\\ n_0 = m_1 - a(m_2-1) \end{matrix}\right.

\\ n_0 = m_1 - a(m_2-1) \end{matrix}\right.

</math>,<br />где a — целое число, m₁ и m₂ — мощность первичного и вторичного алфавита соответственно.

</math>,<br />где a — целое число, m₁ и m₂ — мощность первичного и вторичного алфавита соответственно.

# Последние m₂ символов снова объединяют в один и вставляют его в соответствующей позиции, предварительно удалив символы, вошедшие в объединение.

# Последние m₂ символов снова объединяют в один и вставляют его в соответствующей позиции, предварительно удалив символы, вошедшие в объединение.

# Предыдущий шаг повторяют до тех пор, пока сумма всех m₂ символов не станет равной 1.

# Предыдущий шаг повторяют до тех пор, пока сумма всех m₂ символов не станет равной 1.

Этот процесс можно представить как построение [[Дерево (теория графов)|дерева]], корень которого — символ с вероятностью 1, получившийся при объединении символов из последнего шага, его m₂ потомков — символы из предыдущего шага и т. д.

Этот процесс можно представить как построение [[Дерево (теория графов)|дерева]], корень которого — символ с вероятностью 1, получившийся при объединении символов из последнего шага, его m₂ потомков — символы из предыдущего шага и т. д.

Каждые m₂ элементов, стоящих на одном уровне, нумеруются от 0 до m₂-1. Коды получаются из путей (от первого потомка корня и до листка). При декодировании можно использовать то же самое дерево, считывается по одной цифре и делается шаг по дереву, пока не достигается лист — тогда выводится символ, стоящий в листе и производится возврат в корень.

Каждые m₂ элементов, стоящих на одном уровне, нумеруются от 0 до m₂-1. Коды получаются из путей (от первого потомка корня и до листка). При декодировании можно использовать то же самое дерево, считывается по одной цифре и делается шаг по дереву, пока не достигается лист — тогда выводится символ, стоящий в листе и производится возврат в корень.

== Построение дерева Хаффмана ==

== Построение дерева Хаффмана ==

Общая схема построения дерева Хаффмана:

Общая схема построения дерева Хаффмана:

# Составим список кодируемых символов (при этом будем рассматривать каждый символ как одноэлементное бинарное дерево, вес которого равен весу символа).

# Составим список кодируемых символов (при этом будем рассматривать каждый символ как одноэлементное бинарное дерево, вес которого равен весу символа).

# Из списка выберем 2 узла с наименьшим весом (под весом можно понимать частоту использования символа — чем чаще используется, тем больше весит).

# Из списка выберем 2 узла с наименьшим весом (под весом можно понимать частоту использования символа — чем чаще используется, тем больше весит).

# Сформируем новый узел и присоединим к нему, в качестве дочерних, два узла выбранных из списка. При этом вес сформированного узла положим равным сумме весов дочерних узлов.

# Сформируем новый узел и присоединим к нему, в качестве дочерних, два узла выбранных из списка. При этом вес сформированного узла положим равным сумме весов дочерних узлов.

# Добавим сформированный узел к списку.

# Добавим сформированный узел к списку.