Huffman coding: Difference between revisions

Revision as of 23:04, 11 February 2003

Revision as of 23:05, 11 February 2003

Line 6:

The text to be compressed is considered as a [[string]] of symbols. Symbols that are likely to be frequent are represented by a short sequence of [[bit]]s, and symbols that are likely to be rare are represented by a longer sequences of bits.

Huffman coding uses a specific method for choosing the representations for each symbol, resulting in a prefix-free code (i.e. no bit string of aany symbol is a prefix of the bit string of any other symbol).

It has been proven that Huffman coding is the most effective compression method of this type, that is, no other mapping of source symbols to strings of bits will produce a smaller output when the actual symbol frequencies agree with those used to create the code.

Huffman coding is optimal when the frequencies of input characters are powers of two.