== Построение кода Хаффмана ==
[[Файл:Huffman1.png|100px|right|thumb|Обрабатываем b и c]][[Файл:Huffman2.png|100px|right|thumb|Получившееся дерево]]
В основу алгоритма Хаффмана положена идея: кодировать более коротко те символы, которые встречаются чаще, а те, которые встречаются реже кодировать длиннее. Для построения кода Хаффмана нам необходима таблица частот символов. Рассмотрим пример построения кода на простой строке '''''abacaba'''''<br>
{| class="wikitable"
|}
Следующим шагом будет построение дерева, где вершины - "символы", а пути до них соответствуют их префиксным кодам.
Для этого на каждом шаге будем брать два символа с минимальной частотой вхождения, и объединять их в новые так называемые "символы" с частотой равной сумме частот тех , которые мы объединяли, а также соединять их рёбрами, образуя таким образом дерево(см. рисунок). Выбирать минимальные два символа будем из всех символов, исключая те, которые мы объединялиуже выбирали. В примере мы объединим символы b и с в символ bc с частотой 3.Далее объединим a и bc в символ abc, получив тем самым дерево. Теперь пути от корня (abc) до листьев и есть Коды Хаффмана(каждому ребру соответствует либо 1 либо 0) [[Файл:Haffman1.jpg]]{| class="wikitable"! a || b || c |||-| 0 || 11 || 10 |||}
Хаффман изобрел жадный алгоритм, позволяющий составить оптимальный префиксный код, который получил название код Хаффмана. Доказательство корректности этого алгоритма основывается на свойстве жадного выбора и оптимальной подструктуре. Вместо того чтобы демонстрировать, что эти свойства выполняются, а затем разрабатывать псевдокод, сначала мы представим псевдокод. Это поможет прояснить, как алгоритм осуществляет жадный выбор. В приведенном ниже псевдокоде предполагается, что <tex>C</tex> — множество, состоящее из <tex>n</tex> символов, и что каждый из символов <tex>c\in C</tex> — объект с определенной частотой <tex>f(c)</tex>. В алгоритме строится дерево <tex>T</tex>, соответствующее оптимальному коду, причем построение идет в восходящем направлении. Процесс построения начинается с множества, состоящего из <tex>|C|</tex> листьев, после чего последовательно выполняется <tex>|C|-1</tex> операций "слияния", в результате которых образуется конечное дерево. Для идентификации двух наименее часто встречающихся объектов, подлежащих слиянию, используется очередь с приоритетами <tex>Q</tex>, ключами в которой являются частоты <tex>f</tex>. В результате слияния двух объектов образуется новый объект, частота появления которого является суммой частот объединенных объектов:
<br><br>
'''Huffman(<tex>C</tex>)''' <br>
<tex>n \gets |C|</tex> <br>
<tex>Q \gets C</tex> <br>
'''for''' <tex>i \gets 1</tex> '''to''' <tex>n - 1</tex> <br>
:'''do''' Выделить память для узла <tex>z</tex> <br>
::left[<tex> z</tex>]<tex> \gets x \gets</tex> Extract_Min(<tex> Q</tex>)<br>
::right[<tex>z</tex>]<tex>\gets y \gets </tex> Extract_Min(<tex>Q</tex>) <br>
::<tex>f[z] \gets f[x]+f[y]</tex>
::Insert(<tex>Q</tex>, <tex>z</tex> ) <br>
'''return''' Extract_Min(<tex>Q</tex> ) <tex> \rhd </tex> Возврат корня дерева <br><br>
=== Пример работы алгоритма ===
[[Файл:Huffman.jpg]]<br>
На каждом этапе показано содержимое очереди, элементы которой рассортированы в порядке возрастания их частот. На каждом шаге работы алгоритма объединяются два объекта (дерева) с самыми низкими частотами. Листья изображены в виде прямоугольников, в каждом из которых указана буква и соответствующая ей частота. Внутренние узлы представлены кругами, содержащими сумму частот дочерних узлов. Ребро, соединяющее внутренний узел с левым дочерним узлом, имеет метку 0, а ребро, соединяющее его с правым дочерним узлом, — метку 1. Слово кода для буквы образуется последовательностью меток на ребрах, соединяющих корень с листом, представляющим эту букву. По скольку данное множество содержит шесть букв, размер исходной очереди равен 6(часть ''а'' рисунка), а для построения дерева требуется пять слияний. Промежуточные этапы изображены в частях ''б-д''. Конечное дерево (''е'') представляет оптимальный префиксный код. Как уже говорилось, слово кода для буквы — это последовательность меток на пути от корня к листу с этой буквой.<br>
В строке 2 инициализируется очередь с приоритетами <tex>Q</tex>, состоящая из элементов множества <tex>С</tex>. Цикл '''for''' в строках 3-8 поочередно извлекает по два узла, <tex>x</tex> и <tex>у</tex>, которые характеризуются в очереди наименьшими частотами, и заменяет их в очереди новым узлом, представляющим объединение упомянутых выше элементов. Частота появления <tex>z</tex> вычисляется в строке 7 как сумма частот <tex>x</tex> и <tex>y</tex>. Узел <tex>x</tex> является левым дочерним узлом <tex>z</tex>, а <tex>y</tex> — его правым дочерним узлом. (Этот порядок является произвольным; перестановка левого и правого дочерних узлов приводит к созданию другого кода с той же стоимостью.) После <tex>n - 1</tex> объединений в очереди остается один узел — корень дерева кодов, который возвращается в строке 9.
=== Оценка времени работы ===
При анализе времени работы алгоритма Хаффмана предполагается, что <tex>Q</tex> реализована как бинарная неубывающая пирамида. Для множества <tex>C</tex>, состоящего из <tex>n</tex> символов, инициализацию очереди <tex>Q</tex> в строке 2 можно выполнить за время <tex>O(n)</tex>. Цикл for в строках 3-8 выполняется ровно <tex>n - 1</tex> раз, и поскольку для каждой операции над пирамидой требуется время<tex>O(lg(n))</tex>, вклад цикла во время работы алгоритма равен <tex>O(n \cdot lg(n))</tex>. Таким образом, полное время работы процедуры Huffman с входным множеством, состоящим из <tex>n</tex> символов, равно <tex>O(n \cdot lg(n))</tex>.
== Корректность алгоритма Хаффмана ==
что противоречит предположению о том, что дерево <tex>T'</tex> представляет оптимальный префиксный код для алфавита <tex>C'</tex>. Таким образом, дерево <tex>T</tex> должно представлять оптимальный префиксный код для алфавита <tex>C</tex>.
}}
Лемма 16.3.
Доказательство.
{{Теорема
|id=th1
