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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Сложность алгоритма: орфография)
м (rollbackEdits.php mass rollback)
 
(не показаны 32 промежуточные версии 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. ''Введем следующие понятия''. Две вершины называются совместимой парой, если они соседние или если между ними нет вершин алфавита. Две вершины называются минимальной парой, когда их суммарный вес наименьший из всех. При равенстве весов, выбирается пара с самой левой вершиной, из всех таких та у которой правый узел расположен левее. Минимальной совместимой парой называется наименьшая пара из всех совместимых.
+
=== Алгоритм Ху–Таккера ===
 
+
* Начало.
1. ''Комбинирование''. По данной последовательности из n вершин строим последовательность из <tex>n-1</tex> вершины, комбинируя минимальную совместимую пару и заменяя ее левую вершину вершиной с весом <tex> w = w_{l} + w_{r} </tex> и удаляя правую. Эта процедура повторяется до тех пор пока не останется одна вершина.
+
* '''Шаг 0.''' ''Введем следующие понятия''.  
 
+
**Две вершины называются совместимой парой (англ. ''compatible pair''), если они соседние или если между ними нет вершин алфавита.  
2. ''Определение уровней''. Находим номер уровня <tex>l_{i}</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.
+
* '''Шаг 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>.
 +
* Конец.
  
  
 
Заметим, что перестройку легко можно организовать с помощью следующего стекового алгоритма.
 
Заметим, что перестройку легко можно организовать с помощью следующего стекового алгоритма.
 
+
=== Стековый алгоритм перестройки ===
Шаг 0. Стек пуст.
+
* Начало.
 
+
* '''Шаг 0.''' [[Стек]] пуст.
Шаг 1. Если значение двух верхних элементов различно или в стеке всего один элемент перейти к шагу 2, иначе шагу 3.
+
* '''Шаг 1.''' Если значение двух верхних элементов различно или в стеке всего один элемент перейти к шагу <tex>2</tex>, иначе к шагу <tex>3</tex>.
 
+
* '''Шаг 2.''' Поместить следующий элемент <tex>l_{i}</tex> на вершину стека. Перейти к шагу <tex>1</tex>.
Шаг 2. Поместить следующий элемент <tex>l_{i}</tex> на вершину стека.
+
* '''Шаг 3.''' Удалить <tex>2</tex> верхних элемента стека, поместить в стек элемент со значением меньшим на единицу, чем удаленные. Если значение нового элемента равно нулю {{---}} остановиться, иначе перейти к шагу <tex>1</tex>.
 
+
* Конец.
Шаг 3. Удалить 2 верхних элемента стека, поместить в стек элемент со значением меньшим на единицу, чем удаленные, если значение нового элемента равно нулю - остановится, иначе перейти к шагу 1.
 
  
 
==Пример==
 
==Пример==
[[Файл:Hu-Taker_eps1.gif‎|300px|thumb|right]]
+
Для примера возьмем алфавит <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>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>, и т.д. пока не останется одна вершина.
 
  
 +
Объединим сначала <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>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>.
  
 +
Вершину <tex>t</tex> назовем горой между двумя впадинами.
  
 +
Из [[#lemma3|леммы 3]] следует, что можно образовать две отдельных [[Очередь | очереди]] {{---}} одну для каждой впадины. Из-за горы вершины из разных впадин не совместимы  между собой. Когда наименьшие новые вершины(полученные в результате слияния) во впадинах станут достаточно большими, гора будет наконец скомбинирована. С этого момента все новые вершины станут совместимыми. Получается слияние двух очередей. По существу, фаза <tex>1</tex> в алгоритме Ху–Таккера подобна слиянию нескольких очередей, а произвольную последовательность весов можно рассматривать как соединение нескольких впадин.
  
 +
Чтобы понять, почему последовательность уровней может быть соединена в алфавитное дерево на третьем шаге алгоритма, достаточно рассмотреть два случая:
 +
*Комбинируются две вершины из одной впадины.
 +
*Комбинируются две вершины <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>.
  
Выполним второй шаг.
+
Заметим, что это лишь обоснование, а не строгое доказательство, его задача {{---}} дать понимание правдивости алгоритма.
[[Файл:Hu-Taker_Layer.jpg|300px|right|thumb‎]]
 
Определим уровни для каждого листа <tex>L= \{</tex> ''3,3,5,5,4,3,3,3,3,4,4'' <tex>\} </tex>.
 
  
 +
== Корректность алгоритма Ху–Таккера ==
  
 
+
Как пишет Д. Кнут короткого доказательства алгоритма не известно, и вероятно оно никогда не будет найдено. Для доказательства своего алгоритма Ху и Таккеру потребовалось <tex>3</tex> теоремы и <tex>2</tex> леммы (См. книгу Т.Ч.Ху и М.Т.Шинг Комбинаторные алгоритмы {{---}} стр.172).
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Выполним третий шаг воспользовавшись стековым алгоритмом и получим необходимое дерево.
 
 
 
[[Файл:Hu-Taker_eps3.gif|300px]][[Файл:Hu-Taker_Layer2.jpg‎|300px]]
 
 
 
Осталось только назначить код для каждого символа, это делается аналогично коду Хаффмана, левым ребрам назначается 0, а правым 1.
 
 
 
== Корректность алгоритма Ху-Таккера ==
 
 
 
Как пишет Д. Кнут короткого доказательства алгоритма не известно, и вероятно оно ни когда не будет найдено. Для доказательства своего алгоритма Ху и Таккеру потребовалось 3 теоремы и 2 леммы.
 
  
 
== Сложность алгоритма ==
 
== Сложность алгоритма ==
  
Для реализации данного алгоритма потребуется <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>. В частности, в последовательности вершин будет оставаться л.м.с.п., пока комбинируются другие л.м.с.п.  
  
  
 
Из этой леммы следует, что дерево, получаемое комбинированием л.м.с.п., не зависит от того, в каком порядке они комбинируются.  
 
Из этой леммы следует, что дерево, получаемое комбинированием л.м.с.п., не зависит от того, в каком порядке они комбинируются.  
 
|proof=
 
|proof=
Рассмотрим произвольный вершина <tex>a</tex> и предположим, что вес наименьшей вершины, совместимого с <tex>a</tex>, равен <tex>w_{i}</tex>.
+
Рассмотрим произвольную вершину <tex>a</tex> и предположим, что вес наименьшей вершины, совместимой с <tex>a</tex>, равен <tex>w_{i}</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>(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>, и наоборот.
Строка 118: Строка 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
 +
* ''Дональд Кнут'' Искусство программирования, том 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
 

Текущая версия на 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