3
$\begingroup$

Suppose we have an optimal prefix-free code on a set $C = \{0, 1, \dots , n − 1\}$ of characters and we wish to transmit this code using as few bits as possible. How to represent any optimal prefix-free code on $C$ using only $2n − 1 + n\lceil\log n\rceil$ bits.

My approach:

  1. Begin with $n$ trees, each consists of a single node corresponding to one message word, with the weight of $p(i)$

  2. Repeat until there is only one tree. pick two subtrees with smallest weights combine them by adding a new node as root, and make the two trees its children. The weight of the new tree is the sum of the weight of two subtrees With a heap, each step of combining tree takes $O(\log n)$ time, and the total time is $O(n \log n)$.

Is there any solid proof?

  • 2
    I don't understand. In the first paragraph, you pose a problem of *transmitting* a code. In the second paragraph, you seem to talk only about *constructing* a code; I don't see any reference to transmission. In the end you state time complexities, but originally you required a certain space complexity. What's the connection between the two paragraphs? By the way, you may want to look at how Huffman codes are stored in JPEG files: only the lengths and symbols are stored, not the codes themselves, which are reconstructed from the lengths.2012-02-29

1 Answers 1

6

HINT: An optimal prefix-free code on $C$ has an associated full binary tree with $n$ leaves and $n-1$ internal vertices; such a tree can be unambiguously coded by a sequence of $2n-1$ bits that is easily derived from the preorder traversal of the tree. It only remains to associate the $n$ members of $C$ with the $n$ leaves of the tree, which can be done by listing them in the order in which preorder traversal encounters them. $\lceil\log n\rceil$ is enough bits to represent each of the $n$ members of $C$, and no delimiters are needed if each is alloted $\lceil\log n\rceil$ bits. That comes to a total of $2n-1+n\lceil\log n\rceil$ bits; you need only fill in the details.

  • 1
    Thank you for your response!2012-03-04