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.
9
-
$\begingroup$ I suspect that you will want to add another constraint to disqualify the following construction: if you have only one symbol, zero bits encode it. Otherwise split the symbols into two non-empty parts, $S_1$ and $S_2$. Use prefix $0^k$ for elements in $S_1$ where $k = \sum_{s_i \in S_2} p_i$ and similarly use prefix $1^n$ for elements in $S_2$ where $n = \sum_{s_i \in S_1} p_i$. Now recurse on both parts. By construction, $N_0 = N_1$ achieving the global minimum of the objective function, but the codes are rather long. $\endgroup$– Peter TaylorCommented Sep 11, 2022 at 6:35
-
$\begingroup$ Thank you for the comment, but I did not fully understand it. How can you prove that this coding scheme is an optimal solution, e.g., by outperforming Huffman codes. $\endgroup$– lchenCommented Sep 11, 2022 at 7:20
-
$\begingroup$ If you consider just the bits which distinguish the two children of the root, by construction they contribute $kn$ zeros and $kn$ ones to the encoded message. Then the recursions on the two subtrees continue to maintain the balance $N_0 = N_1$. $\endgroup$– Peter TaylorCommented Sep 11, 2022 at 12:54
-
$\begingroup$ Yes, but why this is the optimal solution? $\endgroup$– lchenCommented Sep 11, 2022 at 15:09
-
2$\begingroup$ Cross-posted to cstheory.stackexchange.com/questions/52082/… . $\endgroup$– Emil JeřábekCommented Nov 1, 2022 at 16:52
|
Show 4 more comments
1 Answer
$\begingroup$
$\endgroup$
9
Proof for 3 symbols: We can assume that the codes are 0, 10, 11, any other choice is suboptimal.
Let the occurrences be $p_1\le p_2\le p_3$. We have 3 sensible options for the encodings:
Option 1. $p_1$: 10, $p_2$: 0, $p_3$: 11
After normalization, $N_0=p_1+p_2$, $N_1=p_1+2p_3$, $N=2p_1+p_2+2p_3=2-p_2$.
The objective function is $\frac{(p_1+p_2)(p_1+2p_3)}{2p_1+p_2+2p_3}$.
Option 2. $p_1$: 10, $p_2$: 11, $p_3$: 0
After normalization, $N_0=p_1+p_3$, $N_1=p_1+2p_2$, $N=2p_1+2p_2+p_3=2-p_3$.
The objective function is $\frac{(p_1+p_3)(p_1+2p_2)}{2p_1+2p_2+p_3}$.
Option 3. $p_1$: 11, $p_2$: 10, $p_3$: 0
After normalization, $N_0=p_2+p_3$, $N_1=2p_1+p_2$, $N=2p_1+2p_2+p_3=2-p_3$.
The objective function is $\frac{(p_2+p_3)(2p_1+p_2)}{2p_1+2p_2+p_3}$.
These are not compared so easily.
To compare the last two, the denominators are the same, so using $p_3=1-p_1-p_2$, so we get
$$(1-p_2)(p_1+2p_2)~VS~(1-p_1)(2p_1+p_2)$$ $$p_2-p_2(p_1+2p_2)~VS~p_1-p_1(2p_1+p_2)$$ $$p_2(p_3-p_2)~VS~p_1(p_3-p_1)$$
So we need to choose between options 2 and 3 depending on whether $p_1$ or $p_2$ is closer to $p_3/2$.
Comparing the other options leads to more complicated calculations, so your problem won't have a nice and simple answer, like the Huffman coding, but rather requires the solution of several inequalities.
-
$\begingroup$ I agree with you that my problem does not admit a simple answer, but my objective can also be finding a polynomial time algorithm computing the optimal coding policy. $\endgroup$– lchenCommented Sep 17, 2022 at 10:06
-
-
$\begingroup$ Maybe it is not correct to use "polynomial" in this problem, As far I as understand, the complexity does not depend on $m$, as the objective function only contains the statistics of $m$, i.e., portions of $0$ and $1$ bits in the message. Let me restate my problem: I seek an algorithm to compute an optimal coding scheme (like huffman algorithm). Maybe a naive approach is to search exhaustively the possible code combinations, but is there a better algorithm, e.g., relying on some sort of dynamic programming... This is what I am lokking for. $\endgroup$– lchenCommented Sep 18, 2022 at 1:36
-
$\begingroup$ Yes, I understand. Apart from eliminating a few trivial cases, like in the above solution, I don't really see how the exhaustive search could be sped up. $\endgroup$– domotorpCommented Sep 18, 2022 at 4:19
-
$\begingroup$ I agree with you. In fact I have been sitting down quite some time thinking over the problem. My feeling was to look at some sort of dynamic programming based structure or like HUffman tree, but the objective function in my case is more complex. Another issue which might be trivial, in your simple 3-symbol example, you implicitly assume that we will not choose longer codes, e.g., 3 bits, is it trivial to prove? $\endgroup$– lchenCommented Sep 18, 2022 at 9:40