3622
правки
Изменения
Нет описания правки
|about=1
|statement=
Если последовательность весов монотонно не убывает или монотонно убывает, то стоимости деревьев Хаффмена Хаффмана и Ху-Таккера совпадают. Более того, существует дерево ХаффменаХаффмана, удовлетворяющее требованию алфавитности (см. упражнения к разделу 2.3.4-5 вт.1 книги Д. Кнута Искусство программирования для ЭВМ).
}}
{{Лемма
|about=2
|statement=
Если последовательность весов является впадиной, то стоимости деревьев Хаффмена Хаффмана и Ху-Таккера равны. Более того, существует дерево ХаффменаХаффмана, удовлетворяющее требованию алфавитности (см. книгу Т.Ч.Ху и М.Т.Шинг Комбинаторные алгоритмы {{---}} леммы 7 и 8 в разделе 5.8).
}}
{{Лемма
Если последовательность весов является впадиной, то новые вершины, создаваемые в фазе 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> назовем горой между двумя впадинами.
*Комбинируются две вершины <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>.
Заметим, что это лишь обоснование, а не строгое доказательство, его задача {{---}} дать понимание правдивости алгоритма.
== Корректность алгоритма Ху-Таккера ==
