Creating a code table for a Huffman tree

Submitted by metaperl on Sun, 10/02/2005 - 3:04am.

Our ultimate goal is to have a list in which each element gives the route on a tree to a particular letter. E.g.

('t',[L])

means go left from the top to code for a t

Similarly:

('a',[R,L])

means go right then left from the top to code for an a

So, we want to be able to do this:


*Main> codeTable (codes "tab")
[('t',[L]),('a',[R,L]),('b',[R,R])]

and the question is how?

Well, step one is to ask what granularity we need to take the input data on. And the answer is: we can take the input data one at a time.

Questions two and three are: what should our final and transition actions look like? Well, let's start with the final action. The final action for any particular leaf is going to yield something like this:

('a',[R,L])

we can restate that as: the final action as we move through a tree is to take a leaf and return the character there as well as the entire path to it.

Having stated the final action, we see what our transition action must be, we need to build up the entire path to that element as we make the transitions

The final code from SJT's implementation shows these final and transition actions as the solution to our problem:

-- Making a table from a Huffman tree.

codeTable :: Tree -> Table

codeTable = convert []

-- Auxiliary function used in conversion to a table. The first argument is
-- the HCode which codes the path in the tree to the current Node, and so
-- codeTable is initialised with an empty such sequence.

convert :: HCode -> Tree -> Table

-- Action Final
convert cd (Leaf c n) = [(c,cd)]

-- Action Transition
convert cd (Node n t1 t2)
= (convert (cd++[L]) t1) ++ (convert (cd++[R]) t2)