Data Compression


Criteria

Survey Formats

Basics

Compression Methods

Data Formats


Huffman Code

Example

Characteristics

Variants

Dynamic Huffman Code

Adaptive Huffman Code


Glossary

Index


Download


www.BinaryEssence.com

Characteristics of Huffman Codes


Huffman codes are prefix-free binary code trees, therefore all substantial considerations apply accordingly [Prefix Codes (Prefix Property)].


Codes generated by the Huffman algorithm achieve the ideal code length up to the bit boundary. The maximum deviation is less than 1 bit.


Example:


Symbol  P(x)    I(x)   Code   H(x)
                      Length
  A     0,387   1,369   1     0,530
  B     0,194   2,369   3     0,459
  C     0,161   2,632   3     0,425
  D     0,129   2,954   3     0,381
  E     0,129   2,954   3     0,381
--------------------------------------
       theoretical minimum:   2,176 bit
       code length Huffman:   2,226 bit

The computation of the entropy results in an average code length of 2.176 bit per symbol on the assumption of the distribution mentioned. In contrast to this a Huffman code attains an average of 2.226 bits per symbol. Thus Huffman coding approaches the optimum on 97.74%.


An even better result can be achieved only with the arithmetic coding, but its usage is restricted by patents.


 <   ^   > 

 Code Trees 

 Arithmetic Coding 

Huffman Code Example Variants