Data Compression


Criteria

Survey Formats

Basics

Compression Methods

Data Formats


Huffman Code

Example

Characteristics

Variants

Dynamic Huffman Code

Construction of the Tree

1. Step

2. Step

3. Step

4. Step

Code Table

Encoding

Decoding

Alternative Construction

Variance

Adaptive Huffman Code


Glossary

Index


Download


www.BinaryEssence.com

Construction of the Tree


The Huffman algorithm generates the most efficient binary code tree at given frequency distribution. Prerequisite is a table with all symbols and their frequency. Any symbol represents a leaf node within the tree.


The following general procedure has to be applied:

  • search for the two nodes providing the lowest frequency, which are not yet assigned to a parent node
  • couple these nodes together to a new interior node
  • add both frequencies and assign this value to the new interior node

The procedure has to be repeated until all nodes are combined together in a root node.


Example: "abracadabra"


   Symbol   Frequency
     a       5
     b       2
     r       2
     c       1
     d       1

According to the outlined coding scheme the symbols "d" and "c" will be coupled together in a first step. The new interior node will get the frequency 2.


 <   ^   > 

Dynamic Huffman Code Dynamic Huffman Code 1. Step