КАК ДОКАЗАТЕЛЬСТВА АЛГОРИТМА ХОФФМАЛЬНОГО АЛГОРИТМА ГРЭЗА НАЧИНАЕТСЯ с оптимального дерева T?

Question

в Эта статья PRE 1 утверждает, что x и y представляют собой наименьшую вероятность и есть оптимальное дерево кода, в котором эти два символа являются братьями и сестрами на максимальной глубине ОтказПри доказательстве этого претензии автор начинается с дерева T , который имеет b и c на максимальной глубине дерева.Я не могу понять, почему дерево t называется оптимальным, потому что если x и y есть самые маленькие вероятностяки, то дерево t не может быть оптимальным, потому что ХоффманАлгоритм не построит такое дерево.Я думаю, что моя проблема здесь с пониманием того, что означает оптимальное дерево.

Если кто-то исходит от CSLR, это о лемме 16.2 и доказательством этого.

Answer 1

Кодное дерево составляет Оптимальное значение , если средняя длина кодового слова минимальна. Это не имеет ничего общего с алгоритмом Хаффмана. Алгоритм Хаффмана гарантированно создает оптимальное дерево кода, но могут быть другие кодовые деревья. Фактически алгоритм Хаффмана может вызвать разные кодовые деревья, используя разные правила разбивающих стяжек. Кроме того, не каждое оптимальное дерево кода может быть получено с использованием алгоритма Хаффемана, даже с произвольным правилом разрыва галстука.

Вот формальное определение оптимального дерева кода. Пусть $ \ pi $ Будьте распределением. $ \ pi $ -cost из дерева кода - ожидаемая длина кодового слова, где ожидается ожидание в отношении $ \ pi $ . Дерево кода является оптимальным для для $ \ pi $ Если его $ \ pi $ --Кост равен минимальному $ \ pi $ -cost любого дерева кода.