허프만 디코딩 (스칼라에서)

Question

허프만 디코딩을 수행하는 알고리즘을 작성하려고합니다. 저는 스칼라에서 그것을하고 있습니다 - 그것은 Coursera 과정을위한 과제이고 명예 암호를 위반하고 싶지 않습니다, 그래서 아래는 스칼라가 아닌 의사 코드입니다.

필자가 작성한 알고리즘은 tree 트리와 bits의 트리를 사용하며 메시지를 반환한다고 가정합니다. 그러나 제공된 트리에서 시도 할 때 NoSuchElementException (빈 목록의 선두)이 표시됩니다. 나는 이유를 알 수 없다.

내 코드가 약간 정돈 될 수 있음을 알고 있습니다. 함수형 프로그래밍에 아직 익숙하지 않아서 필자가 생각하기에, 아마도 가장 컴팩트 한 방법으로 작성한 것입니다. .

def decode(tree, bits) [returns a list of chars]: { 

    def dc(aTree, someBits, charList) [returns a list of chars]: { 

     if aTree is a leaf: 

      if someBits is empty: return char(leaf) + charList 
      else: dc(aTree, someBits, char(leaf) + charList) 

     else aTree is a fork: 

      if someBits.head is 0: dc(leftFork, someBits.tail, charList) 
      else someBits is 1: dc(rightFork, someBits.tail, charList) 
     } 

    dc(tree, bits, [empty list]) 

    } 

미리 도움을 주셔서 감사합니다. StackOverflow에서 처음이기 때문에 사이트를 가장 잘 활용하는 법을 배울 것입니다.

Answer 1

정확하게 이해하면 잎을 찾을 때까지 포크 (방향 비트 포함)를 통과하려고합니다. 그런 다음 리프 목록에 리프 값을 추가하고이 단계에서 단계를 반복하려고합니다. 내가 맞다면 원래 나무를 도우미 메서드로 전달해야합니다. leftFork 또는 rightFork이 아니라 지금 리프가됩니다. 그러면 다음과 같이됩니다.

if aTree is a leaf: 
    if someBits is empty: return char(leaf) + charList 
    else: dc(tree, someBits, char(leaf) + charList)