1632
правки
Изменения
м
rollbackEdits.php mass rollback
'''''Алгоритм Ху-ТаккераХу–Таккера''''' (англ. ''Hu-Tucker Hu–Tucker Algorithm'') {{---}} алгоритм построения оптимального алфавитного дерева.
{{Определение |definition='''Алфавитное дерево'' ' (англ. ''Alphabetical tree'') {{---}} дерево в котором при просмотре листьев слева направо символы идут в алфавитном порядке, и код последующего лексикографически больше предыдущего.==Определение==}}
{{Определение
Пусть <tex>A=\{a_{1},a_{2},...,a_{n}\}</tex> — алфавит из <tex>n</tex> различных символов, <tex>W=\{w_{1},w_{2},...,w_{n}\}</tex> — соответствующий ему набор весов. Тогда алгоритм выбора набора бинарных кодов <tex>C=\{c_{1},c_{2},...,c_{n}\}</tex>, такой, что:
*<tex>c_{i}</tex> не является префиксом для <tex>c_{j}</tex>, при <tex>i \ne j</tex>,
*для всех <tex>a_{i}<a_{j}</tex>, выполнено <tex>c_{i}<c_{j}</tex>,
*при удовлетворенности условия <tex>2</tex>, <tex>\sum\limits_{i \in [1, n]} w_{i}\cdot |c_{i}|</tex> минимальна (<tex>|c_{i}|</tex> — длина кода <tex>c_{i}</tex>)
называется '''алгоритмом Ху-ТаккераХу–Таккера'''.
}}
== Алгоритм ==
=== Алгоритм Ху-Таккера Ху–Таккера ===
* Начало.
* '''Шаг 0.''' ''Введем следующие понятия''.
**Две вершины называются совместимой парой(англ. ''compatible pair''), если они соседние или если между ними нет вершин алфавита.
**Две вершины называются минимальной парой, когда их суммарный вес наименьший из всех. При равенстве весов выбирается пара с самой левой вершиной, из всех таких та, у которой правый узел расположен левее.
**Минимальной совместимой парой называется наименьшая пара из всех совместимых.
* '''Шаг 1.''' Изначально мы имеем только алфавит (и соответствующие веса), отсортированный лексикографически.
* '''Шаг 2.''' ''Комбинирование''(англ. ''Combining''). По данной последовательности из <tex>n</tex> вершин строим последовательность из <tex>n-1</tex> вершины, комбинируя минимальную совместимую пару и заменяя ее левую вершину вершиной с весом <tex> w = w_{l} + w_{r} </tex> и удаляя правую. Эта процедура повторяется до тех пор, пока не останется одна вершина.
* '''Шаг 3.''' ''Определение уровней''. Находим номер уровня <tex>l_{i}</tex> каждого листа относительно корня.
* '''Шаг 4.''' ''Перестройка''. После того, как номера уровней <tex>l_{1}, l_{2}, ..., l_{n}</tex> всех листьев определены, просматриваем последовательность слева направо и находим самый левый номер максимального уровня, скажем, <tex>l_{i}=q</tex>. Тогда и <tex>l_{i+1}=q</tex> (в последовательности <tex>l_{1}, l_{2}, ..., l_{n}</tex> максимальные номера уровней всегда располагаются рядом). Создаем вершину уровня <tex>q-1</tex> вместо вершин уровня <tex>q</tex>. Другими словами, последовательность уровней <tex>l_{1}, l_{2}, ..., l_{q}, l_{q}, ..., l_{n}</tex> заменяется на <tex>l_{1}, l_{2}, ..., l_{q}-1, ..., l_{n}</tex>. Повторяем этот процесс до тех пор пока не останется одна вершина с уровнем <tex>0</tex>.
Осталось только назначить код для каждого символа. Это делается аналогично [[Алгоритм Хаффмана|коду Хаффмана]]: левым ребрам назначается <tex>0</tex>, а правым <tex>1</tex>.
== Обоснование алгоритма Ху-Таккера Ху–Таккера ==
Далее последовательностью-впадиной последовательностью–впадиной будем называть последовательность вида <tex>w_{1} > ... > w_{t} < ... < w_{n}</tex>.
Для обоснования воспользуемся несколькими леммами.
|about=1
|statement=
Если последовательность весов монотонно не убывает или монотонно убывает, то стоимости деревьев Хаффмана и Ху-Таккера Ху–Таккера совпадают. Более того, существует дерево Хаффмана, удовлетворяющее требованию алфавитности (см. упражнения к разделу 2.3.4-5 4–5 вт.1 книги Д. Кнута Искусство программирования для ЭВМ).
}}
{{Лемма
|about=2
|statement=
Если последовательность весов является впадиной, то стоимости деревьев Хаффмана и Ху-Таккера Ху–Таккера равны. Более того, существует дерево Хаффмана, удовлетворяющее требованию алфавитности (см. книгу Т.Ч.Ху и М.Т.Шинг Комбинаторные алгоритмы {{---}} леммы 7 и 8 в разделе 5.8).
}}
{{Лемма
|about=3
|statement=
Если последовательность весов является впадиной, то новые вершины, создаваемые в фазе <tex>1</tex> алгоритма Ху-ТаккераХу–Таккера, образуют очередь с монотонно возрастающими весами. Потомки каждой из этих новых вершин могут быть соединены в алфавитное бинарное дерево(англ. ''Alphabetical binary tree''), удовлетворяющее условию: если <tex>w_{i} \leqslant w_{j}</tex>, то <tex>l_{j} \leqslant l_{i}</tex>.
}}
Заметим, что в последовательности-впадине две наименьших вершины всегда совместимы. Поэтому в алгоритме Хаффмана будут комбинироваться те же пары, что и в фазе <tex>1</tex> алгоритма Ху-ТаккераХу–Таккера. Для удобства введем две вершины алфавита <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]] следует, что можно образовать две отдельных [[Очередь | очереди]] {{---}} одну для каждой впадины. Из-за горы вершины из разных впадин не совместимы между собой. Когда наименьшие новые вершины(полученные в результате слияния) во впадинах станут достаточно большими, гора будет наконец скомбинирована. С этого момента все новые вершины станут совместимыми. Получается слияние двух очередей. По существу, фаза <tex>1</tex> в алгоритме Ху-Таккера Ху–Таккера подобна слиянию нескольких очередей, а произвольную последовательность весов можно рассматривать как соединение нескольких впадин.
Чтобы понять, почему последовательность уровней может быть соединена в алфавитное дерево на третьем шаге алгоритма, достаточно рассмотреть два случая:
Заметим, что это лишь обоснование, а не строгое доказательство, его задача {{---}} дать понимание правдивости алгоритма.
== Корректность алгоритма Ху-Таккера Ху–Таккера ==
Как пишет Д. Кнут короткого доказательства алгоритма не известно, и вероятно оно никогда не будет найдено. Для доказательства своего алгоритма Ху и Таккеру потребовалось <tex>3</tex> теоремы и <tex>2</tex> леммы (См. книгу Т.Ч.Ху и М.Т.Шинг Комбинаторные алгоритмы {{---}} стр.172).
Теперь согласно этой лемме нам не придется искать минимально совместимую пару, что весьма долго. Достаточно лишь находить л.м.с.п., при этом не важно, в каком порядке комбинировать л.м.с.п. По этому нам необходимо иметь массив размера <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. Сортировка и поиск — 2-е изд. — М.: «Вильямс», 2007. — 824 с. — ISBN 5-8459-0082-4
