Анализ алгоритма Оптимальность
Напомним, как работает алгоритм для этого экземпляра: он объединяет две бук- вы с наименьшей частотой у*, z* S в одну букву ω, рекурсивно вызывает себя для сокращенного алфавита S' (в котором у* и z* заменены ω) и посредством индукции строит оптимальный префиксный код для S', представленный размеченным бинар- ным деревом T'. Полученный код расширяется в дерево T для S, для чего листья у* и z* присоединяются как дочерние узлы к узлу T с меткой ω.
Между метриками ABL(T) и ABL(T') существует тесная связь (первая — среднее количество битов, используемых для кодирования букв S, а вторая — среднее ко- личество битов,используемых для кодирования букв S').
Доказательство.
Глубина каждой буквы х, за исключением у*, z , одинакова в T и T'. Кроме того, каждая из глубин у* и z* в T на 1 больше глубины ω в T'. Используя это отношение, а также тот факт, чтo/„ =/* +/_*, получаем
При помощи этой формулы теперь можно переходить к доказательству опти- мальности.
(4.33) Код Хаффмана для заданного алфавита обеспечивает минимальное среднее количество битов на букву в любом префиксном коде.
Доказательство. Действуя от обратного, предположим, что построенное жад- ным алгоритмом дерево T не является оптимальным. Это означает, что существу- ет размеченное бинарное дерево Z, такое что ABL(Z) < ABL(T ); а согласно (4.31), существует такое дерево Z, в котором листья, представляющие у* и z* являются одноранговыми.
Теперь легко прийти к противоречию: если удалить из Z листья с метками у* и z* и пометить их бывшего родителя ω, мы получаем дерево Z', определяющее префиксный код S'. По тому же принципу, по которому дерево T получается из T', дерево Z получается из Z' посредством добавления листьев у* и z* под ω; следова- тельно, равенство из (4.32) также применимо к Z и Z' : ABL(Z') = ABL(Z) - f
Но мы предполагали, что ABL(Z) < ABL(T ); вычитаяf из обеих сторон неравен- ства, получаем ABL(Z') < ABL(T'), что противоречит оптимальности T' как префикс- ного кода S'. ■
Еще по теме Анализ алгоритма Оптимальность:
- § 2. АЛГОРИТМ АНАЛИЗА ПСИХОЛОГО-ПЕДАГОГИЧЕСКИХ СИТУАЦИЙ
- Sшrvig Morten. Базовые алгоритмы Qt 4 (Qt 4's Generic Algorithms), 2000
- Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science, 2016
- АЛГОРИТМ
- АЛГОРИТМ УДАЧИ
- Алгоритм исцеления:
- Алгоритм избавления от боли
- Оптимальные условия
- 2. Специфика и алгоритмы работы с источниками.
- Алгоритм обработки результатов.
- АКТИВАЦИЯ: УРОВЕНЬ ОПТИМАЛЬНЫЙ
- ПОРОГ РАЗЛИЧЕНИЯ ОПТИМАЛЬНОГО
- 6.2.4. Поиск оптимальной финансовой модели СМИ
- 1.1.4. Оптимальная модель социальной сферы современного общества
- СИСТЕМНАЯ ДИАГНОСТИКА АЛГОРИТМ ОБНАРУЖЕНИЯ И УСТРАНЕНИЯ ПРИЧИН ПОВРЕЖДЕНИЙ ВСЕХ СЕМИ ТЕЛ ЧЕЛОВЕКА.
- 2.3. Принципі оптимального поєднання централізованого і локального правового регулювання
- Ключ помогает находить в себе то оптимальное состояние, которое вам нужно.
- Ключ помогает находить в себе то оптимальное состояние, которое вам нужно.
- ПРИНЦИП КЛЮЧА — ПРИНЦИП ОПТИМАЛЬНОСТИ.