Алгоритмы - построение и анализ (1021735), страница 93
Текст из файла (страница 93)
Для любого бинарного кода символов кодирование текста — очень простой процесс: надо просто соединить кодовые слова, представляющие каждый символ в файле. Например, в кодировке с помощью префиксного кода переменной длины, представленного в табл. 16.1, трехсимвольный файл аЬс имеет вид 0 101 100 = = 0101100, где символом "'* обозначена операция конкатенации. Предпочтение префиксным кодам отдается из-за того, что они упрощают декодирование.
Поскольку никакое кодовое слово не выступает в роли префикса другого, кодовое слово, с которого начинается закодированный файл, определяется однозначно. Начальное кодовое слово легко идентифицировать, преобразовать его в исходный символ и продолжить декодирование оставшейся части закодированного файла.
В рассматриваемом примере строка 001011101 однозначно раскладывается на подстроки 0 0 101 1101, что декодируется как ааЬе. Для упрощения процесса декодирования требуется удобное представление префиксного кода, чтобы кодовое слово можно было легко идентифицировать. Одним из таких представлений является бинарное дерево, листьями которого являются кодируемые символы.
Бинарное кодовое слово, представляющее символ, интерпретируется как путь от корня к этому символу. В такой интерпретации О означает "перейти к левому дочернему узлу", а 1 — "перейти к правому дочернему узлу". На рис. 16.3 показаны такие деревья для двух кодов, взятых из нашего примера. Каждый лист на рисунке помечен соответствующим ему символом и частотой появления, а внутренний узел — суммой частот листьев его поддерева.
В части а рисунка приведено дерево, соответствующее коду фиксированной длины, где а = 000, ..., у' = 101. В части 6 показано дерево, соответствующее оптимальному префиксному коду а = О, Ь = 101, ..., г" = 1100. Заметим, Возможно, лучше подошло бы название "беспрефиксные коды", однако "префиксные коды"— стандартный в литературе термин. Глава 16. Жадные алгоритмы 461 600 ))) ! т:5 ) (в:9 ~ б) а) Рис.
16.3. Деревья, соответствующие схемам кодирования, приведенным в табл. 16.1 что изображенные на рисунке деревья не являются бинарными деревьями поиска, поскольку листья в них не обязательно расположены в порядке сортировки, а внутренние узлы не содержат ключей символов. Оптимальный код файла всегда может быть представлен полным бинарным деревом, в котором у каждого узла (кроме листьев) имеется по два дочерних узла (см. упражнение 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 Д'-,~,1 1-„-.9-; ~рзч ~ь„,'.П~ Г819~ ~~85~ Рис. 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}
