<p>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:</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2016-02-16T22:09:32.493Z
So you agree that there is no obvious way to calculate for example the specific question mentioned in my post?
Johnatan Morian
CC BY-SA 3.0
2016-02-16T22:16:08.060Z
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.
David Eppstein
CC BY-SA 3.0
2016-02-17T05:46:42.993Z
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?
Sariel Har-Peled
CC BY-SA 3.0
2016-02-17T07:55:14.080Z
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$.
David Eppstein
CC BY-SA 3.0
2016-02-17T15:12:45.697Z
@Sariel; This is wrong. Lots of people seem to think this is the case, but there are [easy counterexmples](http://cstheory.stackexchange.com/questions/33747/does-huffman-coding-always-produce-shorter-codes-than-the-shannon-code). Maybe you're confusing the Shannon code with the Huffman code.
Peter Shor 
CC BY-SA 3.0
2016-02-17T18:42:55.250Z
Sorry @SarielHar-Peled with your formula can we limited the upper bound for 10 character with frequency 1 to 10?
Johnatan Morian
CC BY-SA 3.0
2016-02-17T19:35:33.833Z
@PeterShor Yes - sorry. I was not sure about the constant in the log... So multiply it by 2. Say $2 \lceil \log_2 (1/p) \rceil$. Every two merges the probability of a node increases by a factor of two. And as David says this is far from tight - it is just what one can do without being careful or thinking...
Sariel Har-Peled
CC BY-SA 3.0
2016-02-17T20:24:34.183Z
@Sariel: your bound of $2\lceil \log_2 (1/p) \rceil$ is only off by a constant (and isn't what David is talking about). I believe the correct constant is 1.44. Here, $1.44 = \log_\phi 2$ where $\phi$ is the golden ratio.
Peter Shor 
CC BY-SA 3.0
2016-02-17T20:50:40.667Z
Yeh. That would be the natural conjecture,..
Sariel Har-Peled
CC BY-SA 3.0
2016-02-18T10:55:56.530Z
Sorry @SarielHar-Peled 2*[log 1/p], which p should be replaced? probability is different !?
Johnatan Morian
CC BY-SA 3.0
2016-02-22T04:13:41.360Z
https://en.wikipedia.org/wiki/Huffman_coding#Problem_definition
Sariel Har-Peled
CC BY-SA 3.0
2016-02-16T22:07:03.450Z
2016-02-16T22:07:03.450Z
David Eppstein
<p>I'd like to as a variation on <a href="https://stackoverflow.com/questions/28833747/huffman-height-calculation-and-some-challenges">this question regarding Huffman tree building</a>. Is there any theory or rule of thumb to calculate the depth of a Huffman tree from the input (or frequency), without drawing tree. </p>

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

<cc.complexity-theory><ds.algorithms><np-hardness><ds.data-structures><greedy-algorithms>
Huffman Tree Depth, Is there any theory?
Johnatan Morian
# Huffman Tree Depth, Is there any theory?

(Asked by: username_0 on 2016-02-16)

I'd like to as a variation on [this question regarding Huffman tree building](https://stackoverflow.com/questions/28833747/huffman-height-calculation-and-some-challenges). 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.

**Tags:** cc.complexity-theory, ds.algorithms, np-hardness, ds.data-structures, greedy-algorithms


---

## 1 answers

### Answer by username_1 on 2016-02-16. Score: 6

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.

> **Comments:**
> **username_0**: So you agree that there is no obvious way to calculate for example the specific question mentioned in my post?  
> **username_1**: 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.  
> **username_2**: 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?  
> **username_1**: 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$.  
> **username_3**: @Sariel; This is wrong. Lots of people seem to think this is the case, but there are [easy counterexmples](http://cstheory.stackexchange.com/questions/33747/does-huffman-coding-always-produce-shorter-codes-than-the-shannon-code). Maybe you're confusing the Shannon code with the Huffman code.  
> **username_0**: Sorry @SarielHar-Peled with your formula can we limited the upper bound for 10 character with frequency 1 to 10?  
> **username_2**: @PeterShor Yes - sorry. I was not sure about the constant in the log... So multiply it by 2. Say $2 \lceil \log_2 (1/p) \rceil$. Every two merges the probability of a node increases by a factor of two. And as David says this is far from tight - it is just what one can do without being careful or thinking...  
> **username_3**: @Sariel: your bound of $2\lceil \log_2 (1/p) \rceil$ is only off by a constant (and isn't what David is talking about). I believe the correct constant is 1.44. Here, $1.44 = \log_\phi 2$ where $\phi$ is the golden ratio.  
> **username_2**: Yeh. That would be the natural conjecture,..  
> **username_0**: Sorry @SarielHar-Peled 2*[log 1/p], which p should be replaced? probability is different !?  
> **username_2**: https://en.wikipedia.org/wiki/Huffman_coding#Problem_definition  

---

