スカラ・ハフマン・デコード

Question

私はスカラ・コースラ・コースをやっており、ハフマン・アルゴリズムの「デコード」メソッドの実装を書こうとしています。私はスカラーには新しいです。

以下は私のコードです（これまでのところ）。

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を与える：実装はaabbbためだけList('a') エンコードを返しますなぜ誰かが助言してくださいすることができ、私が想定しFork(Leaf('a',2), Leaf('b',3), List('a','b'), 5) です：ハフマンで

a -> 0 
b -> 1 

Answer 1

あなたがの1ビットを取るデコードsubBitsフォークするたびに、右または左に移動します。フォークするときとLeafに到達したときのあなたの実装でこれを行います。あなたが手紙に達するたびに、もう1ビット捨てます。

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) 

をそれとも、デバッガを使用してステップバイあなたのコードのステップの谷の実行を行くことができる：

は、あなたの場合には、さらにいくつかのテストでそれを見ることができました。