Изменения

'''''Алгоритм Ху-ТаккераХу–Таккера'''''(англ. ''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>, такой, что:

1. *<tex>c_{i}</tex> не является префиксом для <tex>c_{j}</tex>, при <tex>i \ne j</tex>,

2. *для всех <tex>a_{i}<a_{j}</tex>, выполнено <tex>c_{i}<c_{j}</tex>,

3. *при удовлетворенности условия <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.''' Изначально мы имеем только алфавит (и соответствующие веса), отсортированный лексикографически.1* '''Шаг 2. ''' ''Комбинирование''(англ. ''Combining''). По данной последовательности из <tex>n </tex> вершин строим последовательность из <tex>n-1</tex> вершины, комбинируя минимальную совместимую пару и заменяя ее левую вершину вершиной с весом <tex> w = w_{l} + w_{r} </tex> и удаляя правую. Эта процедура повторяется до тех пор , пока не останется одна вершина. 2* '''Шаг 3. ''' ''Определение уровней''. Находим номер уровня <tex>l_{i}</tex> каждого листа относительно корня. 3* '''Шаг 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>.* Конец.

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

[[Файл:Hu-Taker_eps1.gif‎|300px|thumb|right]]Для примера возьмем алфавит <tex>A= \{</tex> ''a,b,c,d,e,f,t,g,h,i,j'' <tex>\} </tex>, а набор весов <tex>W= \{</tex> ''8,6,2,3,4,7,11,9,8,1,3'' <tex>\} </tex>.

Выполним первый второй шаг алгоритма. Объединим сначала <tex>w(i)=1</tex> и <tex>w(j)=3</tex>, получим вершину с весом <tex>w(ij)=4</tex>, затем <tex>w(c)=2</tex> и <tex>w(d)=3</tex> на вершину веса <tex>w(cd)=5</tex>, и т.д. пока не останется одна вершина.

Выполним второй шаг.[[Файл:Hu-Taker_Layer.jpg|300px|right|thumb‎]]Определим уровни для каждого листа <tex>L= \{</tex> ''3Заметим,3что это лишь обоснование,5а не строгое доказательство,5,4,3,3,3,3,4,4'' <tex>\его задача {{---}} </tex>дать понимание правдивости алгоритма.

                  Выполним третий шаг воспользовавшись стековым алгоритмом и получим необходимое дерево. [[Файл:Hu-Taker_eps3.gif|300px]][[Файл:Hu-Taker_Layer2.jpg‎|300px]] Осталось только назначить код для каждого символа, это делается аналогично коду Хаффмана, левым ребрам назначается 0, а правым 1. == Корректность алгоритма Ху-Таккера == Как пишет Д. Кнут короткого доказательства алгоритма не известно, и вероятно оно ни когда никогда не будет найдено. Для доказательства своего алгоритма Ху и Таккеру потребовалось <tex>3 </tex> теоремы и <tex>2 </tex> леммы(См. книгу Т.Ч.Ху и М.Т.Шинг Комбинаторные алгоритмы {{---}} стр.172).

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

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

Пусть <tex>a</tex> — {{---}} любая вершина в последовательности, состоящей из вершин алфавита и вершин , образованных в результате комбинации, <tex>w_{i}</tex> — {{---}} вес наименьшей вершины <tex>i</tex>, совместимого совместимой с <tex>a</tex>. Если в результате комбинирования некоторой л.м.с.п. какая-нибудь новая вершина <tex>d</tex> становится совместимой c с <tex>a</tex>, то <tex>w_{i}<w_{d}</tex> . В частности, л.м.с.п. в последовательности вершин будет оставаться л.м.с.п., пока комбинируются другие л.м.с.п.

Заметим, что <tex>w_{i}</tex> может находиться в любой стороне от <tex>a</tex>. Если вершина <tex>w_{i}</tex> лежит справа от <tex>a</tex>, то она не вершина алфавита. Пусть <tex>d</tex> — {{---}} вершина, которая становится совместимой с <tex>a</tex> после слияния <tex>(b, c)</tex> (она может быть как алфавитной так и слитой). Тогда <tex>d</tex> должна быть совместима с <tex>c</tex> в исходной последовательности и в силу локальной минимальности пары <tex>(b, c)</tex> имеем <tex>w_{b} \le leqslant w_{d}</tex>.

Но <tex>w_{i}<w_{b}</tex>, так как <tex>b</tex> совместим совместима с <tex>a</tex> в исходной последовательности, а <tex>w_{i}</tex> является наименьшим совместимым с <tex>a</tex> весом. Поэтому <tex>w_{i} \le leqslant w_{b} \le leqslant w_{d}</tex>.

Теперь согласно этой лемме нам не придется искать минимально совместимую пару, что весьма долго, достаточно . Достаточно лишь находить л.м.с.п. , при этом не важно , в каком порядке комбинировать л.м.с.п. По этому нам необходимо иметь массив размера <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. Сортировка и поиск — 824 с. — ISBN 5-8459-0082-4  [[Категория: Дискретная математика и алгоритмы]]

== Литература ==* Т.Ч.Ху и М.Т.Шинг Комбинаторные алгоритмы — стр. 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Алгоритмы сжатия ]]