1
$\begingroup$

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.

$\endgroup$
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 Young
    Oct 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$
    – lchen
    Oct 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 Young
    Oct 31, 2022 at 21:19
  • 1
    $\begingroup$ Cross-posted from mathoverflow.net/questions/430201/… . $\endgroup$ Nov 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 Young
    Nov 2, 2022 at 15:18

1 Answer 1

3
$\begingroup$

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$$

$\endgroup$
2
  • $\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$
    – lchen
    Nov 2, 2022 at 6:27
  • 1
    $\begingroup$ Ah, well that would be a different question. You could make another post, I guess. $\endgroup$
    – Neal Young
    Nov 2, 2022 at 15:10

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.