Перепутанный деревьями Хаффмана
Быстрое учебное руководство при генерации дерева Хаффмана
Перепутанный Деревьями Хаффмана. Около конца той ссылки выше, это показывает дерево с 2 элементами, оставленными и затем завершенное дерево. Я смущен способом, которым это переходится. Существует ли особенный метод, дерево Хаффмана должно перейтись?
Например, 57:* с его правильным ребенком 35:* отклонен направо. Это, возможно, было 35, перешел налево с 22, перешел направо? Кроме того, почему не был 22:* разделенный на пары с 15:4 - это просто соединилось с 20:5 для создания нового дерева.
От начальной буквы obersvations кажется, что дерево не должно быть сбалансировано, или имейте любой определенный порядок кроме этого, частоты листа составляют в целом значение родительского узла. Могли два человека, создающие дерево Хаффмана с теми же данными, заканчивают с различными кодовыми значениями?
2 ответа
Ключ к деревьям Хаффмана заключается в следующем:
Отсортируйте этот список по частоте и сделайте два самых низких элемента листьями
Если у вас больше двух элементов с наименьшей частотой (например, 3,4,4...), подойдут любые два (3 и любой из 4-х - не два 4-х). Кроме того, неважно, какому из этих элементов с наименьшей частотой присвоен 0, а какому - 1. Эти два факта позволяют создавать различные, но правильные кодировки Хаффмана на основе одних и тех же данных.
Предполагается, что дерево Хаффмана должно быть сбалансировано по частотам, а не по количеству узлов. Таким образом, следующее сбалансировано:
(100 (50 (25 (12 (12 1)))))
а это - нет:
(((100 50) 25) ((12 12) 1)))
Конкретно в вашем вопросе 15 сопряжено с 20, а не с 22, потому что 15 и 20 - два наименьших оставшихся значения (оба меньше 22). Любое разветвление (левое или правое) было бы хорошо, если бы оно было последовательным (всегда меньше слева или всегда меньше справа, в рамках одного и того же алгоритма, так что кодировка может быть восстановлена на другом конце).
Все объяснено на странице. 22:* не был поставлен в пару с 15:4, потому что на каждом шаге объединяются два узла с наименьшими элементами. Это создает уникальный порядок.
Коды Хаффмана могут быть разными (если у вас есть несколько значений с одинаковой частотой или обмен 0 и 1 представлением лево/право), но длины Хаффмана не могут быть.
Ветвление влево/вправо - это просто вопрос того, как нарисовать дерево или представить его графически, так что это не имеет значения.