Construction Of Huffman tree for a given message
Step You have to follow:
Arrange all letters in the increasing order of their frequency and then construct binary tree by assigning least frequency letter as left child to the tree. After constructing binary tree from root to leaf every left branch assigned with 0 and right branch assigned with 1.
Notes: You can also take minimum frequency at right side or assigned it with 0 but be consistent whatever you choose.
Example: Message contains “EEEABBCCDDEEE” what will be total minimum bits required for store it.
Symbol Frequency A == 1 B == 2 C == 2 D == 2 E == 6 Step 1: Find two char with minimum frequency [3] 0/ \1 A B Now we have Weight gain from adding two minimum char ==> [3] C ==> 2 D ==> 2 E ==> 6 Now Find again 2 minimum and add it Here c => 2 and d => 2 is minimum [4] 0/ \1 C D Now we have wright [4] , [3], E=> 6 Here minimum is 4 and 3 so merge both above diagram. [7] 0/ \1 [3] [4] 0/ \1 0/ \1 A B C D Now we have wright [7], E=> 6 Here we have remaining 2 so merge both above diagram. [13] 0/ \1 E [7] 0/ \1 [3] [4] 0/ \1 0/ \1 A B C D ================================================= Symbol Frequency Code Code Length total Length A 1 100 3 3 B 2 101 3 6 C 2 110 3 6 D 2 111 3 6 E 6 0 1 6 ================================================= Total=27 Bit required. Another Good Resource
http://www.binaryessence.com/dct/en000080.htm