Friday, June 7, 2013

Huffman Algorithm Implementation in C| Huffman Encoding| Huffman Algorithm Example

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
  • 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

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

1 comment :

  1. Aion Classic Kinah price is central to the game as it allows the purchase of skins, pets, and house decors, get better weapons and armor and other numerous items.


Related Posts Plugin for WordPress, Blogger...