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

Question

Я делаю упражнения для курса о передаче информации.Нам нужно, чтобы Хаффман кодировал в двоичный код алфавит.

Исходный алфавит имеет четыре символа с вероятностями:

• P (A) = 0,4
• P (B) = 0,3
• P (C) = 0,2
• P (D) = 0,1

Так что для Хаффмана я беру два символа с наименьшей вероятностью, чтоC и D в этом примере.Я строю поддерево с двумя листьями (C & D).Следующий символ в списке, B, имеет шанс 0,3.

Теперь я могу сделать две вещи.Либо создайте второе поддерево с A & B, поскольку вероятность B совпадает со значением CD поддерева.Второй вариант - поместить B вместе с поддеревом CD и создать большее дерево со значением 0,6.

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

Теперь у меня вопрос: какой метод выбрать?Создать новое поддерево для равной вероятности?Или положить равные вероятности в дерево?

Answer 1

В этом случае у вас есть только один выбор в алгоритме приложения Хаффмана.На каждом шаге вы должны выбрать две наименьшие вероятности.На втором этапе это 0,3 (B) и 0,3 (C & D).Вы не можете использовать A на этом шаге, так как он имеет более высокую вероятность 0,4.Итак, первое нарисованное вами дерево неверно, так как оно не является результатом применения алгоритма Хаффмана.

Второе дерево, которое вы нарисовали, также неверно.Или, по крайней мере, неправильно нарисовано.Бинарное дерево может иметь только две ветви в любой момент.Это не может иметь три.Правильное дерево - это A & (B & (C & D)).