###Consider walking the tree to decode###

For encoding, using a map is smart, as you can convert your input byte to an output bitstring in a single lookup.

However, for decoding, you don't really know when your bitstring is going to end. Your code does one (unsuccessful) lookup for each bit in the bitstring until the bitstring ends. So if 011011 mapped to 'A', you'd do six total lookups. If you instead walked the huffman tree starting at the root, then for each bit you would move to the left or right child and check whether that node was a leaf. I think that this would be faster because it would be a node traversal versus a map lookup.

###Even faster using FSM###

I think you can get even faster decode times using a finite state machine. There is an article here that describes one implementation.

Consider walking the tree to decode

For encoding, using a map is smart, as you can convert your input byte to an output bitstring in a single lookup.

However, for decoding, you don't really know when your bitstring is going to end. Your code does one (unsuccessful) lookup for each bit in the bitstring until the bitstring ends. So if 011011 mapped to 'A', you'd do six total lookups. If you instead walked the huffman tree starting at the root, then for each bit you would move to the left or right child and check whether that node was a leaf. I think that this would be faster because it would be a node traversal versus a map lookup.

Even faster using FSM

I think you can get even faster decode times using a finite state machine. There is an article here that describes one implementation.