9
$\begingroup$

Knowing the frequencies of each symbol, is it possible to determine the maximum height of the tree without applying the Huffman algorithm? Is there a formula that gives this tree height?

$\endgroup$
  • 1
    $\begingroup$ Try playing around with a few examples, and see if you can find any useful criterion. That's what I would do if I were trying to answer your question, but it's probably better for you to do it yourself... $\endgroup$ – Yuval Filmus Feb 6 '14 at 19:14
  • $\begingroup$ Yes, I've already tried with a lot of examples, but I'm looking for a litteral expression, for instance an asymptotic bound, function of the number of symbols... $\endgroup$ – user7060 Feb 6 '14 at 19:35
  • 1
    $\begingroup$ In terms of the number of symbols, you can't do anything better than $n-1$ on the one hand, and $\lceil \log_2 n \rceil$ on the other. $\endgroup$ – Yuval Filmus Feb 6 '14 at 21:20
  • $\begingroup$ Sorry. I was thinking about the number of symbols and their frequencies. For instance, maybe it is possible to give the maximal depth by looking simply the lowest frequency among all the symbols ? $n-1$ is a rought bound on the depth, I'm interested in a tight bound. $\endgroup$ – user7060 Feb 6 '14 at 21:24
  • $\begingroup$ I would try to look at $\max -\log_2 p_i$ and see if it's related to the depth. You can also try to come up with the recursion corresponding to the actual algorithm, and see if it gives you anything. $\endgroup$ – Yuval Filmus Feb 6 '14 at 22:32
2
$\begingroup$

Huffman coding (asymptotically) gets within one bit of the entropy of the sequence. This means that if you calculate the entropy of your symbol frequencies, you will be (asymptotically) within one bit of the average length (i.e. height) of your code. You can use this average to bound the longest length (on average), or you can use combinatorial methods to get determinsitic bounds.

$\endgroup$
0
$\begingroup$

The pathological case would be when the sorted symbol frequency resembles that of Fibonacci sequence. N:= # of symbols. for N>2, max possible height: N-1. for N == 1 or 2: 1

$\endgroup$
  • 1
    $\begingroup$ This is not what the question asks. $\endgroup$ – Tom van der Zanden Jul 28 '16 at 7:32
  • $\begingroup$ Indeed. The question asks for any-case whil you talk about worst-case. $\endgroup$ – Raphael Jul 28 '16 at 7:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.