Scala 霍夫曼解码

Question

我正在学习 scala coursera 课程并尝试为霍夫曼算法的 'decode' 方法编写一个实现。我是 scala 的新手。

以下是我的代码（到目前为止）。

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)
}

编写测试时，例如下面：

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

给出 t1 作为：Fork(Leaf('a',2), Leaf('b',3), List('a','b'), 5) 有人可以告诉我为什么实施 return 只是 List('a') 我假设 aabbb 的编码是：

a -> 0
b -> 1

Answer 1

在 Huffman 解码中，每次分叉、向右或向左时，您都取 subBits 的一位。在您的实现中，当您分叉和达到 Leaf 时，您会执行此操作。每当你到达一个字母时，你就会多扔掉一点。

你可以通过更多的测试看到，在你的情况下：

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)

或者您可以使用调试器并逐步执行您的代码。

Scala 霍夫曼解码

Scala huffman decoding

scala

decoding

huffman-code