Алгоритм Ху-Таккера

Алгоритм Ху-Таккера (англ. Hu-Tucker Algorithm) — алгоритм построения оптимального алфавитного дерева.

Алфавитное дерево — дерево в котором при просмотре листьев слева направо символы идут в алфавитном порядке, и код последующего лексикографически больше предыдущего.

Определение

Определение:

Пусть [math]A=\{a_{1},a_{2},...,a_{n}\}[/math] — алфавит из [math]n[/math] различных символов, [math]W=\{w_{1},w_{2},...,w_{n}\}[/math] — соответствующий ему набор весов. Тогда алгоритм выбора набора бинарных кодов [math]C=\{c_{1},c_{2},...,c_{n}\}[/math], такой, что: [math]c_{i}[/math] не является префиксом для [math]c_{j}[/math], при [math]i \ne j[/math] для всех [math]a_{i}\lt a_{j}[/math], выполнено [math]c_{i}\lt c_{j}[/math] при удовлетворенности условия [math]2[/math], [math]\sum\limits_{i \in [1, n]} w_{i}\cdot |c_{i}|[/math] минимальна ([math]|c_{i}|[/math] — длина кода [math]c_{i}[/math]) называется алгоритмом Ху-Таккера.

Алгоритм

Алгоритм Ху-Таккера

• Начало.
• Шаг 0. Введем следующие понятия.
  • Две вершины называются совместимой парой, если они соседние или если между ними нет вершин алфавита.
  • Две вершины называются минимальной парой, когда их суммарный вес наименьший из всех. При равенстве весов выбирается пара с самой левой вершиной, из всех таких та, у которой правый узел расположен левее.
  • Минимальной совместимой парой называется наименьшая пара из всех совместимых.
• Шаг 1. Изначально мы имеем только алфавит (и соответствующие веса), отсортированный лексикографически.
• Шаг 2. Комбинирование. По данной последовательности из [math]n[/math] вершин строим последовательность из [math]n-1[/math] вершины, комбинируя минимальную совместимую пару и заменяя ее левую вершину вершиной с весом [math] w = w_{l} + w_{r} [/math] и удаляя правую. Эта процедура повторяется до тех пор, пока не останется одна вершина.
• Шаг 3. Определение уровней. Находим номер уровня [math]l_{i}[/math] каждого листа относительно корня.
• Шаг 4. Перестройка. После того, как номера уровней [math]l_{1}, l_{2}, ..., l_{n}[/math] всех листьев определены, просматриваем последовательность слева направо и находим самый левый номер максимального уровня, скажем, [math]l_{i}=q[/math]. Тогда и [math]l_{i+1}=q[/math] (в последовательности [math]l_{1}, l_{2}, ..., l_{n}[/math] максимальные номера уровней всегда располагаются рядом). Создаем вершину уровня [math]q-1[/math] вместо вершин уровня [math]q[/math]. Другими словами, последовательность уровней [math]l_{1}, l_{2}, ..., l_{q}, l_{q}, ..., l_{n}[/math] заменяется на [math]l_{1}, l_{2}, ..., l_{q}-1, ..., l_{n}[/math]. Повторяем этот процесс до тех пор пока не останется одна вершина с уровнем [math]0[/math].
• Конец.

Заметим, что перестройку легко можно организовать с помощью следующего стекового алгоритма.

Стековый алгоритм перестройки

• Начало.
• Шаг 0. Стек пуст.
• Шаг 1. Если значение двух верхних элементов различно или в стеке всего один элемент перейти к шагу [math]2[/math], иначе к шагу [math]3[/math].
• Шаг 2. Поместить следующий элемент [math]l_{i}[/math] на вершину стека. Перейти к шагу [math]1[/math].
• Шаг 3. Удалить [math]2[/math] верхних элемента стека, поместить в стек элемент со значением меньшим на единицу, чем удаленные. Если значение нового элемента равно нулю — остановиться, иначе перейти к шагу [math]1[/math].
• Конец.

Пример

Для примера возьмем алфавит [math]A= \{a,b,c,d,e,f,t,g,h,i,j\} [/math], а набор весов [math]W= \{8,6,2,3,4,7,11,9,8,1,3\} [/math].

Выполним второй шаг алгоритма.

Объединим сначала [math]w_{i}=1[/math] и [math]w_{j}=3[/math], получим вершину с весом [math]w_{ij}=4[/math], затем [math]w_{c}=2[/math] и [math]w_{d}=3[/math] на вершину веса [math]w_{cd}=5[/math], и т.д. пока не останется одна вершина.

Выполним третий шаг. Определим уровни для каждого листа [math]L= \{3,3,5,5,4,3,3,3,3,4,4\} [/math].

Выполним четвертый шаг, воспользовавшись стековым алгоритмом, и получим необходимое дерево.

Осталось только назначить код для каждого символа. Это делается аналогично коду Хаффмана: левым ребрам назначается [math]0[/math], а правым [math]1[/math].

Обоснование алгоритма Ху-Таккера

Далее последовательностью-впадиной будем называть последовательность вида [math]w_{1} \gt ... \gt w_{t} \lt ... \lt w_{n}[/math].

Для обоснования воспользуемся несколькими леммами.

Лемма (1):

Если последовательность весов монотонно не убывает или монотонно убывает, то стоимости деревьев Хаффмана и Ху-Таккера совпадают. Более того, существует дерево Хаффмана, удовлетворяющее требованию алфавитности (см. упражнения к разделу 2.3.4-5 вт.1 книги Д. Кнута Искусство программирования для ЭВМ).

Лемма (2):

Если последовательность весов является впадиной, то стоимости деревьев Хаффмана и Ху-Таккера равны. Более того, существует дерево Хаффмана, удовлетворяющее требованию алфавитности (см. книгу Т.Ч.Ху и М.Т.Шинг Комбинаторные алгоритмы — леммы 7 и 8 в разделе 5.8).

Лемма (3):

Если последовательность весов является впадиной, то новые вершины, создаваемые в фазе [math]1[/math] алгоритма Ху-Таккера, образуют очередь с монотонно возрастающими весами. Потомки каждой из этих новых вершин могут быть соединены в алфавитное бинарное дерево, удовлетворяющее условию: если [math]w_{i} \leqslant w_{j}[/math], то [math]l_{j} \leqslant l_{i}[/math].

Заметим, что в последовательности-впадине две наименьших вершины всегда совместимы. Поэтому в алгоритме Хаффмана будут комбинироваться те же пары, что и в фазе [math]1[/math] алгоритма Ху-Таккера. Для удобства введем две вершины алфавита [math]w_{L}[/math] и [math]w_{R}[/math] веса [math]\infty[/math], расположенных соответственно в начале и в конце последовательности. Тогда последовательность весов [math]w_{1} \lt w_{2} \lt ... \lt w_{t} \gt w_{t+1} \gt ... \gt w_{n}[/math] можно рассматривать как последовательность состоящую из двух впадин: [math]w_{L} \gt w_{1} \lt w_{2} \lt ... \lt w_{t} \gt w_{t+1} \gt ... \gt w_{n} \lt w_{R}[/math].

Вершину [math]t[/math] назовем горой между двумя впадинами.

Из леммы 3 следует, что можно образовать две отдельных очереди — одну для каждой впадины. Из-за горы вершины из разных впадин не совместимы между собой. Когда наименьшие новые вершины(полученные в результате слияния) во впадинах станут достаточно большими, гора будет наконец скомбинирована. С этого момента все новые вершины станут совместимыми. Получается слияние двух очередей. По существу, фаза [math]1[/math] в алгоритме Ху-Таккера подобна слиянию нескольких очередей, а произвольную последовательность весов можно рассматривать как соединение нескольких впадин.

Чтобы понять, почему последовательность уровней может быть соединена в алфавитное дерево на третьем шаге алгоритма, достаточно рассмотреть два случая:

• Комбинируются две вершины из одной впадины.
• Комбинируются две вершины [math]a[/math] и [math]e[/math] из разных впадин. Пусть при этом между [math]a[/math] и [math]e[/math] расположены новые вершины [math]b,c,d[/math] — каждая из них имеет двух сыновей, скажем, [math]b1[/math] и [math]b2[/math], [math]c1[/math] и [math]c2[/math], [math]d1[/math] и [math]d2[/math] — когда комбинируются [math]a[/math] и [math]e[/math], мы в действительности создаем общего отца для [math]a[/math] и [math]b1[/math]. После этого общего отца получают [math]b2[/math] и [math]c1[/math], затем [math]c2[/math] и [math]d1[/math]. Наконец, общего отца получают [math]d2[/math] и [math]e[/math].

Заметим, что это лишь обоснование, а не строгое доказательство, его задача — дать понимание правдивости алгоритма.

Корректность алгоритма Ху-Таккера

Как пишет Д. Кнут короткого доказательства алгоритма не известно, и вероятно оно никогда не будет найдено. Для доказательства своего алгоритма Ху и Таккеру потребовалось [math]3[/math] теоремы и [math]2[/math] леммы (См. книгу Т.Ч.Ху и М.Т.Шинг Комбинаторные алгоритмы — стр.172).

Сложность алгоритма

Для реализации данного алгоритма потребуется [math]O(n)[/math] памяти и [math]O(n \log n)[/math] времени на построение дерева.

Разберем оценку. Для доказательства такой оценки времени введем понятие локально минимальной совместимой пары (л.м.с.п), пара [math](w_{l},w_{r})[/math] является л.м.с.п, когда выполнены следующие условия [math]w_{r}\lt w_{i}[/math] для всех вершин [math]i[/math] совместимых с [math]l[/math] и [math]w_{l} \leqslant w_{j}[/math] для всех вершин [math]j[/math] совместимых с [math]r[/math]. Также докажем следующую лемму:

Лемма (1):

Пусть [math]a[/math] — любая вершина в последовательности, состоящей из вершин алфавита и вершин, образованных в результате комбинации, [math]w_{i}[/math] — вес наименьшей вершины [math]i[/math], совместимой с [math]a[/math]. Если в результате комбинирования некоторой л.м.с.п. какая-нибудь новая вершина [math]d[/math] становится совместимой с [math]a[/math], то [math]w_{i}\lt w_{d}[/math]. В частности, в последовательности вершин будет оставаться л.м.с.п., пока комбинируются другие л.м.с.п. Из этой леммы следует, что дерево, получаемое комбинированием л.м.с.п., не зависит от того, в каком порядке они комбинируются.

Доказательство:

[math]\triangleright[/math]

Рассмотрим произвольную вершину [math]a[/math] и предположим, что вес наименьшей вершины, совместимой с [math]a[/math], равен [math]w_{i}[/math]. Пусть комбинируется л.м.с.п. [math](b, c)[/math], причем [math]a[/math] ближе к [math]b[/math]. Тогда между [math]a[/math] и [math]b[/math] нет вершин алфавита и хотя бы одна из [math]b[/math], [math]c[/math] должна быть вершиной алфавита, иначе при слиянии [math](b, c)[/math] не появилось бы новых вершин (кроме [math]bc[/math]), совместимых с [math]a[/math]. Заметим, что [math]w_{i}[/math] может находиться в любой стороне от [math]a[/math]. Если вершина [math]w_{i}[/math] лежит справа от [math]a[/math], то она не вершина алфавита. Пусть [math]d[/math] — вершина, которая становится совместимой с [math]a[/math] после слияния [math](b, c)[/math] (она может быть как алфавитной так и слитой). Тогда [math]d[/math] должна быть совместима с [math]c[/math] в исходной последовательности и в силу локальной минимальности пары [math](b, c)[/math] имеем [math]w_{b} \leqslant w_{d}[/math]. Но [math]w_{i}\lt w_{b}[/math], так как [math]b[/math] совместима с [math]a[/math] в исходной последовательности, а [math]w_{i}[/math] является наименьшим совместимым с [math]a[/math] весом. Поэтому [math]w_{i} \leqslant w_{b} \leqslant w_{d}[/math]. Мы доказали, что вес наименьшей вершины, совместимой с любой вершиной, не может уменьшиться. Отсюда следует, что любая л.м.с.п. [math](x, y)[/math] останется л.м.с.п. после слияния другой л.м.с.п., потому что [math]x[/math] останется наименьшей вершиной, совместимой с [math]y[/math], и наоборот.

[math]\triangleleft[/math]

Теперь согласно этой лемме нам не придется искать минимально совместимую пару, что весьма долго. Достаточно лишь находить л.м.с.п., при этом не важно, в каком порядке комбинировать л.м.с.п. По этому нам необходимо иметь массив размера [math]n[/math], из которого мы будем удалять л.м.с.п и создавать новую вершину. На нем легко будет осуществлять поиск л.м.с.п. А так же необходим массив размера [math]2n[/math] для реализации следующего шага, хранящий дерево. Второй шаг легко осуществить проходом по дереву, имея сохраненное дерево. Третий шаг, реализованный стековым алгоритмом, работает за [math]2n[/math] времени и требует [math]4n[/math] памяти [math]n[/math] на стек, [math]n[/math] на хранения уровней вершин и [math]2n[/math] на хранение итогового дерева. Итак, общая оценка как раз получается [math]O(n)[/math] памяти и [math]O(n \log n)[/math] времени.

Смотри также

• Алгоритм Хаффмана
• Избыточное кодирование, код Хэмминга
• Стек
• Очередь

Источники информации

• Т.Ч.Ху, М.Т.Шинг Комбинаторные алгоритмы. — стр. 166. — ISBN 5-85746-761-6
• Дональд Кнут Искусство программирования, том 3. Сортировка и поиск — 2-е изд. — М.: «Вильямс», 2007. — 824 с. — ISBN 5-8459-0082-4