<p>Let <span class="math-container">$T$</span> be a text of length <span class="math-container">$L$</span> containing the symbols <span class="math-container">$$\mathcal{A}=\{a_1, a_2, \ldots, a_n\},$$</span> where each symbol appears at least once and no other symbol appears in <span class="math-container">$T$</span>.</p>
<p>Define the weights <span class="math-container">$$\mathcal{W} = \Big\{w_1 = \frac{c_1}{L}, \ldots, w_n = \frac{c_n}{L}\Big\},$$</span> where <span class="math-container">$c_i$</span> is the number of occurrences of <span class="math-container">$a_i$</span> in <span class="math-container">$T$</span>.</p>
<p>Given <span class="math-container">$\mathcal{A}$</span> and <span class="math-container">$\mathcal{W}$</span>, one can run Huffman's algorithm to find an optimal prefix-free binary code <span class="math-container">$$\mathcal{E} =\{e_1, e_2, \ldots, e_n\},$$</span> where <span class="math-container">$e_i$</span> is the encoding for <span class="math-container">$a_i$</span>.</p>
<p>Optimality of <span class="math-container">$\mathcal{E}$</span> means that the quantity <span class="math-container">$$\sum_{i=1}^{n}w_i l_i$$</span> is minimum among all other encodings, where <span class="math-container">$l_i$</span> is the bit-length of <span class="math-container">$e_i$</span>.</p>
<p>Optimal prefix-free binary codes are not unique in general. My goal is to establish some bounds on the number of optimal prefix-free binary codes for a given pair <span class="math-container">$(\mathcal{A},\mathcal{W})$</span>.</p>
<p>An optimal prefix-free binary code can be represented as a full binary tree. In particular, each leaf corresponds to a symbol, and every edge is labeled with either <span class="math-container">$0$</span> or <span class="math-container">$1$</span>. The codeword <span class="math-container">$e_i$</span> is obtained by reading the path from the root to <span class="math-container">$a_i$</span>.</p>
<p>The number of full binary trees with <span class="math-container">$n$</span> leaves is given by <span class="math-container">$$C_{n-1} = \frac{(2(n-1))!}{n!(n-1)!}.$$</span></p>
<p>Moreover, there are <span class="math-container">$n!$</span> ways of assigning symbols to leaves.</p>
<p>As a consequence, the number of optimal prefix-free binary codes for a pair <span class="math-container">$(\mathcal{A},\mathcal{W})$</span> is bounded from above by <span class="math-container">$$C_{n-1}n!=\frac{(2(n-1))!}{(n-1)!} \sim \sqrt{2}\Big(\frac{4(n-1)}{e}\Big)^{n-1}.$$</span></p>
<p>On the other hand, given a tree and a unique way of assigning symbols to leaves, there are <span class="math-container">$2^{n-1}$</span> ways of labeling the tree with <span class="math-container">$0$</span>s and <span class="math-container">$1$</span>s (for each internal node one can label the left child with <span class="math-container">$0$</span> or <span class="math-container">$1$</span>, and do the opposite for the right child).</p>
<p>Therefore, the number of optimal prefix-free binary codes for a pair <span class="math-container">$(\mathcal{A},\mathcal{W})$</span> is bounded from below by <span class="math-container">$2^{n-1}$</span>.</p>
<p>My questions are:</p>
<ol>
<li>Are the bounds correct?</li>
<li>Are there better bounds?</li>
<li>How can I use the fact that I know <span class="math-container">$\mathcal{W}$</span>?</li>
<li>Is there an efficient method for computing the number of optimal prefix-free binary codes for a pair <span class="math-container">$(\mathcal{A},\mathcal{W})$</span>?</li>
</ol>
<hr />
<p>Edited thanks to @J..yB..y</p>

CC BY-SA 4.0
2022-09-04T17:24:20.700Z
is question 4: is there an efficient #P algorithm? the answer would be no on significant sizes...
daniel pehoushek
CC BY-SA 4.0
2022-09-04T17:36:04.190Z
@danielpehoushek: Why? It seems to me that if you know the shape of the tree, then the number is easy to count. And if there are only a polynomial number of tree shapes, you should be able to determine all tree shapes using dynamic programming. So the question is: can there be a superpolynomial number of tree shapes, and what shold we do then?
Peter Shor 
CC BY-SA 4.0
2022-09-05T22:52:15.400Z
Cross-posted: https://cstheory.stackexchange.com/q/51843/5038, https://math.stackexchange.com/q/4522876/14578.  Please [do not post the same question on multiple sites](https://meta.stackexchange.com/q/64068).  This site forbids simultaneous cross-posting.
D.W.
CC BY-SA 4.0
2022-09-07T12:54:58.653Z
Considering the example of $n$ uniformly weighted symbols (where $n$ is a power of 2), doesn't each of the $n!$ mappings from the symbols to the $ \log_2 n$-bit binary strings give an optimal prefix-free code?  (Giving a lower bound of $n!$ for this class of instances...)
Neal Young
CC BY-SA 4.0
2022-09-07T21:52:31.903Z
@NealYoung: For that class of instances, yes. For the class of instances with weights $1, 2, 4, 8, 16, 32, 64,$ $\ldots$, $2^{n-1}$, there are exactly $2^{n-1}$ optimal trees, showing that the OP's lower bound is tight.
Peter Shor 
CC BY-SA 4.0
2022-09-12T14:19:50.197Z
@PeterShor, yes.  Also, by "shape" of the tree, do you mean the unordered tree? If so surely there can be a super-polynomial number of optimal tree shapes. E.g. consider, for $m=2^{d-1}$ (with $d$ an arbitrarily large integer), having $2m$ symbols of weight 1 and $m$ symbols of weight 2, so the optimal trees are those that are nearly balanced, with $2m$ leaves of depth $d+1$ and $m$ leaves of depth $d$.
Neal Young
<it.information-theory><coding-theory><binary-trees>
On the number of optimal prefix-free binary codes
Riccardo
# On the number of optimal prefix-free binary codes

(Asked by: username_0 on 2022-09-02)

Let $T$ be a text of length $L$ containing the symbols $$\mathcal{A}=\{a\_1, a\_2, \ldots, a\_n\},$$ where each symbol appears at least once and no other symbol appears in $T$.

Define the weights $$\mathcal{W} = \Big\{w\_1 = \frac{c\_1}{L}, \ldots, w\_n = \frac{c\_n}{L}\Big\},$$ where $c\_i$ is the number of occurrences of $a\_i$ in $T$.

Given $\mathcal{A}$ and $\mathcal{W}$, one can run Huffman's algorithm to find an optimal prefix-free binary code $$\mathcal{E} =\{e\_1, e\_2, \ldots, e\_n\},$$ where $e\_i$ is the encoding for $a\_i$.

Optimality of $\mathcal{E}$ means that the quantity $$\sum\_{i=1}^{n}w\_i l\_i$$ is minimum among all other encodings, where $l\_i$ is the bit-length of $e\_i$.

Optimal prefix-free binary codes are not unique in general. My goal is to establish some bounds on the number of optimal prefix-free binary codes for a given pair $(\mathcal{A},\mathcal{W})$.

An optimal prefix-free binary code can be represented as a full binary tree. In particular, each leaf corresponds to a symbol, and every edge is labeled with either $0$ or $1$. The codeword $e\_i$ is obtained by reading the path from the root to $a\_i$.

The number of full binary trees with $n$ leaves is given by $$C\_{n-1} = \frac{(2(n-1))!}{n!(n-1)!}.$$

Moreover, there are $n!$ ways of assigning symbols to leaves.

As a consequence, the number of optimal prefix-free binary codes for a pair $(\mathcal{A},\mathcal{W})$ is bounded from above by $$C\_{n-1}n!=\frac{(2(n-1))!}{(n-1)!} \sim \sqrt{2}\Big(\frac{4(n-1)}{e}\Big)^{n-1}.$$

On the other hand, given a tree and a unique way of assigning symbols to leaves, there are $2^{n-1}$ ways of labeling the tree with $0$s and $1$s (for each internal node one can label the left child with $0$ or $1$, and do the opposite for the right child).

Therefore, the number of optimal prefix-free binary codes for a pair $(\mathcal{A},\mathcal{W})$ is bounded from below by $2^{n-1}$.

My questions are:

1. Are the bounds correct?
2. Are there better bounds?
3. How can I use the fact that I know $\mathcal{W}$?
4. Is there an efficient method for computing the number of optimal prefix-free binary codes for a pair $(\mathcal{A},\mathcal{W})$?

---

Edited thanks to @J..yB..y

**Tags:** it.information-theory, coding-theory, binary-trees

> **Comments:**
> **username_1**: is question 4: is there an efficient #P algorithm? the answer would be no on significant sizes...  
> **username_2**: @danielpehoushek: Why? It seems to me that if you know the shape of the tree, then the number is easy to count. And if there are only a polynomial number of tree shapes, you should be able to determine all tree shapes using dynamic programming. So the question is: can there be a superpolynomial number of tree shapes, and what shold we do then?  
> **username_3**: Cross-posted: https://cstheory.stackexchange.com/q/51843/5038, https://math.stackexchange.com/q/4522876/14578.  Please [do not post the same question on multiple sites](https://meta.stackexchange.com/q/64068).  This site forbids simultaneous cross-posting.  
> **username_4**: Considering the example of $n$ uniformly weighted symbols (where $n$ is a power of 2), doesn't each of the $n!$ mappings from the symbols to the $ \log_2 n$-bit binary strings give an optimal prefix-free code?  (Giving a lower bound of $n!$ for this class of instances...)  
> **username_2**: @NealYoung: For that class of instances, yes. For the class of instances with weights $1, 2, 4, 8, 16, 32, 64,$ $\ldots$, $2^{n-1}$, there are exactly $2^{n-1}$ optimal trees, showing that the OP's lower bound is tight.  
> **username_4**: @PeterShor, yes.  Also, by "shape" of the tree, do you mean the unordered tree? If so surely there can be a super-polynomial number of optimal tree shapes. E.g. consider, for $m=2^{d-1}$ (with $d$ an arbitrarily large integer), having $2m$ symbols of weight 1 and $m$ symbols of weight 2, so the optimal trees are those that are nearly balanced, with $2m$ leaves of depth $d+1$ and $m$ leaves of depth $d$.  

---

## 0 answers

