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

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

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

Определение

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

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

Алгоритм

0. Введем следующие понятия. Две вершины называются совместимой парой, если они соседние или если между ними нет вершин алфавита. Две вершины называются минимальной парой, когда их суммарный вес наименьший из всех, из всех таких выбирается пара с самой левой вершиной, из всех таких та у которой правый узел расположен левее. Минимальной совместимой парой называется наименьшая пара из всех совместимых.

1. Комбинирование. По данной последовательности из n вершин строим последовательность из [math]n-1[/math] вершины, комбинируя минимальную совместимую пару и заменяя ее левую вершину вершиной с весом [math] w = w_{l} + w_{r} [/math] и удаляя правую. Эта процедура повторяется до тех пор пока не останется одна вершина.

2. Определение уровней. Находим номер уровня [math]l_{i}[/math] каждого листа относительно корня.

3. Перестройка. После того, как номера уровней [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]. Повторяем этот процесс до тех пор пока не останется одна вершина с уровнем 0.

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

Шаг 0. Стек пуст.

Шаг 1. Если значение двух верхних элементов различно или в стеке всего один элемент перейти к шагу 2, иначе шагу 3.

Шаг 2. Поместить следующий элемент l на вершину стека.

Шаг 3. Удалить 2 верхних элемента стека, поместить в стек элемент со значением меньшим на единицу, чем удаленные, если значение нового элемента равно нулю - остановится, иначе перейти к шагу 1.

Пример

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

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

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

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

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

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

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

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

Как пишет Д. Кнут короткого доказательства алгоритма не известно, и вероятно оно ни когда не будет найдено. Для доказательства своего алгоритма Ху и Таккеру потребовалось 3 теоремы и 2 леммы.

Литература

• Т.Ч.Ху и М.Т.Шинг Комбинаторные алгоритмы — стр. 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