Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 101
Текст из файла (страница 101)
Такие коды называются ззрефиксмыми (ргейх сопеб) . можно доказать (хотя здесь мы не станем этого делать), что оптимальное сжатие данных, которого можно достичь с помощью кодов, всегда может быль достигнуто при использовании префиксного кода, поэтому рассмотрение одних лишь префиксных кодов не приводит к потере общности. Для любого бинарного кода символов кодирование текста — очень простой процесс: нужно просто соединить кодовые слова, представляющие каждый символ в файле. Например, в кодировке с помощью префиксного кода переменной длины, представленного на рис.
16.3, трехсимвольный файл аЬс имеет вид 0 101 100 = 0101100, где символом "" обозначена операция конкатенации. Предпочтение префиксным кодам отдается из-за того, что они упрощают декодирование. Поскольку никакое кодовое слово не выступает в роли префикса другого, кодовое слово, с которого начинается закодированный файл, определяется однозначно. Начальное кодовое слово легко идентифицировать, преобразовать в исходный символ и продолжить декодирование оставшейся части закодированного файла.
В рассматриваемом примере строка 001011101 однозначно раскладывается на подстроки 0 0. 101 1101, что декодируется как ааЬе. Для упрощения процесса декодирования требуется удобное представление префиксного кода, чтобы можно было легко идентифицировать начальное кодовое слово. Одним из таких представлений является бинарное дерево, листьями которого являются кодируемые символы.
Бинарное кодовое слово, представляющее символ, интерпретируется как простой путь от корня к этому символу. В такой интерпретации 0 означает "перейти к левому дочернему узлу", а 1 — "перейти к правому дочернему узлу". На рис. 16.4 показаны такие деревья для двух кодов, взятых из нашего примера. Заметим, что изображенные на рисунке деревья не являются бинарными деревьями поиска, поскольку листья в них не обязательно расположены в порядке сортировки, а внутренние узлы не содержат ключей символов.
Оптимальный код файла всегда представлен полным бинарным деревом, каждый узел (кроме листьев) которого имеет по два дочерних узла (см. упр. 16.3.2). Код фиксированной длины, представленный в рассмотренном примере, не является оптимальным, поскольку соответствующее ему дерево, изображенное на рис.!6.4,(а), — неполное бинарное дерево: некоторые слова кода начинаются с 10..., но ни одно из них не начинается с 11.... Поскольку здесь мы можем ограничиться только полными бинарными деревьями, можно утверждать, что если С вЂ” алфавит, из которого извлекаются кодируемые символы, и все частоты, с которыми встречаются символы, положительны, то дерево, представляющее оптимальный префиксный код, содержит ровно ~С~ листьев, по одному для каждого символа из множества С, и ровно (С~ — 1 внутренних узлов (см. упр. Б.5.3).
звозыоино, дучше кодошдо бы название '*бесирефиксные коды", однако "ирефиксиые коды" — стандвртный в литературе тернии Глава 1К Жадные алгарааьны л(й(Д 0"' ~ 1 -.. '1 Фб': Яеа 5К~ М 0: ~~ 1~~' ~~ У )н214у~ „'.аЗ: $ИЗ;й':40', ~::юру ':~~ (е) 14) Рнс. 14.4. Деревья, ссатвстствующне схемам каднравяння, предствввснныы на рнс. 16.3. Каждый лист нв рисунке намечен ссствстствующны сыу символом н частотой псявасння, в внусрснннй уюя — суммой чвсссч листьев щс поддерева. (в) Дерева, соответствующее ксду фнкснраввннсй длины в = 000, ..., Г = 101, (0) Дерево, ссствстствующса аптныадьнаыу префнкснаыу кеду в О, Ь = 1О1,..., х 1100. Если имеется дерево Т, соответствующее префиксиому коду, легко подсчитать юличество битов, которые потребуются для кодирования файла.
Пусть для каждого символа с в алфавите С атрибут с.~ген обозначает часппу появления с в файле, а г(т(с) означает глубину листа, представляющего зтот символ в дереве. Заметим, что Йт(с) является также длиной слова, кодирующего символ с. Таким образом, для кодировки файла необходимо количество битов, равное В(Т) = ~~ь с.
~ге() е(тЯ . (16.4) снС Построеиие кода Хаффмаиа Хаффмаи (Нн(йпап) изобрел жадный алгоритм, позволяющий составить оптимальный префиксиый юд, который получил название код Хаффлеаын. В соответствии с линией, намеченной в разделе 16.2, доказательство юрреатиости зтого алгоритма основывается иа свойстве жадного выбора и оптимальной подструкгуре. Вместо того чтобы демонстрировать, что зти свойства выполняются, а затем разрабатывать псевдокод, сначала представим псевдокод.
Это поможет прояснить, как алгоритм осуществляет жадный выбор. В приведенном ниже псевдокоде предполагается, что С вЂ” множество, состоящее из и символов, и что каждый из символов с е С представляет собой обьекг с атрибутом с.угу, определяющим часплу его появления. В алгоритме строится дерево Т, соответствующее оптимальному коду, причем построение идет в восходящем направлении. Процесс построения начинается с множества, состоящего из )С~ листьев, после чего последовательно выполняется )С) — 1 операций "слияния", в результате которых образуется оюичательиое дерево. Для идентификации двух наименее часто встречающихся объектов, подлежащих слиянию, исполь- Назовем зту величину стоимостью дерева Т. ~~4ф ~~~:.ф ~:~~а~ ~~Х$ ()41 ДЬЯ Ейв) ,'чьгт) Часть ГК '«сзтершенствованные методы разработки и аназиза 4бб зуется очередь с приоритетами Я, ключами в которой являются атрибуты 1гед.
В результате слияния двух обьектов образуется новый объект, частота появления которого является суммой частот объединенных объектов. НпеемА14(С) 1 и = )С! 2 Я = С 3 Гог з = 1 го и — 1 4 Выделение памяти для нового узла е 5 з.1е71 = х = ЕХтКАСт-М1Ы(Я) 6 жгздИ = у = ЕхткАст-М114(с4) 7 ж7сгед = х.7гед + у. 1гед 8 11чзект(Я,з) 9 гетцгп ЕхткАст-МпчЯ) // Возврат корня дерева Для рассмотренного ранее примера алгоритм Хаффмана работает так, как показано на рис.
16.5. Поскольку алфавит содержит шесть букв, начальный размер очереди равен и = 6, и дерево строится за пять шагов слияния. Полученное в результате дерево представляет оптимальный префиксный код. Кодовое слово буквы представляет собой последовательность меток ребер на простом пути от корня к листу с этой буквой. В строке 2 инициализируется неубывающая очередь с приоритетами ь4, состоящая из элементов множества С. Цикл 1аг в строках 3-8 поочередно извлекает по два узла, х и у, которые характеризуются в очереди наименьшими частотами, и заменяет их в очереди новым узлом е, представляющим объединение упомянутых выше элементов. Частота появления з вычисляется в строке 7 как сумма частот х и у.
Узел х является левым дочерним узлом г, а у — его правым дочерним узлом. (Этот порядок является произвольным; перестановка левого и правого дочерних узлов приводит к созданию другого кода с той же стоимостью.) После и — 1 объединений в очереди остается один узел — корень дерева кодов, который возвращается в строке 9. Хотя алгоритм приводил бы к такому же результату при полном исключении переменных х и у — путем непосредственного присваивания соответствующих значений атрибутам г. 1е(т и з.
Нд7с1 в строках 5 и 6 и замены строки 7 на е. зтед = з. 1е(1.1гед + х. НдЫ.7гед, — мы асе же будем использовать имена х и у в доказательстве корректности алгоритма. Поэтому лучше оставить эти переменные в псевдокоде. В процессе анализа времени работы алгоритма Хаффмана предполагается, что Я реализована как бинарная неубывающая пирамида (см. главу 6). Для множества С, состоящего из и символов, инициализацию очереди Я в строке 2 можно выполнить за время 0(п) с помощью процедуры Вп1еп-Мпч-НеАЕ из раздела 6.3.
Цикл 1ог в строках 3-8 выполняется ровно и — 1 раз, а поскольку для каждой операции над пирамидой требуется время 0(18 и), вклад цикла во время работы алгоритма равен 0(п!8п). Таким образом, полное время работы процедуры Н11еемА1ч с входным множеством, состоящим из и символов, равно 0(п18п). Глава )б. Жадные алгаршямы 4бу (ь) ~аТЩ ~а~Ус) ('(о: (4~%) ~аДЯ (с:;6,~ 1:,е;б') ш 'т(э~ , 'е% ~а)1йз (б%а) Я(йод й)%У,'; (г) (в)) (;и)) Ге~~в Я~~'! ~,1$ ф! тййб( ):г',5,; 'сазе 1с))й) файф (в) Гаг):" Рис. 1бд. Этапы работы алгоритма Хаффмана для частот, заданных на рнс.
16.3. В кюкдой части показано содержимое очереди, элементы шпорой рассортированы в порядке возрастания их частот. На шждом шаге работы алгоритма обьединжотсл двв объекта (дерева) с самыми низкими частотамн. Листья изображены в виде прямоугольников, в каяшом из воторых укшаны буква н ее частота. Внутренние узлы представлены кругамн, содержюцнми сумму частот дочерних узлов.
Ребро, соелннжошее внутренння узел с левым дочерним узлом, имеет метку О, а ребро, соединшошее его с нрввым дочерним ушам. — метку 1. Кодовое слово для буквы образуется последовательностью меток на ребрах, соединяющих корень с листом, предсташепощим эту букву. (а) Начальное множество нэ и = 6 узлов, по одному для юскдой букам. (6)-(д) Промвкуточные шаги. (е) Окончательное дерево. Это время можно сократить до 0(п 1к )ли), если вместо неубывающей пирамиды воспользоваться деревом ван Эмде Боаса (см. главу 20). Корректность алгоритма Хаффмана Чтобы доказать корректность жадного алгоритма Н()румян, покажем, что задала о построении оптимального префиксного кода демонстрирует свойства жадного выбора и оптимальной подструктуры. В сформулированной ниже лемме показано соблюдение свойства жадного выбора.
Лемма 1(ь2 Пусть С вЂ” алфавит, каждый символ с е С которого встречается с частотой с.~гед. Пуси х и у — два символа алфавита С с самыми низкнмн частотами. Тогда для алфавита С существует оптимальный префиксный код, ш)повые слова символов х и у в котором имеют одинаковую длину н отличаются лишь последним битом.
ф (сиз. ()Ь„'1~. (Ь(л) фас, 1й(зу)' ('-''в(й( (в) ЯФ Ог ~( ОУ ()) (е;а1 ~~уй (,(й) (шу(б) (ь' ),( 1-в)йй ~(„'йт 4бб сзасть з'К усовершенствованные методы разработки и анализа Доказаввельеввво. Идея доказательства состоит в том, чтобы взять дерево Т, представляющее произвольный оптимальный префиксный код, и преобразовать его в дерево, представляющее другой оптимальный префиксный код, в котором символы х и у являются листьями с общим родительским узлом, причем в новом дереве эти листья находятся на максимальной глубине.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
