Quick Way to Decode a Huffman Table

(2nd version - my previous version was erased)

The scope of this blog is astronomy DIY tinkering. The current goal is to develop a set of routines to process some nice amateur astronomer photos and (hopefully) learn some neat stuff along the way. However, it is necessary to learn some techniques/tools out of the scope of the blog (or logbook) along the way sometimes, which is what makes any hobby fun. I came across a neat shortcut to decoding a Huffman table the other day and thought I would share it. It is part of Dave Coffin's dcraw code. You can find the code here. (Look for the make_decoder_ref function in the code)

Huffman Tree - Short Intro
First of all, what is a Huffman tree? I won't go into too many details because you can find it online but basically it is something like this (for the Nikon D90 images for example):
 

Huffman tree for the Nikon D90 NEF files

When reading a bit pattern, you basically start from the root of the tree, move down and left for a 0, down and right for a 1 until you reach a leaf. When you reach a leaf, that's your first data segment in your code (So 011 would yield 0x03 in this example). This variable length coding is quite good for compression where certain bit patterns occur more often than others (so you'd have the more frequent bit pattern represented by a shorter string, with the trade off that the less frequent bit pattern may be represented by a longer string).

Okay, so walking through trees are quite implemented by some sort of referencing mechanism (pointers or arrays). You just follow the arrow like in the diagram. This is usually fine since the depth of trees is logarithmic. It gets even better when the trees are not simply binary, but the behavior is the same.

But why not speed up if you can?

The trick
There is a way to access with one access as opposed to "following the arrows". The trick to getting this to work is the way the huffman table is made. Since one doesn't care about what the exact huffman code is, one can skew the tree. We can re-arrange is such that:

1. For every leaf at some depth d, the next available leaf to the right is at either the same depth d or lower.
2.  There is only one node that is not a leaf and has only one child. (Will make sense later on)

If you look at the Nikon tree above, you'll notice that it seems that they've done just that which is neat. There was no value for the righter most value so it is possible this is not implemented by Nikon.

We then have two properties:

1. From any leaf, the next leaf to the right is a bit pattern of same or greater length than the previous bit pattern
2. (general property of binary tree) At the same depth d, walking along the nodes from left to right is the same as adding 1 to the size d bit string that would represent it. You can prove this by induction. The base case would be a tree of depth 1 of which you could tack on two trees of depth onto as the n+1 case for ex:



Sample Binary tree

Knowing this, let's take the value of every leaf and just pad it to the right with zeros, so that it is as long as the longest possible bit pattern in the Huffman tree. So if my maximum length was 10 and my current bit pattern was 010111, it would then be: 0101110000 for a total length of 10.

Now, let me walk from one leaf of length d1 with pattern A1 and compare if o the next leaf to the right (which may be at a lower depth) A2 with depth d2:
A1(0...0)
A2(0...0)

I know the following. At depth d, I must walk along the nodes to the right at the same depth, so the first d bits must be (A1+1). After this, I know the rest must be zero padded. This is because there are two possible choices for the next leaf:

1. It is the same depth as the previous leaf so the rest of the values are zero padded.
2. It is deeper. This means we're on a node again. Since each node must have two children, then as we walk down the tree, we can always take the node to the left until we reach a leaf (which has 0 children of course).

Implementation
With all this information, there actually ends up being a quick way to implement the access of the huffman code. Let's say the maximum depth of the tree was D. All we need to do is make an array of size 2^D.
We fill the elements as follows:

huff = lengths = array(0., 2^D);
For each depth d:
          For each leaf from i = 1 to N
                  Fill the next 2^(D-d) elements in huff with the first code. Store the length d in a separate array for that code as well.
          end for
end for

And voila. Now, the read process is as follows:
1. Read D bits from buffer. If end of data, exit.
2. huff[D] is the next result and the length of the code was length[D]
3.  Only move cursor in buffer by D-length[D] and go back to 1

Notice that for each code one access is performed. No tree walkthrough necessary!

Drawbacks
This only works for skewed trees with the two-child rule stated earlier. Although it is easy to make a huffman tree following these rules (just loop through finding the min depth leaf and moving it right as you would for sorting), you can't do this if the code you're trying to decode has been encoded. This encoding scheme looks clearly intentional on Nikon's part and is a neat little trick.

Comments suggestions? I view this as a shared logbook. I try to share what I find neat and hope it to interest/inspire others to dig around outside their boundaries of expertise (these ideas are new to me). I hope this to be useful information to some person some day!

(astrophotos soon, and two other projects lined up, but not implemented... :-D)