1302
правки
Изменения
→Построение кода Хаффмана
== Построение кода Хаффмана ==
<div style="float:right; margin:0;padding:0;">{| border="0"| [[Файл:Huffman1.png|100px150px|right|thumb|Обрабатываем b и c]]||[[Файл:Huffman2.png|100px150px|right|thumb|Получившееся дерево]] |}</div>В основу алгоритма Хаффмана положена идея: кодировать более коротко те символы, которые встречаются чаще, а те, которые встречаются реже кодировать длиннее. Для построения кода Хаффмана нам необходима таблица частот символов. Рассмотрим пример построения кода на простой строке '''''abacaba'''''<br>
{| class="wikitable"
! a || b || c ||
| 4 || 2 || 1 ||
|}
Следующим шагом будет построение дерева, где вершины - "символы", а пути до них соответствуют их префиксным кодам.
Для этого на каждом шаге будем брать два символа с минимальной частотой вхождения, и объединять их в новые так называемые символы с частотой равной сумме частот тех, которые мы объединяли, а также соединять их рёбрами, образуя таким образом дерево(см. рисунок). Выбирать минимальные два символа будем из всех символов, исключая те, которые мы уже выбирали.
В примере мы объединим символы b и с в символ bc с частотой 3. Далее объединим a и bc в символ abc, получив тем самым дерево. Теперь пути от корня (abc) до листьев и есть Коды Хаффмана(каждому ребру соответствует либо 1 либо 0)
{| class="wikitable"
| 0 || 11 || 10 ||
|}
== Корректность алгоритма Хаффмана ==
