Анализ алгоритма Оптимальность

Начнем с доказательства оптимальности алгоритма Хаффмана. Поскольку алгоритм работает рекурсивно, вызывая самого себя для последовательно сокращаемых алфавитов, будет естественно попытаться установить его опти- мальность посредством индукции по размеру алфавита.
Очевидно, он опти- мален для всех двухбуквенных алфавитов (так как использует всего один бит на букву). Итак, предположим посредством индукции, что он оптимален для всех алфавитов размера к - 1, и рассмотрим входной экземпляр, состоящий из алфавита S размера к.

Напомним, как работает алгоритм для этого экземпляра: он объединяет две бук- вы с наименьшей частотой у*, 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'. ■

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Анализ алгоритма Оптимальность:

  1. § 2. АЛГОРИТМ АНАЛИЗА ПСИХОЛОГО-ПЕДАГОГИЧЕСКИХ СИТУАЦИЙ
  2. Sшrvig Morten. Базовые алгоритмы Qt 4 (Qt 4's Generic Algorithms), 2000
  3. Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science, 2016
  4. АЛГОРИТМ
  5. АЛГОРИТМ УДАЧИ
  6. Алгоритм исцеления:
  7. Алгоритм избавления от боли
  8. Оптимальные условия
  9. 2. Специфика и алгоритмы работы с источниками.
  10. Алгоритм обработки результатов.
  11. АКТИВАЦИЯ: УРОВЕНЬ ОПТИМАЛЬНЫЙ
  12. ПОРОГ РАЗЛИЧЕНИЯ ОПТИМАЛЬНОГО
  13. 6.2.4. Поиск оптимальной финансовой модели СМИ
  14. 1.1.4. Оптимальная модель социальной сферы современного общества
  15. СИСТЕМНАЯ ДИАГНОСТИКА АЛГОРИТМ ОБНАРУЖЕНИЯ И УСТРАНЕНИЯ ПРИЧИН ПОВРЕЖДЕНИЙ ВСЕХ СЕМИ ТЕЛ ЧЕЛОВЕКА.
  16. 2.3. Принципі оптимального поєднання централізованого і локального правового регулювання
  17. Ключ помогает находить в себе то оптимальное состояние, которое вам нужно.
  18. Ключ помогает находить в себе то оптимальное состояние, которое вам нужно.
  19. ПРИНЦИП КЛЮЧА — ПРИНЦИП ОПТИМАЛЬНОСТИ.