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