Лучшее дерево Хаффмана для оптимального сжатия

Question

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

Я использую этот вид дерева:

Вместо этого рода дерева:

Я думаю, что более 10 отдельных символов невозможно сжать на 8 битах.

Является ли первое изображение действительно оптимальным?

Answer 1

Самая основная идея состоит в том, чтобы добавить два наименьших узла, создав новый узел, значение которого равно сумме двух его дочерних элементов.

Соблюдение этого правила вплоть до корня дерева гарантирует, что полученное дерево будет оптимальным .

Таким образом, у вас нет контроля формы дерева: оно полностью зависит от вероятности распределения символов. Это может в конечном итоге стать вырожденным деревом (одна ветвь на уровень), если распределение вероятностей выглядит как серия Фибоначчи.

Создание дерева Хаффмана с заданной максимальной глубиной, следовательно, является более сложным и требует нарушения обычного правила всегда добавлять 2 наименьших узла. Результирующее дерево, очевидно, не будет оптимальным.