# Tag Info

## Hot answers tagged prefix-free-code

Accepted

### Does Huffman coding always produce shorter codes than the Shannon code?

This is actually problem 5.12 in Cover and Thomas's information theory textbook; show that the probability distribution ${1/12,1/4,1/3,1/3}$ gives a counterexample. And if you want a really nice ...
• 24.8k
Accepted

### Does a given regular language contain an infinite prefix-free subset?

Your problem can be solved in polynomial time. To begin, convert the given NFA to an equivalent NFA with the following additional properties: There are no epsilon transitions All states are ...
• 2,768

### Lower bound on the number of objects in the universe

Because an optimal prefix free code, e.g. a Huffman code, can be shown to be within one bit of source entropy. This is certainly in Cover and Thomas, I am pretty sure.
• 2,070
Accepted

### Lower bound on prefix code lengths

I'll try to show this, hope I interpreted the question correctly. Let $A_k=\{0,1\}^k.$ If $f(n)\leq n+\log n$ for $n$ large enough this implies \max\{\ell(c(x)):x \in A_1 \cup A_2\cup \ldots \cup ...
• 2,070
Accepted

### Prefix free code unbalancing 0 and 1 bits

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 ...
• 10.8k
Definitions Definition 1: Let $S$ be a set of words. We say that $S$ is nicely infinite prefix-free (made up name for the purpose of this answer) if there are words $u_0,\dots,u_n,\dots$ and \$v_1,\...