Scala huffman decoding

Question

I am doing the scala coursera course and trying to write an implementation for the 'decode' method of the huffman algorithm. I am new to scala.

Following is my code(so far).

def decode(tree: CodeTree, bits: List[Bit]): List[Char] = {

def innerDecode(subTree: CodeTree, subBits: List[Bit]): List[Char] =
 subBits match {
  case head :: rest => {
    subTree match {
      case Leaf(c, w) => c :: innerDecode(tree, rest)
      case Fork(left, right, _, _) => {
        if ( head == 0) innerDecode(left, rest)
        else  innerDecode(right, rest)
     }
    }
   }
  case Nil => List[Char]()
 }
innerDecode(tree, bits)
}  

When writing a test e.g. below:

  val decoded = decode(t1, List(0, 1))
  assert(decoded === List('a','b'))//  decoded is returned as List('a') instead of List('a','b')

Gives t1 as: Fork(Leaf('a',2), Leaf('b',3), List('a','b'), 5) Can someone please advise why the implementation will return just List('a') The encode for aabbb I assume is:

a -> 0
b -> 1

Answer 1

In Huffman decoding you take one bit of subBits each time you fork, go right or left. In your implementation you do this when you fork and when you reach a Leaf. Each time you reach a letter you throw one additional bit away.

You could see that with few more tests, in your case:

decode(List(0,1)) === List(a)
decode(List(0,0,1)) === List(a,b)
decode(List(0,0,0)) === List(a,a)
decode(List(0,1,0)) === List(a,a)

Or you could use debugger and go trough execution of your code step by step.