Huffman coding algo is used to compress data using greedy choice so that it does not loose any information.
Example: A is given value 000, Frequency is 10, now since 000 is 3 bits, Total bits is 3x10 = 30
For E -> 3x15 = 45(total bits)
Total bits = 174
We can represent the above example in tree form as:
Step3: Add the next 2 nodes and add their frequency and add to the tree. Goes on
We keep on adding the nodes frequency and making tree, but 18 is more than the highest frequency i,e,15, hence we can no longer keep on adding nodes to this tree.
Hence we add next two lowest frequency to another subtree. Now since only E is left, we will add it to the tree which has lowest root value.
Now we will recalculate the total bits
Total bits = 146 much better than earlier 174
Example: A is given value 000, Frequency is 10, now since 000 is 3 bits, Total bits is 3x10 = 30
For E -> 3x15 = 45(total bits)
Total bits = 174
We can represent the above example in tree form as:
Our AIM:
To reduce the traversal through the code tree to the nodes which has the highest frequency
We keep on adding the nodes frequency and making tree, but 18 is more than the highest frequency i,e,15, hence we can no longer keep on adding nodes to this tree.
Hence we add next two lowest frequency to another subtree. Now since only E is left, we will add it to the tree which has lowest root value.
Now we will recalculate the total bits
No comments:
Post a Comment