0
$\begingroup$

I have to figure out the frequencies of 3 letters for Huffman encoding of {0, 10, 11}. One suggestion is in the order {$\frac{2}{3}$, $\frac{1}{6}$, $\frac{1}{6}$} as given in part (a) the 2nd slide of page 3 here. My question is whether the last 2 character frequencies need to be evenly split. Could we not have had {$\frac{2}{3}$, $\frac{2}{18}$, $\frac{1}{18}$}? Or could the 3 character frequencies be entirely different say {$\frac{1}{2}$, $\frac{1}{4}$, $\frac{1}{4}$}?

$\endgroup$
2
$\begingroup$

You want frequencies $f_1,f_2,f_3$ for three characters, so that their Huffman encodings are $(0,10,11)$.

The Huffman algorithm repeatedly "merges" the two least frequencies. So any choice that assigns the two least frequencies to the last two characters will work. That means $f_2,f_3 \le f_1$. Since these are frequencies you probably also want the values to add to $1$, but that is of no consequence for the algorithm.

In general the Huffman algorithm does not specify which branches go left and which go right (unless we add that to the implementation) so it is hard to guarantee codes $(0,10,11)$ instead of $(1,00,01)$ for instance.

$\endgroup$
0
$\begingroup$

At a higher level: For sets of n symbols, n fixed, the set of possible Huffman codes is finite (since the length of a Huffman code is at most n-1 bits). The set of possible frequencies is infinite.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.