3622
правки
Изменения
Нет описания правки
[[Файл:Hu-Taker_eps3.gif|300px]][[Файл:Hu-Taker_Layer2.jpg|300px]]
Осталось только назначить код для каждого символа, это делается аналогично коду Хаффмана(см. [[Алгоритм Хаффмана|коду Хаффмана]]), левым ребрам назначается 0, а правым 1.
== Корректность алгоритма Ху-Таккера ==
== Сложность алгоритма ==
Для реализации данного алгоритма потребуется <tex>O(n)</tex> памяти и <tex>O(n \log n)</tex> времени на построение дерева.
Разберем оценку. Для доказательства такой оценки времени введем понятие ''локально минимальной совместимой пары'' (л.м.с.п), пара <tex>(w_{l},w_{r})</tex> является л.м.с.п, когда выполнены следующие условия <tex>w_{r}<w_{i}</tex> для всех вершин <tex>i</tex> совместимых с <tex>l</tex> и <tex>w_{l} \le w_{j}</tex> для всех вершин <tex>j</tex> совместимых с <tex>r</tex>. Так же докажем следующую лемму.
Теперь согласно этой лемме нам не придется искать минимально совместимую пару, что весьма долго, достаточно лишь находить л.м.с.п. при этом не важно в каком порядке комбинировать л.м.с.п. По этому нам необходимо иметь массив размера <tex>n</tex> из которого мы будем удалять л.м.с.п и создавать новую вершину, на нем легко будет осуществлять поиск л.м.с.п. А так же необходим массив размера <tex>2n</tex> хранящий дерево, для реализации следующего шага. Второй шаг легко осуществить имея сохраненное дерево, проходом по дереву. Третий шаг реализованный стековым алгоритмом работает за <tex>2n</tex> времени и необходимо <tex>4n</tex> памяти, <tex>n</tex> на стек, <tex>n</tex> на хранения уровней вершин и <tex>2n</tex> на хранение итогового дерева. Итак общая оценка как раз получается <tex>O(n)</tex> памяти и <tex>O(n \log n)</tex> времени. == Смотри также ==* [[Алгоритм Хаффмана]]* [[Избыточное кодирование, код Хэмминга]]
== Литература ==
* Т.Ч.Ху и М.Т.Шинг Комбинаторные алгоритмы — стр. 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
