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.

The following is an excerpt from CLRS's Introduction To Algorithms:

Although we don't prove it here, a prefix code can always achieve the optimal data compression among any character code, and so we suffer no loss of generality by restricting our attention to prefix codes.

Please answer the question by providing or referring to a valid proof of the above statement.

share|improve this question
add comment

1 Answer 1

The optimal coding referred to here is called Huffman coding. Huffman gave an algorithm which produces a prefix code which is optimal among character codes:

Huffman coding uses a specific method for choosing the representation for each symbol, resulting in a prefix code (sometimes called "prefix-free codes", that is, the bit string representing some particular symbol is never a prefix of the bit string representing any other symbol) that expresses the most common source symbols using shorter strings of bits than are used for less common source symbols. Huffman was able to design the most efficient compression method of this type: no other mapping of individual source symbols to unique strings of bits will produce a smaller average output size when the actual symbol frequencies agree with those used to create the code.

The Wikipedia article has complete details.

Huffman's original paper, " Method for the Construction of Minimum-Redundancy Codes", contains a proof of optimality.

share|improve this answer
    
I am aware of Huffman Encoding. I am specifically asking for proof of the optimality of prefix encoding, not Huffman encoding (which the book does provide a proof for). –  user26649 Aug 13 '12 at 4:46
    
Huffman coding can achieve the optimal data compression among any character code. Every Huffman code is a prefix code. Therefore, a prefix code can always achieve the optimal data compression among any character code. –  MJD Aug 13 '12 at 4:48
    
The proof of Huffman Encoding in the book only proves that Huffman Encoding is the optimal prefix tree, not the optimal data conpression among any character code. Could you refer me to a proof of Huffman Encoding being the optimal data conpression among any character code? –  user26649 Aug 13 '12 at 5:08
    
The original Huffman paper is only 3½ pages long, and contains a proof of optimality. I have edited the answer to include a link to an online copy. –  MJD Aug 13 '12 at 5:20
    
@MJD: I think what he's asking is: Does there exist a character code that gives better compression than any prefix code? A proof that, among all possible prefix codes, Huffman is optimal, doesn't resolve this question one way or the other. –  David Cary Aug 21 '12 at 4:44
show 1 more comment

Your Answer

 
discard

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