2
$\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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
11
  • $\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, 2016 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, 2016 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, 2016 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, 2016 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, 2016 at 15:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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