|
||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[111] Построение кода Хаффмена Хаффмен построил жадный алгоритм, который строит оптимальный префиксный код. Этот код называется кодом Хаффмена (Huffman code). Алгоритм строит дерево Г, соответствующее оптимальному коду, снизу вверх, начиная с множества из \С\ листьев и делая \С\ - 1 «слияний». Мы предполагаем, что для каждого символа с £ С задана его частота f[c]. Для нахождения двух объектов, подлежащих слиянию, используется очередь с приоритетами Q, использующая частоты / в качестве рангов - сливаются два объекта с наименьшими частотами. В результате слияния получается новый объект (внутренняя вершина), частота которого считается равной сумме частот двух сливаемых объектов. Huffman (С) 9 return Extract-Min(Q) Работа этого алгоритма для нашего примера показана на рис. 17.5. Поскольку имеется всего 6 букв, первоначально очередь имеет размер га = 6, и для построения дерева нужно сделать 5 слияний. Префиксный код соответствует дереву, полученному в результате всех этих слияний. В строке 2 алгоритма в очередь Q помещаются символы из алфавита С (с соответствующими частотами). В цикле (строки 3-8) повторяется га - 1 раз следующая операция: из очереди изымаются две вершины ж и у с наименьшими частотами /[ж] и f[y], которые заменяются на одну вершину z с частотой /[ж] + f[y] и детьми ж и у (кого из них считать левым ребёнком, а кого правым - неважно: код получится другой, но его стоимость будет та же). В конце в очереди остаётся один узел - корень построенного двоичного дерева. Ссылка на него возвращается в строке 9. Оценим время работы алгоритма, считая, что очередь Q реализована в виде двоичной кучи (см. главу 7). Инициализацию Q в строке 2 можно провести за О (га) операций с помощью процедуры Build-Heap из раздела 7.3. Цикл в строках 3-8 исполняется ровно га - 1 раз; поскольку каждая операция с кучей требует времени О (log га), общее время будет О (га log га). Стало быть, время работы алгоритма Huffman для алфавита из га символов будет О (га log га). 1 2 3 4 5 6 7 8 п\С\ for г 1 to га - 1 Рис. 17.5 Применение алгоритма Хаффмена к таблице частот рис. 17.3. Показаны последовательные состояния очереди (в порядке возрастания частот). На каждом шаге сливаются два поддерева с наименьшими частотами. Листья - прямоугольники, в которых символ и его частота разделены двоеточием. Внутренние вершины изображены кружками, в которых указаны суммы частот их детей. Ребро, идущее к левому ребёнку, помечено нулем, к правому - единицей. В результирующем дереве код любого символа написан на пути, ведущем из корня к этому символу, (а) Начальная стадия: п = 6 листьев, по одному на символ, (б)-(д) Промежуточные стадии, (е) Готовое дерево. Правильность алгоритма Хаффмена Чтобы доказать, что жадный алгоритм Huffman действительно даёт оптимум, мы покажем, что для задачи об оптимальном префиксном коде выполнены принцип жадного выбора и свойство оптимальности для подзадач. Начнём с принципа жадного выбора. Лемма 17.2. Пусть в алфавите С каждый символ с £ С имеет частоту /[с]. Пусть х,у G С - два символа с наименьшими частотами. Тогда для С существует оптимальный префиксный код, в котором последовательности битов, кодирующие х и у, имеют одинаковую длину и различаются только в последнем бите. Доказательство. Утверждение леммы будет выполнено, если листья, соответствующие хну, будут братьями. Рассмотрим дерево Г, соответствующее произвольному оптимальному префиксно- Рис. 17.6 Доказательство леммы 17.2. Здесь Ъ и с - наиболее удалённые от корня листья-братья, а £ и у - листья с наименьшими частотами. Обмен х и Ъ превращает дерево Т в Т", а обмен у и с превращает Т в Г". При каждой из перестановок стоимость дерева не возрастает. му коду, и покажем, что его можно модифицировать, не нарушая оптимальности, так, чтобы вышеуказанное условие выполнялось. В самом деле, рассмотрим пару соседних (имеющих общего родителя) листьев в дереве Г, находящуюся на максимальном расстоянии от корня. (Такие существуют: в оптимальном дереве все внутренние вершины имеют степень 2, и потому лист наибольшей глубины имеет брата.) Символы, стоящие в этих листьях (назовём их бис) - не обязательно ж и у, но заведомо имеют не меньшие частоты (поскольку ж и у были двумя наиболее редкими символами). Не ограничивая общности, можно считать, что /[ж] f[b] и f[y] /[с]. Теперь поменяем местами в дереве Г символы Ь и ж (полученное дерево назовём Г), а затем символы сиу (полученное дерево назовём Г"). После таких обменов ж и у (см. пример на рис. 17.6) станут братьями, находящимися на максимальной глубине. Осталось убедиться, что при обменах стоимость дерева не возрастает и, следовательно, дерево Т" также является оптимальным. Другими словами, мы должны проверить, что В(Т) В(Т) В(Т"), где В - функция стоимости. В самом деле, стоимость определяется как сумма по всем листьям произведений частоты на глубину (17.3). При переходе от Г к Г в этой сумме меняются только два слагаемых: f[b]dx(b) + f[x\dj(x) заменяется на f[b]d,Ti(b) + f[x]dx(x), т.е. на f[b]dT(x) + f[x]dx(b). Таким образом, В(Т) - В(Т) = f[b]dT(b) + f[x]dT(x) - f[b]dT(x) - f[x]dT(b) = = (f[b]-f[x])(dT(b)-dT(x))0. Обе скобки неотрицательны: вспомним, что /[ж] f[b] и что dr(b) б?х(ж), так как лист b был одним из наиболее удалённых от корня. Аналогичным образом В(Т) В(Т"), так что В(Т) В(Т"), и поэтому Т" также оптимально (а все наши неравенства Доказанная лемма показывает, что построение оптимального дерева всегда можно начать со слияния двух символов с наименьшей частотой. Следующее наблюдение оправдывает название «жадный» для такого алгоритма. Назовём стоимостью слияния сумму частот □ |
Среды: Smalltalk80 MicroCap Local bus Bios Pci 12С ML Микроконтроллеры: Atmel Intel Holtek AVR MSP430 Microchip Книги: Емкостный датчик 500 схем для радиолюбителей часть 2 (4) Структура компьютерных программ Автоматическая коммутация Кондиционирование и вентиляция Ошибки при монтаже Схемы звуковоспроизведения Дроссели для питания Блоки питания Детекторы перемещения Теория электропривода Адаптивное управление Измерение параметров Печатная плата pcad pcb Физика цвета Управлении софтверными проектами Математический аппарат Битовые строки Микроконтроллер nios Команды управления выполнением программы Перехода от ahdl к vhdl Холодный спай Усилители hi-fi Электронные часы Сердечники из распылённого железа Анализ алгоритмов 8-разрядные КМОП Классификация МПК История Устройства автоматики Системы и сети Частотность Справочник микросхем Вторичного электропитания Типы видеомониторов Радиобиблиотека Электронные системы Бесконтекстный язык Управление техническими системами Монтаж печатных плат Работа с коммуникациями Создание библиотечного компонента Нейрокомпьютерная техника Parser Пи-регулятор ч.1 ПИ-регулятор ч.2 Обработка списков Интегральные схемы Шина ISAВ Шина PCI Прикладная криптография Нетематическое: Взрывной автогидролиз Нечеткая логика Бытовые установки (укр) Автоматизация проектирования Сбор и защита Дискретная математика Kb радиостанция Энергетика Ретро: Прием в автомобиле Управление шаговым двигателем Магнитная запись Ремонт микроволновки Дискретные системы часть 2 | ||