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.

On my great quest for compressing/decompressing files with a Java implementation of Huffman coding (http://en.wikipedia.org/wiki/Huffman_coding) for a school assignment, I am now at the point of building a list of prefix codes. Such codes are used when decompressing a file. Basically, the code is made of zeroes and ones, that are used to follow a path in a Huffman tree (left or right) for, ultimately, finding a byte.

In this Wikipedia image, to reach the character m the prefix code would be 0111 enter image description here

The idea is that when you compress the file, you will basically convert all the bytes of the file into prefix codes instead (they tend to be smaller than 8 bits, so there's some gain).

So every time the character m appears in a file (which in binary is actually 1101101), it will be replaced by 0111 (if we used the tree above).

Therefore, 1101101110110111011011101101 becomes 0111011101110111 in the compressed file.

I'm okay with that. But what if the following happens:

  • In the file to be compressed there exists only one unique byte, say 1101101.
  • There are 1000 of such byte.

Technically, the prefix code of such byte would be... none, because there is no path to follow, right? I mean, there is only one unique byte anyway, so the tree has just one node.

Therefore, if the prefix code is none, I would not be able to write the prefix code in the compressed file, because, well, there is nothing to write.

Which brings this problem: how would I compress/decompress such file if it is impossible to write a prefix code when compressing? (using Huffman coding, due to the school assignment's rules)

This tutorial seems to explain a bit better about prefix codes: http://www.cprogramming.com/tutorial/computersciencetheory/huffman.html but doesn't seem to address this issue either.

share|improve this question
    
before generating the prefix codes, its pretty standard to ensure the input alphabet contains at least 2 symbols. huffman encoding is not well-suited for compression over small alphabets –  ardnew Nov 22 '12 at 2:25

1 Answer 1

up vote 2 down vote accepted

Actually you would use run-length encoding in such a situation. In essence you store the symbol and the number of repeats.

However, if you still insist on using Huffman coding, you could pick either one or zero to represent the symbol in the tree. This causes no problem really. Your tree simply states that symbol x is represented by bit m. Then you have n number of repeats of the encoded m as data. You could even then apply aforementioned RLE on the actual data (which is essentially a run of equal bits of length n) to compress further.

share|improve this answer
    
Well, that does make sense. However, for my school assignment I am supposed to make a compresser/decompresser with Huffman's algorithm only... or is run-length part of Huffman? –  Omega Nov 22 '12 at 1:35
1  
No, it is not. It's a separate method. You can of course combine many methods in practice. –  zxcdw Nov 22 '12 at 1:38
    
I was going to ask that if my classmate's programs tried to decompress my program's compressed files there would be trouble due to my "cheating" on this part. But thinking about it, you're right: there doesn't seem to be a problem at all. Thank you! So ultimately, Huffman's algorithm (alone) doesn't work well for this scenario? –  Omega Nov 22 '12 at 1:52
    
It works well enough, but because the way you have to store the codes(a single bit in this case) by the amount of encoded symbols it causes a repeating bit pattern. Well, while the 1/8 compression(some loss due to storing the tree) is good, it can be improved by applying the RLE method. So instead of storing say 254 bits of data, you store single 8-bit char representing the value 254 which then tells you how many successive bits there are in the encoded huffman data. Almost a 1/32 compression ratio, voila. ;) –  zxcdw Nov 22 '12 at 2:14
    
One question though: since the Huffman tree is a full binary tree (all internal nodes must have two child), it would mean I need to create a fake leaf as well, right? A leaf, in my program, has a 'char' value. Well, since I have to fake a leaf, what do you recommend? I think I do need to provide a value for the 'char'... or do I? The reason I want to respect this full-binary-tree rule is because apparently my school assignment wants to :( –  Omega Nov 22 '12 at 3:13

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.