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.
5
-
1$\begingroup$ 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. $\endgroup$– Neal YoungOct 30, 2022 at 21:36
-
$\begingroup$ @NealYoung I am sorry for the typo, it is "unbalancing". I seek to minimize it. What is the trivial solution in this case (minimizing)? $\endgroup$– lchenOct 31, 2022 at 4:22
-
$\begingroup$ 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. $\endgroup$– Neal YoungOct 31, 2022 at 21:19
-
1$\begingroup$ Cross-posted from mathoverflow.net/questions/430201/… . $\endgroup$– Emil JeřábekNov 1, 2022 at 16:51
-
$\begingroup$ 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. $\endgroup$– Neal YoungNov 2, 2022 at 15:18
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
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<n$. 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$$
-
$\begingroup$ 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. $\endgroup$– lchenNov 2, 2022 at 6:27
-
1$\begingroup$ Ah, well that would be a different question. You could make another post, I guess. $\endgroup$ Nov 2, 2022 at 15:10