# How to discriminate from two nodes with identical frequencies in a Huffman's tree?

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.

• 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.

-

If your assignment doesn't specify how to discriminate between identical frequencies, then the compression format is underspecified, and you generally can't expect independent implementations to interoperate.

This could either be an oversight on the part of the teacher -- or he/she could be trying to make a memorable point of all this.

I would first try asking for clarification, but absent further input, I would choose a method that is easy to implement and to document, then write up a standard that clearly documents your choice (such that your classmates could readily use it to make sure their implementation was compatible with yours), and turn it in with your assignment.

-
You're right - the assignment I received was kind of flawed. Asking was the solution. Yep, I do have to include info about the tree itself in the file. Thanks. – Omega Nov 21 '12 at 5:03

For huffman coding, if two nodes have the same frequency then for purposes of compression they are identical, so you can choose one or the other and you will get equal compression.

Try it - set your program up so it can be configured to choose either. Then run some test data through it and see if the resulting compressed data changes in size.

-
My worry isn't the size at the end - it is about when a classmate tries to decompress the file. If they build the tree with X configuration while I did mine with Y, then I guess there would be a serious problem. – Omega Nov 20 '12 at 17:00

If you're just writing your own encoding and decoding algorithms, it doesn't matter how you distinguish between equal valued nodes, so long as each half of the operation uses the same methodology.

The answer comes from your implementation of the priority queue. When a value that already exists in the queue is added again, is the new item considered lower or higher than the existing item with the same priority value. This is what you need to make sure of to ensure that your algorithm is compatible with those of your classmates.

-
So to make sure it is compatible, I should ask everyone how are they managing the priority queue? I just fear that in our assignment there is no specification about such queue. Well, in fact, my classmates might be doing something different than Wikipedia's instructions. – Omega Nov 20 '12 at 16:13

Simply choose any of the nodes. You must include information how to reconstruct the tree anyway in the compressed file.