Full Example — Generating Huffman Code Table

/**
 * huffman.scala - Computes huffman compression algorithm.
 *
 *
 * Autor: Pedro Garcia Freitas [sawp@sawp.com.br]
 * License: Creative Commons
 *      <http: //creativecommons.org/licenses/by-nc-nd/2.5/en/>
 *
 * Apr 2011
*/

type Node = (Double, Any)

def huffman(list: List[(Double, String)]): List[(String, String)] = {
  def appendCode(m: String, x: List[Node]): List[Node]  = 
    for ((i,j) < - x) yield (i, m + j)

  def sortByFrequency(x: List[Node]) = {
    def sorter(e1: Node, e2: Node) = 
      if (e1._1 < e2._1) true else false
    x.sortWith(sorter)
  }

  def group(l: List[Node]): List[Node] = {
    val ll = sortByFrequency(l)
    ll match {
      case Tuple2(f1: Double, f2: List[Node]) :: 
           Tuple2(g1: Double, g2: List[Node]) :: t =>
        group((f1 + g1, appendCode("0", f2) ::: appendCode("1", g2)) :: t)
      case _ => ll
    }
  }

  def combining(e: List[Node]) = e match {
    case c :: t => c._2
    case _ => error("Not defined")
  }

  val k = for ((i,j) < - list) yield (i, List((j, "")))
  val combined = group(k)
  val result = combining(combined)
  result.asInstanceOf[List[(String, String)]]
}

def calculateAverageLength(probs: List[(Double, String)], 
                           codes: List[(String, String)]): Double = {
  def getProbabilities(probs: List[(Double, String)]) = 
    for ((prob, letter) <- probs) yield prob

  def getCodeLength(cods: List[(String, String)]) = 
    for ((letter, code) <- cods) yield code.length

  def calculateAverage(codeLengths: List[Int], probs: List[Double]) = {
    val zipedCodesLengths = codeLengths.zip(probs)
    val len = for((codelen, prob) <- zipedCodesLengths) yield codelen * prob
    val average = len.sum
    average
  }

  val probabilities = getProbabilities(probs)
  val codeLengths = getCodeLength(codes)
  val average = calculateAverage(codeLengths, probabilities)
  average
}

def calculateEntropy(probs: List[(Double, String)]) = {
  def getProbabilities(probs: List[(Double, String)]) = 
    for ((prob, letter) <- probs) yield prob

  def getLocalEntropy(probabilities: List[Double]) = 
    for (prob <- probabilities) yield prob * (math.log(prob) / math.log(2.0))

  def getEntropy(localEntropy: List[Double]) = 
    -localEntropy.sum

  val probabilities = getProbabilities(probs)
  val localEntropy = getLocalEntropy(probabilities)
  val entropy = getEntropy(localEntropy)
  entropy
}


/* Tests */
val probs = (0.4, "A") :: (0.2, "B") :: (0.1, "C") :: (0.05, "D") ::
  (0.1, "E") :: (0.075, "F") :: (0.075, "G") :: Nil
val codes = huffman(probs)
val averagelen = calculateAverageLength(probs, codes)
val entropy = calculateEntropy(probs)

println("\n")
println("Frequency and Symbols: " + probs)
println("Huffman code: " + codes)
println("Average length: " + averagelen)
println("Entropy: " + entropy)