73
правки
Изменения
м
Нет описания правки
'''''Алгоритм Ху-ТакераТаккера''''' - алгоритм построения оптимального алфавитного дерева.
''Алфавитное дерево'' - дерево в котором при просмотре листьев слева направо символы идут в алфавитном порядке и код последующего лексикографически больше предыдущего.
3. при удовлетворенности условия 2, <tex>\sum\limits_{i \in [1, n]} w_{i}\cdot |c_{i}|</tex> минимальна (<tex>|c_{i}|</tex> — длина кода <tex>c_{i}</tex>)
называется ''алгоритмом Ху-ТакераТаккера''.
}}
== Алгоритм ==
Осталось только назначить код для каждого символа, это делается аналогично коду Хаффмана, левым ребрам назначается 0, а правым 1.
== Корректность алгоритма Ху-Такера Таккера ==
Как пишет Д. Кнут короткого доказательства алгоритма не известно, и вероятно оно ни когда не будет найдено. Для доказательства своего алгоритма Ху и Такеру Таккеру потребовалось 3 теоремы и 2 леммы.
== Литература ==
* Т.Ч.Ху и М.Т.Шинг Комбинаторные алгоритмы — стр. 166 — ISBN 5-85746-761-6
* Дональд Кнут Искусство программирования, том 3. Сортировка и поиск = The Art of Computer Programming, vol.3. Sorting and Searching. — 2-е изд. — М.: «Вильямс», 2007. — 824 с. — ISBN 5-8459-0082-4
