Алгоритм Ху-Таккера — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Корректность алгоритма Ху-Таккера: ссылка на книгу)
м (rollbackEdits.php mass rollback)
 
(не показано 25 промежуточных версий 5 участников)
Строка 1: Строка 1:
'''''Алгоритм Ху-Таккера''''' - алгоритм построения оптимального алфавитного дерева.
+
'''''Алгоритм Ху–Таккера''''' (англ. ''Hu–Tucker Algorithm'') {{---}} алгоритм построения оптимального алфавитного дерева.
  
''Алфавитное дерево'' - дерево в котором при просмотре листьев слева направо символы идут в алфавитном порядке и код последующего лексикографически больше предыдущего.
+
{{Определение
==Определение==
+
|definition=
 +
'''Алфавитное дерево''' (англ. ''Alphabetical tree'') {{---}} дерево в котором при просмотре листьев слева направо символы идут в алфавитном порядке, и код последующего лексикографически больше предыдущего.
 +
}}
  
 
{{Определение  
 
{{Определение  
 
|definition=
 
|definition=
Пусть <tex>A=\{a_{1},a_{2},...,a_{n}\}</tex> — алфавит из n различных символов, <tex>W=\{w_{1},w_{2},...,w_{n}\}</tex>  — соответствующий ему набор весов. Тогда алгоритм выбора набора бинарных кодов <tex>C=\{c_{1},c_{2},...,c_{n}\}</tex>, такой, что:
+
Пусть <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>
+
*<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>
+
*для всех <tex>a_{i}<a_{j}</tex> выполнено <tex>c_{i}<c_{j}</tex>,
  
3. при удовлетворенности условия 2, <tex>\sum\limits_{i \in [1, n]} w_{i}\cdot |c_{i}|</tex> минимальна  (<tex>|c_{i}|</tex> — длина кода <tex>c_{i}</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. ''Введем следующие понятия''. Две вершины называются совместимой парой, если они соседние или если между ними нет вершин алфавита. Две вершины называются минимальной парой, когда их суммарный вес наименьший из всех. При равенстве весов, выбирается пара с самой левой вершиной, из всех таких та у которой правый узел расположен левее. Минимальной совместимой парой называется наименьшая пара из всех совместимых.
+
=== Алгоритм Ху–Таккера ===
 +
* Начало.
 +
* '''Шаг 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>.
 +
* Конец.
  
1. ''Комбинирование''. По данной последовательности из n вершин строим последовательность из <tex>n-1</tex> вершины, комбинируя минимальную совместимую пару и заменяя ее левую вершину вершиной с весом <tex> w = w_{l} + w_{r} </tex> и удаляя правую. Эта процедура повторяется до тех пор пока не останется одна вершина.
 
  
2. ''Определение уровней''. Находим номер уровня <tex>l_{i}</tex> каждого листа относительно корня.
+
Заметим, что перестройку легко можно организовать с помощью следующего стекового алгоритма.
 +
=== Стековый алгоритм перестройки ===
 +
* Начало.
 +
* '''Шаг 0.''' [[Стек]] пуст.
 +
* '''Шаг 1.''' Если значение двух верхних элементов различно или в стеке всего один элемент перейти к шагу <tex>2</tex>, иначе к шагу <tex>3</tex>.
 +
* '''Шаг 2.''' Поместить следующий элемент <tex>l_{i}</tex> на вершину стека. Перейти к шагу <tex>1</tex>.
 +
* '''Шаг 3.''' Удалить <tex>2</tex> верхних элемента стека, поместить в стек элемент со значением меньшим на единицу, чем удаленные. Если значение нового элемента равно нулю {{---}} остановиться, иначе перейти к шагу <tex>1</tex>.
 +
* Конец.
  
3. ''Перестройка''. После того, как номера уровней <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>. Повторяем этот процесс до тех пор пока не останется одна вершина с уровнем 0.
+
==Пример==
 +
Для примера возьмем алфавит <tex>A= \{a,b,c,d,e,f,t,g,h,i,j\} </tex>, а набор весов <tex>W= \{8,6,2,3,4,7,11,9,8,1,3\} </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>, и т.д. пока не останется одна вершина.
  
Шаг 0. Стек пуст.
+
[[Файл:Hu-Taker_eps1.gif‎|300px]]
  
Шаг 1. Если значение двух верхних элементов различно или в стеке всего один элемент перейти к шагу 2, иначе шагу 3.
+
Выполним третий шаг.
 +
Определим уровни для каждого листа <tex>L= \{3,3,5,5,4,3,3,3,3,4,4\} </tex>.
  
Шаг 2. Поместить следующий элемент <tex>l_{i}</tex> на вершину стека.
+
[[Файл:Hu-Taker Layer2.png|300px]]
  
Шаг 3. Удалить 2 верхних элемента стека, поместить в стек элемент со значением меньшим на единицу, чем удаленные, если значение нового элемента равно нулю - остановится, иначе перейти к шагу 1.
+
Выполним четвертый шаг, воспользовавшись стековым алгоритмом, и получим необходимое дерево.
  
==Пример==
+
[[Файл:Hu-Taker_eps3.gif|300px]][[Файл:Hu Takker eps3.png ‎|300px]]
Для примера возьмем алфавит <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>0</tex>, а правым <tex>1</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_eps1.gif‎|300px]]
+
Далее последовательностью–впадиной будем называть последовательность вида <tex>w_{1} > ... > w_{t} < ... < w_{n}</tex>.
  
Выполним второй шаг.
+
Для обоснования воспользуемся несколькими леммами.
Определим уровни для каждого листа <tex>L= \{</tex> ''3,3,5,5,4,3,3,3,3,4,4'' <tex>\} </tex>.
+
{{Лемма
 +
|id=lemma1
 +
|about=1
 +
|statement=
 +
Если последовательность весов монотонно не убывает или монотонно убывает, то стоимости деревьев Хаффмана и Ху–Таккера совпадают. Более того, существует дерево Хаффмана, удовлетворяющее требованию алфавитности (см. упражнения к разделу 2.3.4–5 вт.1 книги Д. Кнута Искусство программирования для ЭВМ).
 +
}}
 +
{{Лемма
 +
|id=lemma2
 +
|about=2
 +
|statement=
 +
Если последовательность весов является впадиной, то стоимости деревьев Хаффмана и Ху–Таккера равны. Более того, существует дерево Хаффмана, удовлетворяющее требованию алфавитности (см. книгу Т.Ч.Ху и М.Т.Шинг Комбинаторные алгоритмы {{---}} леммы 7 и 8 в разделе 5.8).
 +
}}
 +
{{Лемма
 +
|id=lemma3
 +
|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>.
  
[[Файл:Hu-Taker_Layer.jpg|300px]]
+
Вершину <tex>t</tex> назовем горой между двумя впадинами.
  
Выполним третий шаг воспользовавшись стековым алгоритмом и получим необходимое дерево.
+
Из [[#lemma3|леммы 3]] следует, что можно образовать две отдельных [[Очередь | очереди]] {{---}} одну для каждой впадины. Из-за горы вершины из разных впадин не совместимы  между собой. Когда наименьшие новые вершины(полученные в результате слияния) во впадинах станут достаточно большими, гора будет наконец скомбинирована. С этого момента все новые вершины станут совместимыми. Получается слияние двух очередей. По существу, фаза <tex>1</tex> в алгоритме Ху–Таккера подобна слиянию нескольких очередей, а произвольную последовательность весов можно рассматривать как соединение нескольких впадин.
  
[[Файл:Hu-Taker_eps3.gif|300px]][[Файл:Hu-Taker_Layer2.jpg‎|300px]]
+
Чтобы понять, почему последовательность уровней может быть соединена в алфавитное дерево на третьем шаге алгоритма, достаточно рассмотреть два случая:  
 +
*Комбинируются две вершины из одной впадины.
 +
*Комбинируются две вершины <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>.
  
Осталось только назначить код для каждого символа, это делается аналогично [[Алгоритм Хаффмана|коду Хаффмана]], левым ребрам назначается 0, а правым 1.
+
Заметим, что это лишь обоснование, а не строгое доказательство, его задача {{---}} дать понимание правдивости алгоритма.
  
== Корректность алгоритма Ху-Таккера ==
+
== Корректность алгоритма Ху–Таккера ==
  
Как пишет Д. Кнут короткого доказательства алгоритма не известно, и вероятно оно ни когда не будет найдено. Для доказательства своего алгоритма Ху и Таккеру потребовалось 3 теоремы и 2 леммы (См. книгу Т.Ч.Ху и М.Т.Шинг Комбинаторные алгоритмы <tex>-</tex> стр.172).
+
Как пишет Д. Кнут короткого доказательства алгоритма не известно, и вероятно оно никогда не будет найдено. Для доказательства своего алгоритма Ху и Таккеру потребовалось <tex>3</tex> теоремы и <tex>2</tex> леммы (См. книгу Т.Ч.Ху и М.Т.Шинг Комбинаторные алгоритмы {{---}} стр.172).
  
 
== Сложность алгоритма ==
 
== Сложность алгоритма ==
Строка 66: Строка 106:
 
Для реализации данного алгоритма потребуется <tex>O(n)</tex> памяти и <tex>O(n \log n)</tex> времени на построение дерева.
 
Для реализации данного алгоритма потребуется <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 w_{j}</tex> для всех вершин <tex>j</tex> совместимых с <tex>r</tex>. Так же докажем следующую лемму.
+
Разберем оценку. Для доказательства такой оценки времени введем понятие ''локально минимальной совместимой пары'' (л.м.с.п), пара <tex>(w_{l},w_{r})</tex> является л.м.с.п, когда выполнены следующие условия <tex>w_{r}<w_{i}</tex> для всех вершин <tex>i</tex> совместимых с <tex>l</tex> и <tex>w_{l} \leqslant w_{j}</tex> для всех вершин <tex>j</tex> совместимых с <tex>r</tex>. Также докажем следующую лемму:
 
{{Лемма
 
{{Лемма
 
|id=lemma1
 
|id=lemma1
 
|about=1
 
|about=1
 
|statement=
 
|statement=
Пусть <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>a</tex> {{---}} любая вершина в последовательности, состоящей из вершин алфавита и вершин, образованных в результате комбинации, <tex>w_{i}</tex> {{---}} вес наименьшей вершины <tex>i</tex>, совместимой с <tex>a</tex>. Если в результате комбинирования некоторой л.м.с.п. какая-нибудь новая вершина <tex>d</tex> становится совместимой с <tex>a</tex>, то <tex>w_{i}<w_{d}</tex>. В частности, в последовательности вершин будет оставаться л.м.с.п., пока комбинируются другие л.м.с.п.  
  
  
Строка 80: Строка 120:
 
Пусть комбинируется л.м.с.п. <tex>(b, c)</tex>, причем <tex>a</tex> ближе к <tex>b</tex>. Тогда между <tex>a</tex> и <tex>b</tex> нет вершин алфавита и хотя бы одна из <tex>b</tex>, <tex>c</tex> должна быть вершиной алфавита, иначе при слиянии <tex>(b, c)</tex> не появилось бы новых вершин (кроме <tex>bc</tex>), совместимых с <tex>a</tex>.
 
Пусть комбинируется л.м.с.п. <tex>(b, c)</tex>, причем <tex>a</tex> ближе к <tex>b</tex>. Тогда между <tex>a</tex> и <tex>b</tex> нет вершин алфавита и хотя бы одна из <tex>b</tex>, <tex>c</tex> должна быть вершиной алфавита, иначе при слиянии <tex>(b, c)</tex> не появилось бы новых вершин (кроме <tex>bc</tex>), совместимых с <tex>a</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 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} \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 w_{b} \le 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} \leqslant w_{b} \leqslant w_{d}</tex>.  
  
 
Мы доказали, что вес наименьшей вершины, совместимой с любой вершиной, не может уменьшиться. Отсюда следует, что любая л.м.с.п. <tex>(x, y)</tex> останется л.м.с.п. после слияния другой л.м.с.п., потому что <tex>x</tex> останется наименьшей вершиной, совместимой с <tex>y</tex>, и наоборот.
 
Мы доказали, что вес наименьшей вершины, совместимой с любой вершиной, не может уменьшиться. Отсюда следует, что любая л.м.с.п. <tex>(x, y)</tex> останется л.м.с.п. после слияния другой л.м.с.п., потому что <tex>x</tex> останется наименьшей вершиной, совместимой с <tex>y</tex>, и наоборот.
Строка 88: Строка 128:
  
  
Теперь согласно этой лемме нам не придется искать минимально совместимую пару, что весьма долго, достаточно лишь находить л.м.с.п. при этом не важно в каком порядке комбинировать л.м.с.п. По этому нам необходимо иметь массив размера <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> времени.
+
Теперь согласно этой лемме нам не придется искать минимально совместимую пару, что весьма долго. Достаточно лишь находить л.м.с.п., при этом не важно, в каком порядке комбинировать л.м.с.п. По этому нам необходимо иметь массив размера <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  
+
* ''Т.Ч.Ху, М.Т.Шинг'' Комбинаторные алгоритмы. — стр. 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
+
* ''Дональд Кнут'' Искусство программирования, том 3. Сортировка и поиск — 824 с. — ISBN 5-8459-0082-4
  
  

Текущая версия на 19:33, 4 сентября 2022

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


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


Определение:
Пусть [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. Введем следующие понятия.
    • Две вершины называются совместимой парой (англ. compatible pair), если они соседние или если между ними нет вершин алфавита.
    • Две вершины называются минимальной парой, когда их суммарный вес наименьший из всех. При равенстве весов выбирается пара с самой левой вершиной, из всех таких та, у которой правый узел расположен левее.
    • Минимальной совместимой парой называется наименьшая пара из всех совместимых.
  • Шаг 1. Изначально мы имеем только алфавит (и соответствующие веса), отсортированный лексикографически.
  • Шаг 2. Комбинирование (англ. Combining). По данной последовательности из [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], и т.д. пока не останется одна вершина.

Hu-Taker eps1.gif

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

Hu-Taker Layer2.png

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

Hu-Taker eps3.gifHu Takker eps3.png

Осталось только назначить код для каждого символа. Это делается аналогично коду Хаффмана: левым ребрам назначается [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] алгоритма Ху–Таккера, образуют очередь с монотонно возрастающими весами. Потомки каждой из этих новых вершин могут быть соединены в алфавитное бинарное дерево (англ. Alphabetical binary tree), удовлетворяющее условию: если [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. Сортировка и поиск — 824 с. — ISBN 5-8459-0082-4