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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
м (rollbackEdits.php mass rollback)
 
(не показаны 23 промежуточные версии 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.''' Изначально мы имеем только алфавит (и соответствующие веса) отсортированный лексикографически.
+
* '''Шаг 1.''' Изначально мы имеем только алфавит (и соответствующие веса), отсортированный лексикографически.
* '''Шаг 2.''' ''Комбинирование''. По данной последовательности из n вершин строим последовательность из <tex>n-1</tex> вершины, комбинируя минимальную совместимую пару и заменяя ее левую вершину вершиной с весом <tex> w = w_{l} + w_{r} </tex> и удаляя правую. Эта процедура повторяется до тех пор пока не останется одна вершина.
+
* '''Шаг 2.''' ''Комбинирование'' (англ. ''Combining''). По данной последовательности из <tex>n</tex> вершин строим последовательность из <tex>n-1</tex> вершины, комбинируя минимальную совместимую пару и заменяя ее левую вершину вершиной с весом <tex> w = w_{l} + w_{r} </tex> и удаляя правую. Эта процедура повторяется до тех пор, пока не останется одна вершина.
 
* '''Шаг 3.''' ''Определение уровней''. Находим номер уровня <tex>l_{i}</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>. Повторяем этот процесс до тех пор пока не останется одна вершина с уровнем 0.
+
* '''Шаг 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>.
 
* Конец.
 
* Конец.
  
Строка 34: Строка 37:
 
=== Стековый алгоритм перестройки ===
 
=== Стековый алгоритм перестройки ===
 
* Начало.
 
* Начало.
* '''Шаг 0.''' Стек пуст.
+
* '''Шаг 0.''' [[Стек]] пуст.
* '''Шаг 1.''' Если значение двух верхних элементов различно или в стеке всего один элемент перейти к шагу 2, иначе шагу 3.
+
* '''Шаг 1.''' Если значение двух верхних элементов различно или в стеке всего один элемент перейти к шагу <tex>2</tex>, иначе к шагу <tex>3</tex>.
* '''Шаг 2.''' Поместить следующий элемент <tex>l_{i}</tex> на вершину стека.
+
* '''Шаг 2.''' Поместить следующий элемент <tex>l_{i}</tex> на вершину стека. Перейти к шагу <tex>1</tex>.
* '''Шаг 3.''' Удалить 2 верхних элемента стека, поместить в стек элемент со значением меньшим на единицу, чем удаленные, если значение нового элемента равно нулю - остановится, иначе перейти к шагу 1.
+
* '''Шаг 3.''' Удалить <tex>2</tex> верхних элемента стека, поместить в стек элемент со значением меньшим на единицу, чем удаленные. Если значение нового элемента равно нулю {{---}} остановиться, иначе перейти к шагу <tex>1</tex>.
 
* Конец.
 
* Конец.
  
 
==Пример==
 
==Пример==
Для примера возьмем алфавит <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>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>, и т.д. пока не останется одна вершина.
+
Объединим сначала <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]]
 
[[Файл:Hu-Taker_eps1.gif‎|300px]]
  
Выполним второй шаг.
+
Выполним третий шаг.
Определим уровни для каждого листа <tex>L= \{</tex> ''3,3,5,5,4,3,3,3,3,4,4'' <tex>\} </tex>.
+
Определим уровни для каждого листа <tex>L= \{3,3,5,5,4,3,3,3,3,4,4\} </tex>.
 +
 
 +
[[Файл:Hu-Taker Layer2.png|300px]]
 +
 
 +
Выполним четвертый шаг, воспользовавшись стековым алгоритмом, и получим необходимое дерево.
 +
 
 +
[[Файл:Hu-Taker_eps3.gif|300px]][[Файл:Hu Takker eps3.png ‎|300px]]
 +
 
 +
Осталось только назначить код для каждого символа. Это делается аналогично [[Алгоритм Хаффмана|коду Хаффмана]]: левым ребрам назначается <tex>0</tex>, а правым <tex>1</tex>.
 +
 
 +
== Обоснование алгоритма Ху–Таккера ==
 +
 
 +
Далее последовательностью–впадиной будем называть последовательность вида <tex>w_{1} > ... > w_{t} < ... < w_{n}</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).
  
 
== Сложность алгоритма ==
 
== Сложность алгоритма ==
Строка 68: Строка 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>. В частности, в последовательности вершин будет оставаться л.м.с.п., пока комбинируются другие л.м.с.п.  
  
  
Строка 82: Строка 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>, и наоборот.
Строка 90: Строка 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