Тернарное сжатие Хаффмана

[Xendler]

Имеется алфавит с вероятностями. Необходимо построить тернарное дерево и закодировать символы. Проблема в построении дерева. Если с бинарным деревом все понятно, то здесь не ясно, как именно распределяются ветви.

[Brukvalub]

Что-то не видно тернарности нигде, кроме последних ветвей.

[Xendler]

Как я понял из лекции - разница между бинарным построением и тернарным в том, что в тернарном мы объединяем 3 узла с минимальной суммой вероятностей, поэтому в конце мы получаем в этом примере 2 ветви, связывать мы начинаем слева на право. вопрос в том, если мы при второй связке объедини нижние 3, то у нас остается ветвь на 2 узла и что с ней делать?

[Brukvalub]

Xendler в сообщении #1112707 писал(а):

у нас остается ветвь на 2 узла и что с ней делать?

А как поступают в бинарном алгоритме Хаффмана, кодируя нечетное число символов?

[Xendler]

Разобрался)

[venco]

Там, вроде, при каждом слиянии надо брать 3 текущих узла с минимальной вероятностью. Эти узлы могут быть на разном уровне.

[Xendler]

venco , да, всё верно. Уже разобрался)