1
$\begingroup$

In my textbook there was the following question:

How many Huffman codes can be written for a set of three characters?

In the solution they said:

The Huffman code is determined by the source's probability vector. The code is determined by the order of the probabilities and their combinations. When given a vector of probabilities of the set of symbols the code is determined. The match between the vector space of probabilities and the appropriate code is not 1-1. The match depends on the relationship between the probabilities in the vector. For a group with one symbol there is one code. For a group with two symbols there is one symbol whose probability is greater than or equal to the other symbol and therefore there is a single Huffman code. For a group with 3 symbols - After arranging the vector of probabilities we get that the union of the two symbols with the same small probabilities is equal. But there are two options for uniting the groups in the second stage. We will get two possible codes: $0,10,11$ or $1,00,01$.

It made me wonder - what if we have $n$ elements in the set? Is there a general formula to count the number of ways? Also, why for set with one element it's $1$ and not $2$? (I can encode the element to be $0$ or $1$ no?)

$\endgroup$
2
  • $\begingroup$ For a set with two elements, there is only one code: $0,1$. $\endgroup$ Feb 9 at 9:21
  • $\begingroup$ @YuvalFilmus Right, but for one element why is it not two? $\{\{0\},\{1\}\}$. $\endgroup$
    – vesii
    Feb 9 at 10:24

1 Answer 1

4
$\begingroup$

A non-redundant prefix code on $n$ elements (which seems to be what your textbook means by Huffman code) is the same as a binary tree with $n$ leaves, and those are counted by Catalan numbers.

$\endgroup$
0

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.