Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
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. –  joriki Feb 29 '12 at 18:52

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
    
Thank you for your response! –  Windows on ARM Mar 4 '12 at 13:12

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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