73
правки
Изменения
Добавлен раздел "Обоснование алгоритма"
Осталось только назначить код для каждого символа. Это делается аналогично [[Алгоритм Хаффмана|коду Хаффмана]]: левым ребрам назначается 0, а правым 1.
== Обоснование алгоритма Ху-Таккера ==
Для обоснования воспользуемся несколькими леммами.
{{Лемма
|id=lemma1
|about=1
|statement=
Если последовательность весов монотонно не убывает или монотонно убывает, то стоимости деревьев Хаффмена и Ху-Таккера совпадают. Более того, существует дерево Хаффмена, удовлетворяющее требованию алфавитности (см. упражнения к разделу 2.3.4-5 вт.1 книги Д. Кнута Искусство программирования для ЭВМ).
}}
{{Лемма
|id=lemma2
|about=2
|statement=
Если последовательность весов является впадиной, то стоимости деревьев Хаффмена и Ху-Таккера равны. Более того, существует дерево Хаффмена, удовлетворяющее требованию алфавитности (см. книгу Т.Ч.Ху и М.Т.Шинг Комбинаторные алгоритмы {{---}} леммы 7 и 8 в разделе 5.8).
}}
{{Лемма
|id=lemma3
|about=3
|statement=
Если последовательность весов является впадиной, то новые вершины, создаваемые в фазе 1 алгоритма Ху-Таккера, образуют очередь с монотонно возрастающими весами. Потомки каждой из этих новых вершин могут быть соединены в алфавитное бинарное дерево, удовлетворяющее условию: если <tex>w_{i} \le w_{j}</tex>, то <tex>l_{j} \le l_{i}</tex>.
}}
Заметим, что в последовательности-впадине две наименьших вершины всегда совместимы. Поэтому в алгоритме Хаффмена будут комбинироваться те же пары, что и в фазе 1 алгоритма Ху-Таккера. Для удобства введем две вершины алфавита <tex>w_{L}</tex> и <tex>w_{R}</tex> веса <tex>\infty</tex>, расположенных соответственно в начале и в конце последовательности. Тогда последовательность весов <tex>w_{1} < w_{2} < ... < w_{t} > w_{t+1} > ... > w_{n}</tex> можно рассматривать как последовательность состоящую из двух впадин: <tex>w_{L} > w_{1} < w_{2} < ... < w_{t} > w_{t+1} > ... > w_{n} < w_{R}</tex>.
Вершину <tex>t</tex> назовем горой между двумя впадинами.
Из [[#lemma3|леммы 3]] следует, что можно образовать две отдельных очереди — одну для каждой впадины. Из-за горы узлы из разных впадин не совместимы между собой. Когда наименьшие новые вершины(полученные в результате слияния) во впадинах станут достаточно большими, гора будет наконец скомбинирована. С этого момента все новые вершины станут совместимыми. Получается слияние двух очередей. По существу, фаза 1 в алгоритме Ху-Таккера подобна слиянию нескольких очередей, а произвольную последовательность весов можно рассматривать как соединение нескольких впадин.
Чтобы понять, почему последовательность уровней может быть соединена в алфавитное дерево, достаточно рассмотреть два случая:
*Комбинируются две вершины из одной впадины.
*Комбинируются две вершины <tex>a</tex> и <tex>e</tex> из разных впадин. Пусть при этом между <tex>a</tex> и <tex>e</tex> расположены новые вершины <tex>b,c,d</tex> {{---}} каждая из них имеет двух сыновей, скажем, <tex>b1</tex> и <tex>b2</tex>, <tex>c1</tex> и <tex>c2</tex>, <tex>d1</tex> и <tex>d2</tex> {{---}} когда комбинируются <tex>a</tex> и <tex>e</tex>, мы в действительности создаем общего отца для <tex>a</tex> и <tex>b1</tex>. После этого общего отца получают <tex>b2</tex> и <tex>c1</tex>, затем <tex>c2</tex> и <tex>d1</tex>. Наконец, общего отца получают <tex>d2</tex> и <tex>e</tex>.
Заметим, что это лишь обоснование, а не строгое доказательство, его задача дать понимания правдивости алгоритма.
== Корректность алгоритма Ху-Таккера ==
Как пишет Д. Кнут короткого доказательства алгоритма не известно, и вероятно оно никогда не будет найдено. Для доказательства своего алгоритма Ху и Таккеру потребовалось 3 теоремы и 2 леммы (См. книгу Т.Ч.Ху и М.Т.Шинг Комбинаторные алгоритмы <tex>{{-</tex> --}} стр.172).
== Сложность алгоритма ==
