Для задачи Тернари Хаффмана, можем ли мы сделать дерево (или схему кодирования) для «4» символов?

Question

Для задачи Тернари Хаффмана, можем ли мы создать дерево (или схему кодирования) для символов " 4 "? " Скажем, у меня есть 4 символа с этими частотами: частота (а) = 5 частота (б) = 3 частота (с) = 2 частота (д) = 2

Как я буду их кодировать в форме 0,1,2, чтобы ни одно кодовое слово не являлось префиксом другого кодового слова?

Answer 1

Хорошо для классического Хаффмана вы просто продолжаете объединять 2 узла с самой низкой частотой за раз, чтобы построить дерево, когда присваиваете 1 левому (или правому) ребру и 0 - другому ребру, а путь dfs к некоторому узлу - это код этих узлов.

то есть

Таким образом, в этом случае кодирование:

a - 1
b- 01
c - 001
d - 000

На троичном Хаффмане вы просто соединяете узлы с 3 низшими частотами за раз (и меньше узлов, если узлов недостаточно для последнего шага)

т.е.

Таким образом, в этом случае кодировка:

a - 2
b -12
с - 11
д - 10