81
правка
Изменения
Нет описания правки
== Построение кода Хаффмана ==
В основу алгоритма Хаффмана положена идея: кодировать более коротко те символы, которые встречаются чаще, а те, которые встречаются реже кодировать длиннее. Для построения кода Хаффмана нам необходима таблица частот символов. Рассмотрим пример построения кода на простой строке '''''abacaba'''''<br>
{| class="wikitable"
! a || b || c ||
|-
| 4 || 2 || 1 ||
|}
Следующим шагом будет построение дерева, где вершины - "символы", а пути до них соответствуют их префиксным кодам.
Для этого на каждом шаге будем брать два символа с минимальной частотой вхождения, и объединять их в новые так называемые "символы" с частотой равной сумме частот тех символов, которые мы объединяли.
В примере мы объединим символы b и с в символ bc с частотой 3.
Хаффман изобрел жадный алгоритм, позволяющий составить оптимальный префиксный код, который получил название код Хаффмана. Доказательство корректности этого алгоритма основывается на свойстве жадного выбора и оптимальной подструктуре. Вместо того чтобы демонстрировать, что эти свойства выполняются, а затем разрабатывать псевдокод, сначала мы представим псевдокод. Это поможет прояснить, как алгоритм осуществляет жадный выбор. В приведенном ниже псевдокоде предполагается, что <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>
