Huffman Encoding – How to Discriminate Between Two Nodes with Identical Frequencies

algorithm-analysisalgorithmshuffman encoding

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:

enter image description here

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:

enter image description here

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.

Best Answer

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.

Related Topic