Huffman coding is a technique which attempts to reduce the amount of bits required to represent a string of symbols. The algorithm accomplishes its goals by allowing symbols to vary in their length. Shorter codes are assigned to the most frequently used symbols in a string and longer codes to the symbols which appear less frequent.
Using binary tree with nodes containing the symbols and the probabilities of its occurrence, Huffman code can be generated.
Construct a tree as follows:
Step 1.Create leaf nodes for each symbols along with its probabilities of occurrence.
Step 2.Select the two leaf nodes with the lowest probabilities.
Step 3.Create a new node which is the parent of the two lowest probability nodes.
Step 4.Assign the new node the probability which is equal to the sum of its children's probabilities.
Step 5.Repeat from Step 2 until there is only one leaf node left.
See this example to make your concept clear:
Character Frequency
'b' 3
'e' 4
'p' 2
' ' 2
'o' 1
'!' 1
'r' 1
Now place these characters with their frequency as priority:
Now we get the first two elements and create link between them by creating a new binary tree node and add their possibilities. After that add the new node we created with sum of its priorities of it's children.
Repeat the same steps:
At last we got the final tree:
Now to get the code corresponding to the symbols assign 0 to the left branch and 1 to the right branch.
Thus we get the corresponding codes for the symbols:
Character Code
'b' 00
'e' 11
'p' 101
' ' 011
'o' 010
'!' 1000
'r' 1001
To decode the string of bits we need to traverse the tree for each bit, if the bit is 0 we take left step else if its 1 we take a right step until we hit a leaf.
[Expecting Your Valuable Comments]
Thank You
No comments:
Post a Comment