Árbol Huffman y profundidad máxima

Conociendo las frecuencias de cada símbolo, ¿es posible determinar la altura máxima del árbol sin aplicar el algoritmo Huffman? ¿Hay alguna fórmula que le dé altura a este árbol?

trees coding-theory usuario7060
fuente

Intente jugar con algunos ejemplos y vea si puede encontrar algún criterio útil. Eso es lo que haría si intentara responder a su pregunta, pero probablemente sea mejor que lo haga usted mismo ...

Yuval Filmus

Sí, ya lo he intentado con una gran cantidad de ejemplos, pero estoy buscando una expresión Litteral, por ejemplo, un asintótica obligado, en función del número de símbolos ...

user7060

En términos de la cantidad de símbolos, no puede hacer nada mejor que

por un lado, y

por el otro.

n - 1

$n-1$

⌈ \log_{2} n ⌉

$\lceil \log_2 n \rceil$

Yuval Filmus

Lo siento. Estaba pensando en la cantidad de símbolos y sus frecuencias. Por ejemplo, ¿tal vez es posible dar la profundidad máxima mirando simplemente la frecuencia más baja entre todos los símbolos?

es un límite obligado en la profundidad, estoy interesado en un límite ajustado.

n - 1

$n-1$

user7060

max - \log_{2} p_{i}

$\max -\log_2 p_i$

Respuestas:

La codificación de Huffman (asintóticamente) se encuentra dentro de un bit de la entropía de la secuencia. Esto significa que si calcula la entropía de las frecuencias de sus símbolos, estará (asintóticamente) dentro de un bit de la longitud promedio (es decir, la altura) de su código. Puede usar este promedio para enlazar la longitud más larga (en promedio), o puede usar métodos combinatorios para obtener límites deterministas.

Ari Trachtenberg
fuente

El caso patológico sería cuando la frecuencia del símbolo ordenado se asemeja a la de la secuencia de Fibonacci. N: = # de símbolos. para N> 2, altura máxima posible: N-1. para N == 1 o 2: 1

Bill Liu
fuente

Esto no es lo que hace la pregunta.

Tom van der Zanden

En efecto. La pregunta pide cualquier caso mientras habla del peor de los casos.

Raphael