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?


  • 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)?
    – user7043
    Aug 10, 2014 at 15:02
  • @delnan You mean ordered from the most frequent to most infrequent? Hmm... How would that work?
    – shoham
    Aug 10, 2014 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.
    – user7043
    Aug 10, 2014 at 15:06
  • @delnan Maybe I'm confused, but how would you store the tree? In order scan? Can you elaborate?
    – shoham
    Aug 10, 2014 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.
    – user7043
    Aug 10, 2014 at 15:17

4 Answers 4


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);

    node n = toBuild.popFront();
    bool bit = grabBit();
        n.left = new node;
        n.value = chars[charIndex++];
    bit = grabBit();
        n.right = new node;
        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.

Another option is to store the length of each encoded token. Using just that you can build a huffman tree deterministically. You start with the shortest token and assign it all 0 bits. The next token you add with carry 1 to the encoding and add 0 bits as needed. To store the length of each token you can use a fixed huffman encoding.

This is the method used in DEFLATE.

  • 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, 2014 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. Aug 10, 2014 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, 2014 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).

  • 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, 2014 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.


You absolutely don't need the frequencies. Define a fixed algorithm that determines the code values depending on the code lengths for each code. The code lengths for single bytes will be on average less than eight and take three bits on average to store, so you do some statistics and define a fixed Huffman encode for code lengths.

Example: Assume 4 symbols with code lengths 2, 3, 3, 1. You assign the next possible code. So 2 -> 00. 3 -> 010. 3 -> 011. 1 -> 1. You only need to store the code lengths. In this case 2 bits per code were enough, giving eight bits for the table.

But we might assume that 3 bits is the most common code length, followed by 1 and 2. So we store "3" using one bit, and 1 a 2 using two bits. Now we have 2x1 + 2 + 2 = 6 bits.

for 256 values, you'll likely need less than 256 x 3 bits = 96 bytes.

If you don't mind slower encoding and decoding, you don't need to store a table at all. Define an algorithm that creates a Huffman code from the frequencies with reasonable results in all cases, including the worst case that you have no frequency results at all yet.

So the encoder builds a Huffman code for all frequencies zero and the decoder does the same. You encode the first byte, the decoder decodes the first byte. Both now know the first byte and create a new Huffman code for one non-zero frequency. They encode and decode the second byte, then build another code with the added information, and so on.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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