Как нарисовать дерево Хаффмана правильно

Question

У меня есть следующие символы и вероятность, и я хотел бы нарисовать дерево Хаффмана для них:

s = 0.04 || i = 0.1 || n = 0.2 || b = 0.04 || a = 0.3 || d = 0.26 || ~ = 0.06 

на основе алгоритма Хаффмана, я сгенерировал следующее дерево:

Это было сделано:

1. Регистрация s + i
2. Регистрация результат 1 и n
3. Регистрация ~ + d
4. Регистрация b + a
5. Регистрация результат 3 и 4
6. Регистрация результат 5 и 2

Мои вопросы: - это то, что я сделал правильно или нет? Если да, то приемлемо ли, что конечная вероятность (результат 6) больше 1?

Благодаря

Answer 1

Нет, что вы сделали не так, и нет, единственное, что является приемлемым в том, что окончательное число должно равняться сумме исходных чисел.

Суммы соответствуют вашему делу, так как 0,34 + 0,66 = 1, поэтому я не знаю, почему вы спрашиваете об этом. Кстати, цифры не обязательно должны быть вероятностями, поэтому сумма не обязательно должна быть 1. Часто числа - это частоты, т. Е. Количество числа раз, когда этот символ появился.

Что касается вашего дерева, вы всегда должны присоединяться к двум самым низким номерам, будь то лист или верхняя часть поддерева. В начале это s = 0.04 и b = 0.04. Вы этого не делали, поэтому ваше дерево не представляет собой приложение алгоритма Хаффмана. Затем к 0.08 добавьте ~ = 0.06. И так далее.