Изменения

Чтобы доказать корректность жадного алгоритма Huffman, покажем, что в за- даче задаче о построении оптимального префиксного кода проявляются свойства жадного выбора и оптимальной подструктуры. В сформулированной ниже лемме показано соблюдение свойства жадного выбора.  {{Лемма 16.2. |id=lemma1|about=1|statement=Пусть С <tex>C</tex> — алфавит, каждый символ с€С <tex>c \in C</tex> которого встречается с ча- стотой / частотой <tex>f[сc]</tex>. Пусть х <tex>x</tex> и у <tex>y</tex> — два символа алфавита С <tex>C</tex> с самыми низкими частотами. Тогда для алфавита С <tex>C</tex> существует оптимальный префиксный код, кодовые слова символов х <tex>x</tex> и у <tex>y</tex> в котором имеют одинаковую длину и отличаются лишь последним битом. Доказательство. |proof=Идея доказательства состоит в том, чтобы взять дерево Т<tex>T</tex>, пред- ставляющее представляющее произвольный оптимальный префиксный код, и преобразовать его в дерево, представляющее другой оптимальный префиксный код, в котором сим- волы х символы <tex>x</tex> и у <tex>y</tex> являются листьями с общим родительским узлом, причем в новом дереве эти листья находятся на максимальной глубине. Пусть а <tex>a</tex> и <tex>b </tex> — два символа, представленные листьями с общим родительским узлом, которые находятся на максимальной глубине дерева Т<tex>T</tex>. Предположим без потери общности, что / <tex>f[аa] ^ / \le f[Ьb] </tex> и / <tex>f[хx] ^ / \le f[уy]</tex>. Поскольку / <tex>f[хx] </tex> и / <tex>f[уy] </tex> — две самые маленькие частоты (в указанном порядке), а / <tex>f[аa] </tex> и / <tex>f[6b] </tex> — две произвольные частоты, то выполняются соотношения <tex>f[x]^\le f [аa] </tex> и / <tex>f[уy] ^ / \le f[6b]</tex>. Как показано на рис. 16.5, в В результате перестановки в дереве Т <tex>T</tex> листьев а <tex>a</tex> и х <tex>x</tex> получается дерево Т"<tex>T'</tex>, а при последующей перестановке в дереве V листьев Ь <tex>b</tex> и у <tex>y</tex> получается дерево Т". Согласно уравнению A6<tex>T''</tex>.5), разность Разность стоимостей деревьев Т и Т" равна <br>В<tex>B(ТT)-В B(ГT') = ?/\sum_{c \in C} f(c)dr d_T(сC) - ?/\sum_{c \in C} f(c)d_{T'}(fev (сC) = сес сес = f [x] dT (х) + f [a] dT (а) - f [x] dT, (х) - </ [a] dTtex><br><tex> (а) = = / [х] dT (х) + / [a] dT (а) - / [х] dT (а) - / [а] dT (x) = = (f[a]-f[x}])(dTd_T(a)-dTd_T(x))\ge 0</tex>0, <br> поскольку величины / <tex>f[аa]-/ f[хx] </tex> и йт <tex>d_T(aj—dr a) - d_T(x) </tex> неотрицательны. Величина / <tex>f[аa] — - f [хx] </tex> неотрицательна, потому что х — лист с минимальной частотой, величина <tex>d_T(оa) — dr - d_T(x) </tex> неотрицательна, потому что а <tex>a</tex> — лист на максимальной глубине Глава 16. Жадные алгоритмы 465 Рис. 16.5. Иллюстрация ключевых этапов доказательства леммы 16.2 в дереве Т<tex>T</tex>. Аналогично, перестановка листьев у <tex>y</tex> и <tex>b </tex> не приведет к увеличению стоимости, поэтому величина В <tex>B(Т"T') — В - B(Т"T'') </tex> неотрицательна. Таким образом, выполняется неравенство В <tex>B(Г"T') ^ В \le B(ТT'')</tex>, и поскольку Т <tex>T</tex> — оптимальное дерево, то должно также выполняться неравенство В <tex>B(ТT'') < В \le B(Т"T')</tex>, откуда следует, что В {Т"<tex>B(T') = В B(ТT'')</tex>. Таким образом, Т" <tex>T''</tex> — оптимальное дерево, в котором х <tex>x</tex> и у <tex>y</tex> — находящиеся на максимальной глубине дочерние листья одного и того же узла, что и доказывает лемму. д Из леммы 16.2 следует, что процесс построения оптимального дерева путем }}объединения узлов без потери общности можно начать с жадного выбора, при котором объединению подлежат два символа с наименьшими частотами. Почему {{Лемматакой выбор будет жадным? Стоимость объединения можно рассматривать как сумму частот входящих в него элементов|id=lemma2. В упражнении 16.3-3 предлагается показать, что полная стоимость сконструированного таким образом дерева равна |about=2сумме стоимостей его составляющих. Из всевозможных вариантов объединения на каждом этапе в процедуре Huffman выбирается тот, в котором получается минимальная стоимость. В приведенной ниже лемме показано, что задача о составлении оптимальных префиксных кодов обладает свойством оптимальной подструктуры. Лемма 16.3. |statement=Пусть дан алфавит С<tex>C</tex>, в котором для каждого символа се С опре- делены <tex>c \in C</tex> определены частоты / <tex>f[сc]</tex>. Пусть х иу <tex>x</tex> и <tex>y</tex> — два символа из алфавита С <tex>C</tex> с минимальными частотами. Пусть С <tex>C'</tex> — алфавит, полученный из алфавита С <tex>C</tex> путем удаления сим- волов х символов <tex>x</tex> и у <tex>y</tex> и добавления нового символа <tex>z</tex>, так что С <tex>C = С C — {х,у} U \cup {z}</tex>. По определению частоты <tex>f</ tex> в алфавите С <tex>C'</tex> совпадают с частотами в алфавите С<tex>C</tex>, за исключением частоты / <tex>f[z] = f [x] + / f[уy]</tex>. Пусть Т" <tex>T'</tex> — произвольное дерево, представляющее оптимальный префиксный код для алфавита С <tex>C'</tex> Тогда дерево Г<tex>T</tex>, полученное из дерева Т" <tex>T'</tex> путем замены листа <tex>z </tex> внутренним узлом с дочерними элементами х <tex>x</tex> и у<tex>y</tex>, представляет оптимальный префиксный код для алфавита С<tex>C</tex>. Доказательство. |proof=Сначала покажем, что стоимость В <tex>B(ГT) </tex> дерева Г <tex>T</tex> можно выра- зить выразить через стоимость В <tex>B(Т"T') </tex> дерева Т", рассматривая стоимости компонентов из уравнения A6.5)<tex>T'</tex>. Для каждого символа се С — <tex>c \le C - {хx,уy} </tex> выполняется соотношение 466 Часть IV. Усовершенствованные методы разработки и анализа Aт {с<tex>d_T(C) = йтd_{T' }(сc)</tex>, следовательно, /<tex>f[сc]Aтd_T(сC) = /f[c]d^d_{T'}(c)</tex>. Поскольку dr <tex>d_T(#x) = = dr d_{T}(уy) = drd_{t' B:}(z) + 1</tex>, получаем соотношение <br>/ <tex>f[хx] dT d_T(хx) + f [уy] dT d_{T}(уy) = (/ f[хx] + f [y])(d_{уT'}(z) + 1) = f[z]d_{dT> T'}(z) + 1(f[x] + f[y]) = </tex><br>из которого следует равенство <br><tex> B(T) = B(T')+f[x) ] + f[y] </tex> <br>ИЛИ <br><tex> B{(T')=B(T)-f[x]-f[y]</tex>. <br>Докажем лемму методом от противного. Предположим, дерево Т <tex> T </tex> не представ- ляет представляет оптимальный префиксный код для алфавита С <tex> C </tex>. Тогда существует дерево Т"<tex> T'' </tex>, для которого справедливо неравенство В<tex> B(Т"T'') < В{ТB(T)</tex>. Согласно лемме 16.2(1), х <tex>x</tex> и у <tex>y</tex> без потери общности можно считать дочерними элементами одного и того же узла. Пусть дерево Т"<tex>T''' </tex> получено из дерева Т" <tex>T''</tex> путем замены элементов х <tex>x</tex> и у <tex>y</tex> листом <tex>z </tex> с частотой / <tex>f[z] = / f[хx] + f [уy]</tex>. Тогда можно записать: <br> <tex>B(T"''')=B{(T"'')-f[x}] -f{[y}] <B(T)-f[x}] -f[y} ] = B(T')</tex>, <br> что противоречит предположению о том, что дерево Т<tex>T' </tex> представляет оптимальный префиксный код для алфавита С<tex>C'</tex>. Таким образом, дерево Г <tex>T</tex> должно представлять оптимальный префиксный код для алфавита С<tex>C</tex>. }} Лемма 16.3. Доказательство. ?

Справедливость теоремы непосредственно следует из лемм (1 ) и (2)