Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 96
Текст из файла (страница 96)
Пусть дан алфавит С, в котором для каждого символа с Е С определены частоты г" [с). Пусть х и у — два символа из алфавита С с минимальными частотами. Пусть С' — алфавит, полученный из алфавита С путем удаления символов х и у и добавления нового символа х, так что С' = С вЂ” [х, у) 0 1х). По определению частоты г в алфавите С' совпадают с частотами в алфавите С, за исключением частоты г [з] = г [х) + г' [у). Пусть Т' — произвольное дерево, представляющее оптимальный префиксный код для алфавита С'. Тогда дерево Т, полученное из дерева Т' путем замены листа з внутренним узлом с дочерними элементами х и у, представляет оптимальный префиксный код для алфавита С.
Доказательство. Сначала покажем, что стоимость В (Т) дерева Т можно выразить через стоимость В (Т') дерева Т', рассматривая стоимости компонентов из уравнения (16.5). Для каждого символа с Е С вЂ” 1х, у) выполняется соотношение Из леммы 16.2 следует, что процесс построения оптимального дерева путем объединения узлов без потери общности можно начать с жадного выбора, при котором объединению подлежат два символа с наименьшими частотами. Почему такой выбор будет жадным? Стоимость объединения можно рассматривать как сумму частот входящих в него элементов. В упражнении !6.3-3 предлагается показать, что полная стоимость сконструированного таким образом дерева равна сумме стоимостей его составляющих. Из всевозможных вариантов объединения на каждом этапе в процедуре НиггмАм выбирается тот, в котором получается минимальная стоимость.
В приведенной ниже лемме показано, что задача о составлении оптимальных префиксных кодов обладает свойством оптимальной подструктуры. Часть!У. Усовершенствованные методы разработки и анализа 466 йт(с) = г1т (с), следовательно, г" [с] йт (с) = г" [с] йт (с). Поскольку с1т (х) = = пт (У) = Йт (а) + 1, получаем соотношение У[х] г1т (х) + Х [у] г1т (у) = (У [х] + г" [у]) (г1т (з) + 1) = = ~ [з] "т [з)+ У[х]+ У [у]) из которого следует равенство В (Т) = В (Т') + г' [х] + г" [у], В (Т~) = В (Т) — г [х] — г [у] . Докажем лемму методом от противного. Предположим, дерево Т не представляет оптимальный префиксный код для алфавита С. Тогда существует дерево Т", для которого справедливо неравенство В (Тв) < В (Т). Согласно лемме 16.2, х и у без потери общности можно считать дочерними элементами одного и того же узла.
Пусть дерево Тсч получено из дерева Т" путем замены элементов х и у листом х с частотой г" [а] = г" [х] + г" [у]. Тогда можно записать: В (Тв') = В (Тв) — г" [х] — г" [у] < В(Т) — г" [х] — г' [у] = В (Т'), что противоречит предположению о том, что дерево Т' представляет оптимальный префиксный код для алфавита С'. Таким образом, дерево Т должно представлять оптимальный префиксный код для алфавита С. П Теорема 16.4. Процедура Н11ггмлн дает оптимальный префиксный код. Доказательсгиао.
Справедливость теоремы непосредственно следует из лемм 16.2 и 16.3. и Упражнения 16.3-1. Докажите, что бинарное дерево, которое не является полным, не может соответствовать оптимальному префиксному коду. 16.3-2. Определите оптимальный код Хаффмана для представленного ниже мно- жества частот, основанного на первых восьми числах Фибоначчи. а:1 Ь:1 с:2 с1:3 е:5 й:8 д:13 1т:21 Попытайтесь обобщить ответ на случай первых и чисел Фибоначчи. 16.3-3. Докажите, что полную стоимость дерева, представляющего какой-нибудь код, можно также вычислить как сумму комбинаций частот двух дочерних узлов по всем внутренним узлам. Глава 16.
Жадные алгоритмы 467 16.3-4. Докажите, что если символы отсортированы в порядке монотонного убывания частот, то существует оптимальный код, длина слов в котором— монотонно неубывающая величина. 16.3-5. Предположим, имеется оптимальный префиксный код для множества С = (О, 1,..., п — Ц и мы хотим передать его, использовав как можно меньше битов. Покажите, как представить любой оптимальный префиксный код для множества С с помощью всего 2п — 1+ и ~18п1 битов. (Указание: для представления структуры дерева, определяемой его обходом, достаточно 2п — 1 битов.) 16.3-6. Обобщите алгоритм Хаффмана для кодовых слов в троичной системе счисления (т.е.
слов, в которых используются символы О, 1 и 2) и докажите, что с его помощью получается оптимальный троичный код. 16.3-7. Предположим, что файл данных содержит последовательность 8-битовых символов, причем все 256 символов встречаются достаточно часто: максимальная частота превосходит минимальную менее чем в два раза.
Докажите, что в этом случае кодирование Хаффмана по эффективности не превышает обычный 8-битовый юд фиксированной длины. 16.3-8. Покажите, что в среднем ни одна схема сжатия не в состоянии даже на один бит сжать файл, состоящий из случайных 8-битовых символов. (Указание: сравните количество возможных файлов с количеством сжатых файлов.) *16.4 Теоретические основы жадных методов В этом разделе в общих чертах рассматривается элегантная теория жадных алгоритмов. Она оказывается полезной, когда нужно определить, когда жадный метод дает оптимальное решение. Эта теория содержит комбинаторные структуры, известные под названием "матроиды".
Несмотря на то, что рассматриваемая теория не описывает все случаи, для которых применим жадный метод (например, она не описывает задачу о выборе процессов из раздела 16.1 или задачу о кодах Хаффмана из раздела 16.3), она находит применение во многих случаях, представляющих практический интерес. Более того, эта теория быстро развивается и обобщается, находя все больше приложений. В юнце данной главы приводятся ссылки на литературу, посвященную этой теме. Матроиды Маюироид (та1гоЫ) — это упорядоченная пара М = (Я,2), удовлетворяющая сформулированным ниже условиям. Часть 1Ч.
Усовершенствованные методы разработки и анализа 468 1. Множество Я конечное. 2. 2' — непустое семейство подмножеств множества Я (которые называются независимыми подмножествами), таких что если В Е 2 и А С В, то А Е 2. Если семейство 2' удовлетворяет этому свойству, то его называют наследственным (легей~агу). Заметим, что пустое множество 9 с необходимостью принадлежит семейству 2. 3. Если А Е 2; В Е 2' и 1А( < 1В), то существует такой элемент х Е А — В, что А 0 1х) Е 2'.
Говорят, что структура М удовлетворяет свойству замени (ехспалйе ргорепу). Термин "матроид" был введен Хасслером Уитни (Назз1ег%Ыгпеу). Он изучал матричные матроиды, элементами Я которых являются строки заданной матрицы. Множество строк является независимым, если они линейно независимы в обычном смысле. Легко показать, что эта структура задает матроид (см. упражнение 16А-2). В качестве другого примера матроида рассмотрим графовый матроид Мс = = (Яс,Х~), определенный ниже в терминах неориентированного графа С = = ('г', Е).
° Яс — множество Е ребер графа С. ° Если А — подмножество множества Е, то А е 2г: тогда и только тогда, когда множество А ациклическое, т.е. множество ребер А независимо тогда и только тогда, когда подграф Сл = (Ъ', А) образует лес. Графовый матроил Мс тесно связан с задачей о минимальном остовном дереве, подробно описанном в главе 23. Теорема 16.5. Если С = (К Е) — неориентированный граф, то Мс = (Яс, Тс)— матроид. Доказательство. Очевидно, что Яс: = Š— конечное множество. Кроме того, Тгз — наследственное семейство, поскольку подмножество леса является лесом. Другими словами, удаление ребер из ацикличесюго множества ребер не может привести к образованию циклов.
Таким образом„осталось показать, что структура Мс удовлетворяет свойству замены. Предположим, что Сл = ('г', А) и Сн = (Ъ; В) — леса графа С и что ~В( > 1А(, те. А и  — ациклические множества ребер, и в множестве В содержится больше ребер, чем во множестве А. Из теоремы Б.2 следует, что лес, в котором имеется )я ребер, содержит ровно 1'Ц вЂ” 1с деревьев.
(Чтобы доказать это другим путем, начнем с 1Ц деревьев, каждое из которых содержит толью одну вершину и не содержит ни одного ребра. Тогда каждое ребро, которое добавляется в лес, на единицу уменьшает Глава 16. Жадные алгоритмы 469 количество деревьев.) Таким образом, лес СА содержит )Ц вЂ” (А! деревьев, а лес Сн — ٠— )В! деревьев. Поскольку в лесу Сн меньше деревьев, чем в лесу СА„ в нем должно содержаться некоторое дерево Т, вершины которого принадлежат двум различным деревьям леса Сл.
Более того, так как дерево Т вЂ” связное, оно должно содержать таюе ребро (и, о), что вершины и и о принадлежат разным деревьям леса Сл. Поскольку ребро (и, о) соединяет вершины двух разных деревьев леса СА, его можно добавить в лес Сд, не образовав при этом цикла. Таким образом, структура Мг, удовлетворяет свойству замены, что и завершает доказательство того, что Мг, — матроид.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
