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

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

Implementation of Huffman Algorithm in C