1
$\begingroup$

I'd like to as a variation on this question regarding Huffman tree building. Is there any theory or rule of thumb to calculate the depth of a Huffman tree from the input (or frequency), without drawing tree.

Specific Example is : 10-Input Symbol with Frequency 1 to 10 is 5. the above question mentioned depth is 5.

$\endgroup$
6
$\begingroup$

I don't know of a way to compute the length of the code exactly without constructing a Huffman code. And there may be more than one optimal Huffman code for a given set of weighted items, with different lengths. But there has been some related theory on lengths of Huffman codes:

Length-limited Huffman coding is a variant of Huffman coding where you are not allowed to use codewords longer than a given threshold. One can construct an optimal length-limited code in time $O(nL)$ where $n$ is the number of items and $L$ is the length bound; it is unknown whether this can be improved to match the time of unrestricted Huffman coding. See Larmore and Hirschberg, "A fast algorithm for optimal length-limited Huffman codes", JACM 1990, and Turpin and Moffat, "Practical length-limited coding for large alphabets", Computer J. 1995.

The length-limited problem was introduced earlier by Gilbert, "Codes based on inaccurate source probabilities", IEEE Trans. Inf. Th. 1971, who also showed that it is possible to restrict the length to log_2 n + (log log n)^{1+o(1)} while increasing the expected length by at most one. In "Restructuring ordered binary trees", J. Alg. 2004, Evans and Kirkpatrick write that restricting the length more strongly, to ceiling(log_2 n)+1, can force the expected length increase to be arbitrarily close to one. Evans and Kirkpatrick show that this strong length restriction can be obtained, even for alphabetic codes, with an expected increase in length of two.

$\endgroup$
  • $\begingroup$ So you agree that there is no obvious way to calculate for example the specific question mentioned in my post? $\endgroup$ – Johnatan Morian Feb 16 '16 at 22:09
  • $\begingroup$ I don't think the specific example is of much interest to this board, which should be only for research-level questions, which is why I answered a different question than the precise one you asked. $\endgroup$ – David Eppstein Feb 16 '16 at 22:16
  • 2
    $\begingroup$ It easy to show (I think) that if a symbol has probability $p$, then the length of its code word is at most $1+\log_2 (1/p)$ (or maybe 1+the ceiling of the log). That should be a good enough estimate for back of the envelope calculation, no? $\endgroup$ – Sariel Har-Peled Feb 17 '16 at 5:46
  • $\begingroup$ True, but that estimate could be far from the actual code length. E.g. consider a Huffman code for two elements with probabilities $\epsilon$ (close to zero) and $1-\epsilon$; the length is 1, independent of $\epsilon$. $\endgroup$ – David Eppstein Feb 17 '16 at 7:55
  • 2
    $\begingroup$ @Sariel; This is wrong. Lots of people seem to think this is the case, but there are easy counterexmples. Maybe you're confusing the Shannon code with the Huffman code. $\endgroup$ – Peter Shor Feb 17 '16 at 15:12

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.