Должна ли частота правого поддерева узла больше, чем частота левого поддерева в дереве хаффмана?

Question

Может ли частота левого поддерева больше, чем правая?

Answer 1

(титр не задает позитивный вопрос, а тело просит соответствующий отрицательный вопрос, поэтому я не могу ответить да или нет!)

Вы можете выбрать левый и правый, как вам нравится , или эквивалентно присваивать 0 и 1, как вам нравится левым и правым ветвям, и вы по-прежнему будете иметь оптимальный код. Все изменения - это значения кода. Существует 128 различных наборов значений кода, которые вы можете сгенерировать из этого дерева.

В реальных приложениях длина каждого кода - это все, что происходит от дерева, после чего дерево отбрасывается. Затем вы можете присвоить значения кода с помощью a canonical approach. Это позволяет выбрать один из 128 возможных кодов. Тогда приемник должен знать длину кода для каждого символа для декодирования.

Кстати, есть еще одна вариация в дереве, которая возможна, поскольку вы можете выбрать либо D, либо L для сопряжения с U, поскольку они имеют одинаковую частоту. Это даст два разных дерева, хотя, поскольку результирующие длины кода одинаковы, остается только один канонический код.