Huffman Algorithm is an encoding technique for symbols where most frequently occuring symbols are represented with short length bit strings and least frequently occuring symbols are represented with long bit strings.

This algorithm is widely used as the fundamental encoding algorithm in compressing audio and image files.

#### Algorithm (Pseudo-code)

*Huffman*(C: symbols ai with freuencies wi; i=1,2,3,.....n)

F: Forest of n rooted trees, each consisting of the single vertex ai and assigned weight wi in ascending order of wi

*while*F is not a tree

*begin*

- Replace the rooted trees T and T' of least weight from F with w(T) >= w(T') with a tree having a new root that has T as its left subtree and T' as its right subtree
- Label new edge to T with 0 and new edge to T' with 1
- Assign w(T)+w(T') as weight of new tree

*end*

**Example:**

Use Huffman Algorithm to encode the following symbols:

__Symbol__

__Frequency__

A 0.5

B 0.2

C 0.2

D 0.1

After running the algorithm, we'll get the following encodings:

__Symbol__

__Code__

A 0

B 100

C 11

D 101

## No comments :

## Post a Comment