# Prefix free code unbalancing 0 and 1 bits

We have a long message $$m$$ to encode. The message is composed of a set of symbols $$\{s_i\}$$. Let $$p_i$$ denote the number of appearance of $$s_i$$ in $$m$$. We seek to find a prefix-free code for each $$s_i$$ so as to minimize $$\frac{N_0N_1}{N}$$, where $$N_0$$ and $$N_1$$ denote the number of bits $$0$$ and $$1$$ in the coded message, respectively, $$N=N_0+N_1$$ denotes the length of the coded message. The prefix-free code system is a set of codes where any code is not a prefix of another. Our problem is to find such optimal coding system. Our problem resembles Huffman coding but with a more complex objective function.

• I think this question, as stated at least, has a trivial (and practically useless) answer, so is not research-level. BTW, OP, why do you title it "balancing", when minimizing $N_0 N_1/N$ does the opposite? And if you meant "maximizing", I think the question would still have a trivial (and practically useless) answer. Commented Oct 30, 2022 at 21:36
• @NealYoung I am sorry for the typo, it is "unbalancing". I seek to minimize it. What is the trivial solution in this case (minimizing)? Commented Oct 31, 2022 at 4:22
• Sorry, my comment was overstated. I conjecture that my "trivial" solution is optimal, but can only show that it is nearly so. I'll explain what I had in mind as an answer below. Commented Oct 31, 2022 at 21:19
• Cross-posted from mathoverflow.net/questions/430201/… . Commented Nov 1, 2022 at 16:51
• Can you explain more about why you care about this objective function? It seems quite strange. It's almost the same as maximizing $\max(N_0, N_1)/\min(N_0, N_1)$, which would be a very strange thing to do. Commented Nov 2, 2022 at 15:18

This answer does not quite answer the question. Rather, it describes a trivial solution and shows that it is close to optimal. FWIW I conjecture that the solution is actually optimal.

Let $$n$$ be the number of symbols given. Consider the code where $$s_n = 0^{n-1}$$ and $$s_i = 0^{i-1}1$$ for $$i. It has $$N_1 = n-1$$ and $$N_0=n(n-1)/2$$. By calculation its ratio is $$\frac{N_0N_1}{N_0+N_1} = n - 3 + \frac{6}{n+2}.$$

I conjecture this is optimal. It is easy to show it is nearly optimal:

Lemma 1. For any code, the ratio $$N_0N_1/N$$ is at least $$n - O(n/\log n)$$.

Proof. The ratio is $$N_0(N-N_0)/N$$. Any code has at most one all-0 codeword and at most one all-1 codeword, so $$n-1 \le N_0 \le N-(n-1)$$. Also, $$N \ge n \log_2 n$$ (as any binary tree with $$n$$ leaves has average leaf depth at least $$\log_2 n$$). So the ratio is at least $$\frac{(n-1)(N - (n-1))}{N} = n - 1 - \frac{(n-1)^2}{N} = n - O(n/\log n).~~~~~~\Box$$

• Thank you for the analysis. In fact I have thought of this solution, but the problem is that the code is too long. If we impose an upper-bound on the code length, I suppose the solution will be to make the codes the most unbalanced possible. Commented Nov 2, 2022 at 6:27
• Ah, well that would be a different question. You could make another post, I guess. Commented Nov 2, 2022 at 15:10