Decoding a Huffman code
This code relies heavily on the previous recipe, Encoding a string using a Huffman tree. The same Huffman tree data structure is used next to decode a string representation of a Huffman coding.
Getting ready
Read the previous recipe, Encoding a string using a Huffman tree. The same HTree data structure is used in this recipe.
How to do it...
We traverse down the tree until we hit a leaf node. Then, we prepend the character found and restart from the root node. This process continues until no input is available:
decode :: String -> HTree -> String
decode str htree = decode' str htree
where decode' "" _ = ""
decode' ('0':str) (HTree _ l _)
| leaf l = value l : decode' str htree
| otherwise = decode' str l
decode' ('1':str) (HTree v _ r)
| leaf r = value r : decode' str htree
| otherwise = decode' str r
leaf tree = left tree == Null && right tree == NullSee also
To encode data using a Huffman tree, see...