스칼라 호프만 디코딩

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

예를 들면. 이다 구현 내가 가정 aabbb만을위한 List('a') 인 코드를 반환 할 이유 Fork(Leaf('a',2), Leaf('b',3), List('a','b'), 5) 누군가가 조언을 주시겠습니까 : 아래로 :

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

가 부여 t1 허프만에서

a -> 0 
b -> 1 

Answer 1

는 한 비트를 가지고 디코딩 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) 

을 또는 당신은 디버거를 사용하여 단계별로 코드 단계의 저점 실행을 갈 수 :

당신은 귀하의 경우, 몇 가지 더 테스트를 것을 볼 수 있었다.