ハフマン符号化

huffman.scala

// P50
abstract sealed class Node[A]{
  val freq: Int
}

case class Leaf[A](element: A, freq: Int) extends Node[A]
case class Branch[A](left: Node[A], right: Node[A]) extends Node[A]{
  val freq = left.freq + right.freq
}

def huffman[A](ls: List[(A, Int)]): List[(A, String)] = {
  def makeTree(ls: List[Node[A]]): Node[A] = ls match{
    case Nil => throw new IllegalArgumentException
    case top :: Nil => top
    case _ => {
      val last = ls.sortBy(_.freq).slice(0, 2)
      makeTree(Branch(last(0), last(1)) :: ls filterNot {last.contains})
    }
  }
  def huffmanCode(n: Node[A], code: String): List[(A, String)] = n match{
    case Leaf(element, freq) => List((element, code))
    case Branch(left, right) => huffmanCode(left, code + "0") ::: huffmanCode(right, code + "1")
    case _ => throw new IllegalArgumentException
  }
  val top = makeTree(ls map {n => Leaf(n._1, n._2): Node[A]})
  huffmanCode(top, "")
}

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