How to discriminate from two nodes with identical frequencies in a Huffman's tree?
- by Omega
Still on my quest to compress/decompress files with a Java implementation of Huffman's coding (http://en.wikipedia.org/wiki/Huffman_coding) for a school assignment.
From the Wikipedia page, I quote:
Create a leaf node for each symbol and add it to the priority queue.
While there is more than one node in the queue:
Remove the two nodes of highest priority (lowest probability) from the queue
Create a new internal node with these two nodes as children and with probability equal to the sum of the two nodes' probabilities.
Add the new node to the queue.
The remaining node is the root node and the tree is complete.
Now, emphasis:
Remove the two nodes of highest priority (lowest probability) from the queue
Create a new internal node with these two nodes as children and with probability equal to the sum of the two nodes' probabilities.
So I have to take two nodes with the lowest frequency. What if there are multiple nodes with the same low frequency? How do I discriminate which one to use?
The reason I ask this is because Wikipedia has this image:
And I wanted to see if my Huffman's tree was the same. I created a file with the following content:
aaaaeeee nnttmmiihhssfffouxprl
And this was the result:
Doesn't look so bad. But there clearly are some differences when multiple nodes have the same frequency.
My questions are the following:
What is Wikipedia's image doing to discriminate the nodes with the same frequency?
Is my tree wrong? (Is Wikipedia's image method the one and only answer?)
I guess there is one specific and strict way to do this, because for our school assignment, files that have been compressed by my program should be able to be decompressed by other classmate's programs - so there must be a "standard" or "unique" way to do it. But I'm a bit lost with that.
My code is rather straightforward. It literally just follows Wikipedia's listed steps. The way my code extracts the two nodes with the lowest frequency from the queue is to iterate all nodes and if the current node has a lower frequency than any of the two "smallest" known nodes so far, then it replaces the highest one. Just like that.
