Дерево Хаффмана и максимальная глубина

Зная частоты каждого символа, можно ли определить максимальную высоту дерева без применения алгоритма Хаффмана? Есть ли формула, которая дает эту высоту дерева?

trees coding-theory user7060
источник

Попробуйте поиграть с несколькими примерами и посмотреть, сможете ли вы найти какой-нибудь полезный критерий. Это то, что я бы сделал, если бы попытался ответить на ваш вопрос, но, вероятно, вам лучше сделать это самостоятельно ...

Юваль Фильмус

Да, я уже пробовал много примеров, но я ищу буквальное выражение, например асимптотическую границу, функцию числа символов ...

user7060

Что касается количества символов, вы не можете сделать ничего лучше, чем с одной стороны, и с другой.

n - 1

$n-1$

⌈ \log_{2} n ⌉

$\lceil \log_2 n \rceil$

Юваль Фильмус

Сожалею. Я думал о количестве символов и их частотах. Например, возможно, можно дать максимальную глубину, просто посмотрев самую низкую частоту среди всех символов? - это точная граница на глубине, меня интересует жесткая граница.

n - 1

$n-1$

user7060

Я бы попытался посмотреть на и посмотреть, связано ли это с глубиной. Вы также можете попытаться придумать рекурсию, соответствующую фактическому алгоритму, и посмотреть, даст ли она вам что-нибудь.

max - \log_{2} p_{i}

$\max -\log_2 p_i$

Юваль Фильмус

Ответы:

Кодирование Хаффмана (асимптотически) попадает в один бит энтропии последовательности. Это означает, что если вы вычисляете энтропию частот вашего символа, вы будете (асимптотически) в пределах одного бита от средней длины (то есть высоты) вашего кода. Вы можете использовать это среднее значение, чтобы ограничить самую длинную длину (в среднем), или вы можете использовать комбинаторные методы, чтобы получить детерминированные границы.

Ари Трахтенберг
источник

Патологический случай был бы, когда отсортированная частота символа напоминает частоту последовательности Фибоначчи. N: = количество символов. для N> 2 максимально возможная высота: N-1. для N == 1 или 2: 1

Билл Лю
источник

Это не то, что задает вопрос.

Том ван дер Занден

Верно. Вопрос требует любого случая, когда вы говорите о худшем случае.

Рафаэль