Árvore de Huffman e profundidade máxima

Conhecendo as frequências de cada símbolo, é possível determinar a altura máxima da árvore sem aplicar o algoritmo de Huffman? Existe uma fórmula que dê altura a essa árvore?

trees coding-theory user7060
fonte

Tente brincar com alguns exemplos e veja se consegue encontrar algum critério útil. Isso é o que eu faria se eu estivesse tentando responder à sua pergunta, mas é provavelmente melhor para você fazê-lo sozinho ...

Yuval Filmus

Sim, eu já tentei com um monte de exemplos, mas eu estou procurando uma expressão Litteral, por exemplo, uma assintótica limite, função do número de símbolos ...

user7060

Em termos do número de símbolos, você não pode fazer nada melhor do que

n - 1

$n-1$ por um lado, e

⌈ \log_{2} n ⌉

$\lceil \log_2 n \rceil$ no outro.

Yuval Filmus

Desculpa. Eu estava pensando sobre o número de símbolos e suas frequências. Por exemplo, talvez seja possível fornecer a profundidade máxima procurando simplesmente a menor frequência entre todos os símbolos?

n - 1

$n-1$ é um limite limitado na profundidade, estou interessado em um limite apertado.

user7060

max - \log_{2} p_{i}

$\max -\log_2 p_i$

Respostas:

A codificação de Huffman (assintoticamente) fica dentro de um bit da entropia da sequência. Isso significa que, se você calcular a entropia das frequências de seus símbolos, estará (assintoticamente) a um bit do comprimento médio (ou seja, a altura) do seu código. Você pode usar essa média para limitar o comprimento mais longo (em média) ou usar métodos combinatórios para obter limites determinísticos.

Ari Trachtenberg
fonte

O caso patológico seria quando a frequência do símbolo classificado se assemelhasse à da sequência de Fibonacci. N: = número de símbolos. para N> 2, altura máxima possível: N-1. para N == 1 ou 2: 1

Bill Liu
fonte

Não é isso que a pergunta faz.

Tom van der Zanden

De fato. A pergunta pede qualquer caso em que você fale sobre o pior caso.

Raphael