Huffman coding: Difference between revisions

Revision as of 21:33, 14 February 2003

Revision as of 21:35, 14 February 2003

Line 7:

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 any 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. However, Huffman coding may fail in the case that the set of symbols has a uniform probability distribution.

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

[[Data compression/Arithmetic coding|Arithmetic coding]] produces slight gains over Huffman coding,

Line 26 ⟶ 27:

Huffman coding today is often used as a "back-end" to some other compression method.

[[Data compression/Deflation|Deflation]] (PKZIP's algorithm) and multimedia codecs such as [[JPEG]] and [[MP3]] have a front-end model and quantization followed by Huffman coding.

Note: Huffman coding fails when the set of symbols have a uniform probability distribution.