P50. Scala로 만들어본 허프만 코드

P50 (***) Huffman code.

First of all, consult a good book on discrete mathematics or algorithms for a detailed description of Huffman codes!

We suppose a set of symbols with their frequencies, given as a list of (S, F) Tuples. E.g. (("a", 45), ("b", 13), ("c", 12), ("d", 16), ("e", 9), ("f", 5)). Our objective is to construct a list of (S, C) Tuples, where C is the Huffman code word for the symbol S.

scala> huffman(List(("a", 45), ("b", 13), ("c", 12), ("d", 16), ("e", 9), ("f", 5)))
res0: List[String, String] = List((a,0), (b,101), (c,100), (d,111), (e,1101), (f,1100))

허프만 코드는 엘리먼트들의 비중치를 기준으로 오름차순 정렬한 후 

0번째와 1번째를 묶는 과정을 더 묶을 수 없을 때까지 반복하고,

만들어진 트리 왼쪽에 0, 오른쪽에 1을 할당해 읽어 내려가면 된다.

예를 들어, 문제처럼

(A, 45), (B, 13), (C, 12), (D, 16), (E, 9), (F, 5) 가 주어졌을 때

1) 

(F, 5)

(E, 9)

(C, 12)

(B, 13)

(D, 16)

(A, 45)

↓

((F, 5), (E, 9), 14)

(C, 12)

(B, 13)

(D, 16)

(A, 45)

2)

(C, 12)

(B, 13)

((F, 5), (E, 9), 14)

(D, 16)

(A, 45)

↓

((C, 12), (B, 13), 25)

((F, 5), (E, 9), 14)

(D, 16)

(A, 45)

3)

((F, 5), (E, 9), 14)

(D, 16)

((C, 12), (B, 13), 25)

(A, 45)

↓

(((F, 5), (E, 9), 14), (D, 16), 30)

((C, 12), (B, 13), 25)

(A, 45)

4)

((C, 12), (B, 13), 25)

(((F, 5), (E, 9), 14), (D, 16), 30)

(A, 45)

↓

(((C, 12), (B, 13), 25), (((F, 5), (E, 9), 14), (D, 16), 30), 55)

(A, 45)

5)

(A, 45)

(((C, 12), (B, 13), 25), (((F, 5), (E, 9), 14), (D, 16), 30), 55)

↓

((A, 45), (((C, 12), (B, 13), 25), (((F, 5), (E, 9), 14), (D, 16), 30), 55), 100)

트리로 그려진 결과. 루트부터 빨간 숫자를 따라 읽으면 그 요소의 허프만 코드다.

위 알고리즘 그대로 스칼라 코드로 구현해 보았다.

노드는 왼쪽에 값 또는 다른 노드들을 가질 수 있기 때문에 Either를 사용했고

양쪽에 노드를 가지는 노드는 HuffmanNode라는 case class로 정의했다.

/**
  *
  * P50.
  * 허프만 코드.
  *
  * @since 2017-01-06
  * @author Park Hyo Jun
  *
  */

class HuffmanCode[A] {

  type Node = (Either[A, HuffmanNode], Int) // (값 혹은 다른 노드, 비중치)
  case class HuffmanNode(left: Node, right: Node)

  /**
    * (값, 비중치) 리스트를 입력받아 (값, 허프만코드) 리스트를 만들어내는 메소드
    *
    * @param lst (값, 비중치) 리스트
    * @return List[A, HuffmanCode)]
    */
  def huffman(lst: List[(A, Int)]): List[(A, String)] = {

    /**
      * 허프만 코드에서 사용되는 트리를 만드는 메소드
      *
      * @param lst 노드 리스트
      * @return 허프만 트리의 최상위 노드
      */
    def huffmanTree(lst: List[Node]): Node = {

      /**
        * 노드 둘의 비중치를 더하는 메소드
        *
        * @param s1 허프만노드
        * @param s2 허프만노드2
        * @return 비중치
        */
      def getWeight(s1: Node, s2: Node): Int = s1._2 + s2._2

      /**
        * 리스트에서 왼쪽 두개를 묶어 노드로 만드는 메소드
        *
        * @param lst 노드 리스트
        * @return 왼쪽 두개가 노드로 묶인 노드 리스트
        */
      @tailrec
      def huffmanRecursive(lst: List[Node]): List[Node] = lst.sortWith(_._2 < _._2) match {
        case Nil | _ :: Nil => lst
        case h :: m :: t =>
          val node = (Right(HuffmanNode(h, m)), getWeight(h, m))
          huffmanRecursive(node :: t)
      }

      huffmanRecursive(lst).head // 루트노드
    }

    /**
      * 트리를 이용해 허프만 코드를 만들어내는 메소드
      *
      * @param root 루트 노드
      * @param fix  이전 할당된 허프만 코드
      * @return (A, HuffmanCode) 리스트
      */
    def huffmanCodes(root: Node, fix: String = ""): List[(A, String)] = root match {
      case (Left(x), _) =>
        List((x, fix)) // 값 노드인 경우 (값, 허프만 코드) 리턴
      case (Right(x), _) => // 노드인 경우 좌우 재귀호출
        val l = huffmanCodes(x.left, fix + "0")
        val r = huffmanCodes(x.right, fix + "1")
        l ::: r
    }
    
    huffmanCodes(huffmanTree(lst.map(x => (Left(x._1), x._2))))
  }
}

자바에선 이런 경우 항상 자바 빈 클래스를 만든다. 

자바와는 달리 스칼라는 튜플이 지원되니 튜플로 처리할 수 있었다. 

하지만 튜플은 오히려 코드의 가독성이 떨어질 수 있다고 생각한다. 

_1, 혹은 _2의 값이 무엇인지 바로 알 수 없으니까.