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

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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

Wikipedia says (about decompression):

Before this can take place, however, the Huffman tree must be somehow reconstructed. In the simplest case, where character frequencies are fairly predictable, the tree can be preconstructed (and even statistically adjusted on each compression cycle) and thus reused every time, at the expense of at least some measure of compression efficiency. Otherwise, the information to reconstruct the tree must be sent a priori.

Answer 4

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.

Answer 5

Keeping in view the First Come First Serve mechanism then the problem of producing different codes for the same characters will be avoided.