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.

I'm writing a huffman encoding program in C. I'm trying to include the least amount of information in the header as possible, I know the simplest way to decompress the file in the header would be to store the frequencies of each character in the file, but for a large file with 256 characters it would take 2304 bytes ((1 byte for character + 8 bytes for long frequency) * 256), which I don't think is optimal.
I know I can reconstruct a tree from a preorder scan and an inorder scan of it, but that requires having no duplicate values. That is bad because I now have to store each node in the tree (in a huffman tree: n*2 - 1 with n being the number of unique characters), twice, having each node be a long value (which could take ((256*2 - 1) * 2) * 8 = 8176 bytes.

Is there a way I'm missing here, or are those my only options?

Thanks.

share|improve this question
    
It's been a while since I dealt with Huffman codes, but isn't it enough to reconstruct the tree without frequencies (i.e. the node value would only be the character)? –  delnan Aug 10 at 15:02
    
@delnan You mean ordered from the most frequent to most infrequent? Hmm... How would that work? –  shoham Aug 10 at 15:04
    
No, just the tree (as it would be produced given the real frequencies), but without actually including the frequencies (because the codes only depend on the position in the tree). Just the characters in order of frequency wouldn't work, I think. –  delnan Aug 10 at 15:06
    
@delnan Maybe I'm confused, but how would you store the tree? In order scan? Can you elaborate? –  shoham Aug 10 at 15:10
    
There are plenty of ways to store a tree. Removing the frequencies is orthogonal to how you store the tree, it just saves you eight bytes per node. There might also be a better way to store the tree but I'll have to think about that some more. –  delnan Aug 10 at 15:17

3 Answers 3

up vote 1 down vote accepted

There are 2 separate problems, store the topography and assign the leaf nodes

Assigning the leaf nodes can be done by storing the characters in in a predefined order so it can be extracted as needed.

Storing topography can be done by having a bit vector with 2 bits per parent node in the previous layer where 1 represents a compound node and 0 represents a leaf node

so first there is 1 bit for the root which is 1 and the next 2 bits will represent the next level down

to build the tree using the node{char value; node* left, right;} setup will be:

char[] chars;//prefill with the other array
int charIndex = 0;

node root;
vector<node*> toBuild(root);

while(!toBuild.empty()){
    node n = toBuild.popFront();
    bool bit = grabBit();
    if(bit){
        n.left = new node;
        toBuild.pushBack(n.left);
    }else
        n.value = chars[charIndex++];
    bit = grabBit();
    if(bit){
        n.right = new node;
        toBuild.pushBack(n.left);
    }else
        n.value = chars[charIndex++];
}
return root;

This is 2*n bits in the topography plus the permutation which is O(log n!) at the minimum.

share|improve this answer
    
Just to make sure I understand: 1. For storing the topography (the structure of the tree), I use a list of bits that is essentially a preorder scan of the tree, where 0 means it's a leaf node and 1 means it's not. Am I right? 2. For assigning the leaf nodes I can store them in a predefined order, what do you mean? Sorted by ASCII code? By frequency? And then what? After I assign them, what do I do with that? –  shoham Aug 10 at 17:12
    
sorted by the order you find them in during reconstruction. after that you have your huffman tree ready for use, leaf nodes have null child nodes and a value while non leaf nodes have the opposite. –  ratchet freak Aug 10 at 17:20
    
Oh, I think I got it, tell me where I'm wrong: I traverse the huffman tree in an order I like (pre/in/post), saving the leaf nodes's characters as I go along in their order, while doing that, I also write a list of bits that represent each node, 1 for a leaf node, 0 for a non-leaf node (or the other way around, doesn't matter). After I finish going through the tree, I write the list of characters and the list of bits to the header. When I try to decompress the file, I run through the header, build the tree, for every leaf node I find, I give it the matching character and then I'm done. Thanks! –  shoham Aug 10 at 18:12

First, as discussed in comments, you should get rid of the frequencies since you only need them to create the tree, not to reproduce the codes for decoding. In your program, but not on disk, the tree structure would might look like this (note the absence of frequencies):

struct Node {
  char value; // only used for leaf nodes
  // leaf nodes have BOTH child pointers NULL
  struct Node *left, *right;
}

I think the following scheme should allow reproducing the tree (though not the frequencies) using at most 2n * k bits for alphabets where each character takes k bits (so k <= log2 n <= k + 1):

  • Assign arbitrary consecutive indices to all interior nodes of the Huffman tree.
  • For each character, write out the index of the parent node.
  • Order the interior nodes by their indices. For each node except the root, write out the index of its parent node. For the root node, make its "parent" index equal to itself.

Since there are at most n-1 interior nodes, node indices fit into k bits each. So the interior node records plus the n character records, we arrive at slightly less than 2n*k bits. Decoding is relatively easy: First read the k character records, create the corresponding interior nodes, and iteratively add the newly discovered nodes (those referenced by other interior nodes but not yet created). You can recognize the root node by its self-reference.

Note that this would require a different tree structure, one with parent references instead of child references and a flag to distinguish leaf nodes (in memory, you can use NULL for the root's parent) If this makes it easier to generate the codes, you can invert the parent pointers, i.e. turn this representation into the nice top-down structure mentioned above.

Caveat: I assumed k is known to both parties (if not, a single extra byte should suffice for any practical application). I also assumes an alphabet of fixed-size bit vectors, but I think that's the case in virtually all applications (and if it's not true, you can add that metadata and still get away rather well).

share|improve this answer
    
That's... complicated... given the difference between this and writing the frequency of each char, in my case, is 256 bytes, I don't think it's worth the effort. But thanks a lot for putting in the time. –  shoham Aug 10 at 16:08

It's not necessary to store the actual frequencies of each symbol, or the exact topology of the Huffman tree. You only need to store enough information to encode the level on the tree at which each symbol resides.

You can modify a Huffman tree by shuffling symbols and internal branch nodes around on the same level without changing the coding efficiency of the tree. So it makes sense to map your particular huffman tree to its canonical version then you only need to specify which of the canonical trees you are using. I suggest, starting at the top then going down, shove all the symbols to the left as far as they will go, then sort them in ascending order.

Once you've made you tree canonical you need to actually encode it.

If you limit your tree depth to 32 levels then you can just encode a 256 by 5-bit array (160 bytes) giving the huffman tree level of each symbol.

You can approach the information-theoretic minimum of the encoding size of you arithmetically encode the subset of available symbols at each level, but I figure since you're using Huffman codes you're not ready for arithmetic encoding yet.

share|improve this answer

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.