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

Huffman Code


The algorithm as described by David Huffman assigns every symbol to a leaf node of a binary code tree. These nodes are weighted by the number of occurences of the corresponding symbol called frequency or cost.


The tree structure results from combining the nodes step-by-step until all of them are embedded in a root tree. The algorithm always combines the two nodes providing the lowest frequency in a bottom up procedure. The new interior nodes gets the sum of frequencies of both child nodes.


Code Tree according to Huffman



The branches of the tree represent the binary values 0 and 1 according to the rules for common prefix-free code trees. The path from the root tree to the corresponding leaf node defines the particluar code word.



 <   ^   > 

Data Compression 11. Symbol: a Huffman Code: Example