Как выбирается приоритет при построении дерева Хаффмана?

Question

Предположим, что мои персонажи и их частоты следующие:

Char    Freq.
 a       1
 b       2
 c       3
 d       4
 e       5
 f       6
 g       7
 h       8

При построении дерева на шаге 2 мы имеем это:

   [3]     [3]   [4]   [5]   [6]   [7]   [8]
   / \      c     d     e     f     g     h
  /   \
[1]   [2]
 a     b

Теперь, так как у нас есть два 3как мы можем определить их приоритет?

В кодировании Хаффмана это рассматривается как:

[3]    [3]     [4]   [5]   [6]   [7]   [8]
 c     / \      d     e     f     g     h   
      /   \
    [1]   [2]
     a     b

Почему?

Answer 1

Какая разница? На данный момент игнорируем от d до h, в первом случае вы получите

a = 00
b = 01
c = 1

и во втором случае

a = 10
b = 11
c = 0

Пока c находится на той же высоте в конечном дереве, его код будет иметь ту же длину.

Answer 2

Ваш случай не интересен.Присвоение 0 и 1 ветвям является произвольным, поэтому выбранный вами контур приводит к одному и тому же коду, т.е. к одинаковой длине кода в любом случае.или более групп с одинаковой общей частотой и разными формами.Любой выбор приведет к одинаковой общей оптимальности, то есть к тому же количеству битов для кодирования предоставленных символов на предоставленных частотах.Однако выбор может привести к различным деревьям формы с различными комбинациями длин битов.Затем можно сделать такой выбор, чтобы достичь более глубоких или более мелких деревьев, в зависимости от того, что требуется.

Answer 3

Я бы взял c с большим приоритетом (более короткий код). Это будет соответствовать основному принципу деревьев Хаффмана: приоритет / более короткий код для немедленных результатов и более низкий приоритет для большего анализа.