А если бы структура дерева оптимального префиксного кода была известна?

Существует метод, который часто помогает при поиске эффективного алгоритма: вы мысленно предполагаете, что у вас имеется частичная информация об опти- мальном решении, и смотрите, как воспользоваться этой неполной информацией для поиска полного решения.
(Как будет показано позднее, в главе 6, этот метод является одной из главных основ метода динамического программирования при разработке алгоритмов.)

В контексте текущей задачи будет полезно задаться вопросом: а если бы нам было известно бинарное дерево T *, соответствующее оптимальному префиксному коду, но не разметка листьев? Осталось бы разобраться, какой буквой должен быть помечен каждый из листьев T *, и код был бы найден. Насколько сложно это сделать?

На самом деле это достаточно просто, но сначала следует сформулировать базовый факт.

(4.29) Допустим, и и v — листовые узлы T*, такие что depth(u) < depth(v). Также предположим, что в разметке T *, соответствующей оптимальному префиксному коду, лист и помечается у S, а лист v помечается z S. В этом случае f >f.

Доказательство. Следующее короткое доказательство основано на методе за- мены. Допустим, f < f; рассмотрим код, который будет получен, если поменять местами метки узлов и и v. В выражении для среднего количества битов на букву

АВL(r)∑^/(lср

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

Еще по теме А если бы структура дерева оптимального префиксного кода была известна?:

  1. Глава 6 ПОНИМАНИЕ ГОЛОСОВОГО КОДА АНАЛИЗ ГОЛОСОВОГО КОДА
  2. Глава 6 ПОНИМАНИЕ ГОЛОСОВОГО КОДА АНАЛИЗ ГОЛОСОВОГО КОДА
  3. Глава 5 ПОНИМАНИЕ РЕЧЕВОГО КОДА АНАЛИЗ РЕЧЕВОГО КОДА
  4. Глава 5 ПОНИМАНИЕ РЕЧЕВОГО КОДА АНАЛИЗ РЕЧЕВОГО КОДА
  5. О друзьях-деревьях
  6. 3.11.10. Облако и Дерево
  7. Дерево упало
  8. I ВНАЧАЛЕ БЫЛА ИГРА
  9. Построение дерева целей.
  10. Над деревьями
  11. И НА КАМНЯХ РАСТУТ ДЕРЕВЬЯ
  12. Известные подходы
  13. Оптимальные условия
  14. Как была написана эта книга?
  15. ИДЕЯ 41 ДЕРЕВО, СПОСОБНОЕ ВЫДЕРЖАТЬ УРАГАН