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