Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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.

share|improve this question

4 Answers 4

up vote 2 down vote accepted

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.

share|improve this answer
    
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

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.

share|improve this answer
    
This is odd, as far as I can tell, the format of the compressed file we have to create will not contain any extra information about how to build the tree - instead, our programs are supposed to be able to generate such tree each time they read the compressed file. That's why I fear that my tree will be different than others, as I can't see a "standard" way to deal with it. –  Omega Nov 20 '12 at 0:02
    
@Omega Break ties alphabetically. No additional information required for that rule. –  btilly Nov 20 '12 at 2:02
    
@btilly: I'm not sure I understand that tip. Could you please elaborate? And thanks for replying! –  Omega Nov 20 '12 at 4:08
1  
@Omega I do not have your assignment. But I can tell you that it is logically impossible to generate the tree from well-compressed data. So somehow you have to specify the tree. Assuming that you have just frequency data, you can do it by having a completely unambiguous way of constructing the tree from that data. A frequency tie-break rule of, "choose alphabetically based on the first option in either side" is entirely unambiguous on how to construct the tree and saves you from any sort of "random coin flip." –  btilly Nov 20 '12 at 5:13
    
Of course if you don't have frequency data, the tree must be specified in some other way. But it MUST be specified in some way. (If it isn't, that is a flaw in the assignment as given to you.) –  btilly Nov 20 '12 at 5:15

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.

share|improve this answer
    
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

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.

share|improve this answer
1  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.